Kollision zweier 2dim Polygonen.

[Chris88]

Hi, ich suche einen ähnlichen Algorithmus für 2 Polygone, wie es man ihn überall für die Kollision von einem Punkt und einem Polygon findet.
Bewegung ist dabei relativ egal. Ich will einfach nur wissen, ob zwei 2dim Polygone kollidieren.

Habe bisher recht wenig gefunden. Das beste von allem waren Algorithmen in anderen Programmiersprachen, welche dort spezifische Funktionen benutzen, welche ich wohl schlecht in Delphi konvertieren könnte. Geschweige denn verstehen.

Gruß
Chris

[Reinhard Kern]

Zitat:

Zitat von Chris88

Hi, ich suche einen ähnlichen Algorithmus für 2 Polygone, wie es man ihn überall für die Kollision von einem Punkt und einem Polygon findet.
Bewegung ist dabei relativ egal. Ich will einfach nur wissen, ob zwei 2dim Polygone kollidieren.

Habe bisher recht wenig gefunden. Das beste von allem waren Algorithmen in anderen Programmiersprachen, welche dort spezifische Funktionen benutzen, welche ich wohl schlecht in Delphi konvertieren könnte. Geschweige denn verstehen.

Gruß
Chris

Hallo,

2 Polygone kollidieren, wenn sich irgendwelche ihrer Umrandungslinien schneiden. D.h. bei 1 Fünf- und 1 Sechseck 5 x 6 = 30 mal berechnen, ob sich 2 Geradenstücke (nicht Geraden!) schneiden. Ich weiss nicht, ob es eine schnellere Möglichkeit gibt.

Gruss Reinhard

[Hawkeye219]

Hallo Chris,

ich kann keine Aussage über die zu erreichende Geschwindigkeit machen, aber hast du es schon einmal mit den Region-Befehlen aus der Win32-API versucht? Mit CreatePolygonRgn kannst du aus deinen Polygonen jeweils eine Region erzeugen, mit CombineRgn und dem Modus RGN_AND prüfst du, ob es Überdeckungen gibt.

Gruß Hawkeye

PS: Willkommen in der Delphi-PRAXiS!

[Corpsman]

Du Must auch Berücksichtigen das 1 Polygon Komplett in einem Anderen drin sein kann.

Ich zieh mir zu diesem Zeug grad die Ganze Theorie rein. Aber es wird noch ein paar Tage dauern bis ich verwertbare Ergebnisse habe.

[Sidorion]

Solange die Polygone beide Konvex sind, kollidieren sie, wenn ein Punkt des ersten im zweiten oder ein Punkt des zweiten im ersten liegt.
Nachdem Du wie Du schriebst bereits einen Algorithmus hast, der einen Punkt mit einem Poly vergleicht sollte das einfach sein.
Du kannst aber auch zuerst jeweils den Umkreis (Oder Umrechteck, ist schneller, aber ungenauer) beider Polygone berechnen (einmal reicht, oder sobald sie sich ändern) und erstmal gucken, ob sich die Umkreise berühren. Wenn nein kollidieren sie nicht, wenn ja, musst Du Punktgenau werden.

Bei Konvexen Polygonen gilt die erste Regel immernoch, aber in der Einschränkung, dass wenn nicht, die Polys dennoch kollidieren können. In dem Fall musst Du dann wirklich alle Seiten paarweise kreuzen.

[Reinhard Kern]

Zitat:

Zitat von Corpsman

Du Must auch Berücksichtigen das 1 Polygon Komplett in einem Anderen drin sein kann.

Ich zieh mir zu diesem Zeug grad die Ganze Theorie rein. Aber es wird noch ein paar Tage dauern bis ich verwertbare Ergebnisse habe.

Hallo,

ja, das habe ich übersehen. Aber das bedeutet nur, dass man noch 2 Prüfungen Punkt zu Polygon anhängen muss, wobei es ja egal ist, welchen Punkt man jeweils nimmt, also am einfachsten den Startpunkt für den Umriss.

Gruss Reinhard

[Chris88]

Das mit dem gegenseitigen Punkttest, kommt mir etwas Langsam vor.
Versuche gerade die Lösung von Hawkeye219 zu realisieren. Mir fehlt allerdings noch eine Zeile :-/

Code:

function PolygonInPolygon(PointArrayA, PointArrayB: Array of TPoint):boolean;
var RgnA, RgnB, RgnC: hdc;
begin
  RgnA := CreatePolygonRgn(PointArrayA,Length(PointArrayA),Winding);
  RgnB := CreatePolygonRgn(PointArrayB,Length(PointArrayB),Winding);
  try
    CombineRgn(
      RgnC,       // handle to destination region
      RgnA,       // handle to source region
      RgnB,       // handle to source region
      RGN_AND     // region combining mode
    );
    (* Hier muss natürlich jetzt eine Abfrage stehen, ob es RgnB ein Polygon ist *)
  finally
    DeleteObject(RgnA);
    DeleteObject(RgnB);
    DeleteObject(RgnC);
  end;
end;

Wie muss jetzt mein Vergleich jetzt Aussehen? Ich kenne mich mit Regionen in keinster Weise aus.
Für meinen Punkttest benutze ich übrigens auch die Windows API Funktion.

Gruß
Chris

[OregonGhost]

Der Rückgabewert von CombineRgn kann einer der folgenden sein:

Zitat:

NULLREGION The region is empty.
SIMPLEREGION The region is a single rectangle.
COMPLEXREGION The region is more than a single rectangle.
ERROR No region is created.

Wenn SIMPLEREGION oder COMPLEXREGION dabei rauskommt, kollidieren die also, schätze ich.

[igel457]

Wie wäre es damit? Ich hatte schonmal das selbe Problem...

http://www.coding-board.de/board/sho...6002#post96002

EDIT: Ich habe den Code mal hier her kopiert, um toten Links vorzubeugen:

Delphi-Quellcode:

type
  TPointArray = array of TPoint;

function PointInPolygon(const Polygon : TPointArray; const P : TPoint): boolean;
var
  ToTheLeftofPoint, ToTheRightofPoint : byte;
  np : integer;
  OpenPolygon : boolean;
  XIntersection : real;
begin
  ToTheLeftofPoint := 0;
  ToTheRightofPoint := 0;
  OpenPolygon := False;

  if not ((Polygon[0].X = Polygon[High(Polygon)].X) and
   (Polygon[0].Y = Polygon[High(Polygon)].Y)) then
   OpenPolygon := True;

  for np := 1 to High(Polygon) do
   if ((Polygon[np - 1].Y <= P.Y) and
     (Polygon[np].Y > P.Y)) or
     ((Polygon[np - 1].Y > P.Y) and
     (Polygon[np].Y <= P.Y)) then
   begin
     XIntersection := Polygon[np - 1].X +
      ((Polygon[np].X - Polygon[np - 1].X) /
      (Polygon[np].Y - Polygon[np - 1].Y)) * (P.Y - Polygon[np - 1].Y);

     if XIntersection < P.X then Inc(ToTheLeftofPoint);
     if XIntersection > P.X then Inc(ToTheRightofPoint);
   end;

  if OpenPolygon then
  begin
   np := High(Polygon);
   if ((Polygon[np].Y <= P.Y) and
     (Polygon[0].Y > P.Y)) or
     ((Polygon[np].Y > P.Y) and
     (Polygon[0].Y <= P.Y)) then
   begin
     XIntersection := Polygon[np].X +
      ((Polygon[0].X - Polygon[np].X) /
      (Polygon[0].Y - Polygon[np].Y)) * (P.Y - Polygon[np].Y);

     if XIntersection < P.X then Inc(ToTheLeftofPoint);
     if XIntersection > P.X then Inc(ToTheRightofPoint);
   end;
  end;

  if (ToTheLeftofPoint mod 2 = 1) and (ToTheRightofPoint mod 2 = 1) then
   Result := True
  else
   Result := False;
end;

[Chris88]

@igel457: Das ist ja nur eine Funktion, um zu testen, ob ein Punkt in einem Polygon liegt. Ich suche aber eine Funktion, welche prüft ob ein Polygon in einem anderen Polygon ist...


Habe meine Funktion mal angepasst, sie funktioniert aber nicht.
Hier mal die Funktion, welche ich zum testen benutzt habe:

Delphi-Quellcode:

procedure TestPolygonInPolygon;
var
  RgnA, RgnB, RgnC: hdc;
  TestA, TestB: Array of TPoint;
begin
  SetLength(TestA, 3);
  TestA[0] := point(1,1);
  TestA[1] := point(5,1);
  TestA[2] := point(2,6);

  SetLength(TestB, 3);
  TestB[0] := point(3,1);
  TestB[1] := point(1,4);
  TestB[2] := point(4,4);

  RgnA := CreatePolygonRgn(TestA,3,Winding);
  RgnB := CreatePolygonRgn(TestB,3,Winding);
  try
    showmessage(IntToStr(CombineRgn(
      RgnC,       // handle to destination region
      RgnA,       // handle to source region
      RgnB,       // handle to source region
      RGN_AND     // region combining mode
    ))+#10+'NULLREGION: '+IntToStr(NULLREGION)
    +#10+'SIMPLEREGION: '+IntToStr(SIMPLEREGION)
    +#10+'COMPLEXREGION: '+IntToStr(COMPLEXREGION)
    +#10+'ERROR: '+IntToStr(ERROR));


  finally
    DeleteObject(RgnA);
    DeleteObject(RgnB);
    DeleteObject(RgnC);
  end;
end;

Als Rückgabewert bekomme ich immer '0' also einen Fehler. Hat jemand eine Ahnung warum?

Gruß
Chris

[Cöster]

Zitat:

Zitat von Chris88

@igel457: Das ist ja nur eine Funktion, um zu testen, ob ein Punkt in einem Polygon liegt. Ich suche aber eine Funktion, welche prüft ob ein Polygon in einem anderen Polygon ist...

Wenn ein Punkt eines Polygons in einem anderen liegt, müssten die beiden Polygone kollidieren, sonst nicht.

[Namenloser]

leider funktioniert das bei folgendem nicht mehr: (siehe anhang?)

[F34r0fTh3D4rk]

und wenn du möchtest dass das schneller geht, solltest du dich mal über Trennungsachsen informieren ;) (Separation Axis)

[Cöster]

Zitat:

Zitat von NamenLozer

leider funktioniert das bei folgendem nicht mehr: (siehe anhang?)

Stimmt :wall:

[negaH]

Delphi-Quellcode:

....
  RgnA := CreatePolygonRgn(TestA,3,Winding);
  RgnB := CreatePolygonRgn(TestB,3,Winding);

  RgnC := CreateRectRgn(0,0,0,0);
....

wenn ich mich richtig erinnere musst du für die Resulatat Region RgnC ein Region Handle erzeugen. CombineRgn() macht dies nicht für dich.

du könntest also auch so arbeiten

Delphi-Quellcode:

  RgnA := CreatePolygonRgn(TestA,3,Winding);
  RgnB := CreatePolygonRgn(TestB,3,Winding);
  try
    case CombineRgn(RgnA, RgnA, RgnB, RGN_AND) of
    end;
  finally
    ...
  end;

sprich inplaced in Region A.

Gruß Hagen

[Chris88]

Ich hab es jetzt so gemacht, wie es in der aller ersten Antwort angedeutet war:

Zitat:

Zitat von Reinhard Kern

2 Polygone kollidieren, wenn sich irgendwelche ihrer Umrandungslinien schneiden. D.h. bei 1 Fünf- und 1 Sechseck 5 x 6 = 30 mal berechnen, ob sich 2 Geradenstücke (nicht Geraden!) schneiden. Ich weiss nicht, ob es eine schnellere Möglichkeit gibt.

Danach muss natürlich noch jeweils ein Punkt gegengeprüft werden.

Hab davor noch eine BoundingBox-Collision geschaltet. Die BoundingBox zu berechnen geht ja einfach. Man geht einfach das Polygon durch und ermittelt MinX, MaxX, MinY, MaxY.

Damit fallen schon mal viele Kollisionen für die relativ Aufwändige Schnittpunktberechnung weg. Was sich im Vergleich zu der Windows API Funktion aber nur einen Bruchteil braucht. Hier hab ich es mit Hilfe von Vektoren gemacht. Die meiner Meinung nach schnellte Funktion.

Nun möchte ich meine Objekte aber noch in einen Quadtree speichern. Da ich mitunter mal > 10000 Objekte habe. Ich kapiere dort allerdings das Vorgehen nur wage. Für einzelne Punkte kann ich mir es noch vorstellen. Aber wie sieht das mit Polygonen aus. Betrachtet man da nur den Startpunkt?
Kann mir jemand mal erklären, wie man bei einem Quadtree seine Knoten anordnet? Oder ein gutes Tutorial hier verlinken. Finde nämlich immer nur ausführliche wissenschaftliche Artikel, welche ich kaum verstehen kann.

Gruß
Chris