Kollision zweier 2dim Polygonen.

[Cöster]

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 von NamenLozer:

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

Stimmt

[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 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