4. Polygone verschneiden

Polygone verschneiden

  • D

    Hallo Geometrie- Freaks.

    Ich habe folgendes Problem:

    Zwei Polygone sollen miteinander verschnitten werden (Vereinigung, Differenz)
    Ich habe das Problem gelöst, für den Fall, dass die Polygone "saubere Schnittpunkte" miteinander habe - d.h. es überschneiden sich nur Kanten.
    das klappt eigentlich fast perfekt.
    - Ich ermittle alle Schnittpunkte
    - füge diese paarweise in die Polygone ein und
    - laufe im Wechsel die Polygonteile entlang.
    Ergebnis = ein oder meherere Teilpolygone (auch Lochbildende)

    Mein Problem ist, wenn eine Ecke eines Polygons auf eine Kante trifft.
    Noch schlimmer wird es, wenn sich zwei Ecken treffen.

    Wie muss dieser Sonderfall jeweils begandelt werden?

    Hat ev. jemand einen brauchbaren Link?
    Ich bräuchte sowas wie nen (verbalen) Algo.

    Thx
    Frank

    0
  • J

    Also Ecke auf Kante kannst Du auf den zweiten Fall reduzieren, füge einfach im ersten Polygon einen zusätzlichen Punkt ein. Dann haste den Punkt auf Punkt-Fall.

    Was passiert denn, wenn Du nun einen der beiden Punkte nimmst und ihn ein kleines Stückchen ins innere des anderen Polygons verschiebst. Dann biste zurück im normalen Fall. Nachdem dort alles berechnet ist mußt halt die neu erzeugten Schnittknoten wieder wegwerfen und durch die ursprüngliche Ecke ersetzen.

    Eventuell kannst Du das im ersten Fall auch direkt machen. Dadurch erhältst Du zwei Schnittpunkte, die Du danach eben wieder zusammenschnappen lassen mußt.

    0
  • T

    Vielleicht hilft dir das: http://www.cs.man.ac.uk/~toby/alan/software// (Code ist im Zip enthalten)

    0
  • D

    Die Bibliothek sieht sehr gut aus.
    Das Problem dabei ist die Lizenz. ??? Ich brauche das für ein commerzielles Tool.

    Mal sehen, was die Uni Manchester für Bedingungen hat.

    @Jester
    Ja so in etwa hatte ich mir auchg ws überlegt. Aber der PC ist ja 'ne blinde Nuss.
    Das grösste Problem ist zu erkennen welches Segment- Ende welcher Kontur zu verlängern ist.
    Kritisch ist auch bei Ecke/Ecke kontakt:
    - kreuzen die Polygone sich => dann brauchen die Ecken nur
    zu Schnitt deklariert werden oder
    - dann braucht es vor/ hinter den Ecken je einen Schnittpunkt
    (kann am Ende direkt an Eckekoordinate herangezogen werden)
    ABER: wie muss die Paarweise Zuordnung der 4 Schnittpunkte sein?
    (Laufen die Polygone an der Ecke in die "gleiche" Hauptrichtung oder
    sind die Gegenläufig?)
    Bei falscher Zuordnung erfolgt am Ende der wechsel von Poly1
    zu Poly2 (oder zurück) falsch.
    ODER: Sind am Treffpunkt der Ecken ein oder beide Segmente parallel?
    Das ist scheinbar die "dümmste" geometrielage.

    Das Hauptproblem scheint die genaue Erkennung der Ecklage(n) zu sein und deren richtige Behandlung.

    Gruss
    Frank

    0
  • T

    Ich sitze gerade über dem selben Problem und teste diese Lib:

    http://clippoly.sourceforge.net/

    Ich fange gerade erst damit an, aber wenn ich erste Resultate habe, melde ich mich wieder. Falls du diese Lib testest, würde ich mich über einen Erfahrungsbericht auch freuen.

    Ich habe mich gerade gestern mit jemanden unterhalten, der sowas schon mal (für einen Spezialfall) impelementiert hat. Der meinte, die (leider sehr oft auftretenden) Spezialfälle seien oft numerisch extrem unangenehm.

    0
  • D

    Hallo taurin,
    das Teil sieht auch recht interessant aus. Ich muss mir das mal genauer durchlesen.
    Mein Ansatz ist ja leicht ähnlich. mal sehen was da mit Ecken- Verdoppelung genu gemeint ist.
    Problem ist aber auch wider das GNU.

    Die (leider oft autretenden) Sonderfälle sind wirklich irgendwie das schlimmste an der Verarbeitung. Vor allem, wie erkenne ich die Sonderfälle genau und zuverlässig.

    Naja, ich werd mal weiter tüfteln.

    Gruss
    Frank

    0
  • T

    DerAltenburger schrieb:

    Die (leider oft autretenden) Sonderfälle sind wirklich irgendwie das schlimmste an der Verarbeitung. Vor allem, wie erkenne ich die Sonderfälle genau und zuverlässig.

    Das erkennen ist genau das Problem. Wann sind zwei Fließkommazahlen gleich? Wenn ihre Differenz kleiner einer gewissen Schranke ist. Und das wählen dieser Schranke ist das große Problem...

    0
  • D

    Ich habe sowas:

    !!! Ist editiert !!!
    !!! War vorher ne einfache, ältere Variante !!!

    im Header ist:

    enum TIntersectTyp {istParallel, //KEIN Schnit; Linien Parallel versetzt
    istInLine, //KEIN Schnit; Linien Parallel in Flucht
    istNotInLine, //Schnitt in Verlaengerung beider Linien
    istTouched, //Eine linie berührt die andere
    istEdged, //Beide Linien beruehren sich an Enden
    istIntersect}; //ECHTER Schnittpunkt
    deklariert

    TIntersectTyp __fastcall IntersectPhys(PRealPoint P0,PRealPoint P1, PRealPoint P2, PRealPoint P3)
{
  double X0,Y0;
  double X1,Y1,X2,Y2,X3,Y3;
  double A1_01,A2_01,SA_01,DA_01;
  double A1_12,A2_12,SA_12,DA_12;
  X0=0;
  Y0=0;
  X1=P1->X - P0->X;
  Y1=P1->Y - P0->Y;
  X2=P2->X - P0->X;
  Y2=P2->Y - P0->Y;
  X3=P3->X - P0->X;
  Y3=P3->Y - P0->Y;
  A1_01=X1 * Y2 - X2 * Y1;// / 2.0
  A2_01=X1 * Y3 - X3 * Y1;// / 2.0
  SA_01=fabs(A1_01 + A2_01);
  DA_01=fabs(A1_01 - A2_01);
  X0=P0->X - P2->X;
  Y0=P0->Y - P2->Y;
  X1=P1->X - P2->X;
  Y1=P1->Y - P2->Y;
  X2=0;
  Y2=0;
  X3=P3->X - P2->X;
  Y3=P3->Y - P2->Y;
  A1_12=X3 * Y0 - X0 * Y3;// / 2.0
  A2_12=X3 * Y1 - X1 * Y3;// / 2.0
  SA_12=fabs(A1_12 + A2_12);
  DA_12=fabs(A1_12 - A2_12);
  if (DA_01==0)
  { if (SA_01==0)
    { return istInLine;
    }
    else
    { return istParallel;
    }
  }
  else
  {
    if (SA_01>DA_01)
    { return istNotInLine;
    }
    else
    {
      if (SA_01==DA_01)
      {
/*      //Oldversion
        return itTouched;
*/      //OldVersion Ende
        //Newversion
        if (DA_12==0)
        { if (SA_12==0)
          { return istInLine;
          }
          else
          { return istParallel;
          }
        }
        else
        {
          if (SA_12>DA_12)
          { return istNotInLine;
          }
          else
          { if (SA_12==DA_12)
            { return istEdged;
            }
            else
            { return istTouched;
            }
          }
        //Newversion Ende
        }
      }
      else
      {
        if (DA_12==0)
        { if (SA_12==0)
          { return istInLine;
          }
          else
          { return istParallel;
          }
        }
        else
        {
          if (SA_12>DA_12)
          { return istNotInLine;
          }
          else
          { if (SA_12==DA_12)
            { return istTouched;
            }
            else
            { return istIntersect;
            }
          }
        }
      }
    }
  }
//  return itParallel;
}

    Der Funktion gebe ich je zwei Koordinaten (x,y als double)zweier zu testender Segmente.

    Die Funktion sagt, ob die Linien parallel (itParallel) sind, sich richtig schneiden (itIntersect) oder nur in gedachter Verlängerung (itNotInLine).

    Gibt es nur eine Punkt- Berührung (Eine Ecke trifft Kante oder zwei Ecken treffen sich) wird itTouched gemeldet.

    Den letzten Fall sollte ich noch etwas untergliedern. Und eine Fehlerschranke für die Vergleiche einführen.

    Was sagst Du dazu?

    Gruss
    Frank

    0
  • J

    kannst ja auch mal CGAL anschaun. ich weiß nicht genau, welche lizenzmodelle die anbieten. vielleicht reicht dir ja sowas wie lgpl?

    0
Anmelden zum Antworten