Kollisionsberechnung von nichtrechtwinkligen QUADS

[Green]

SO ich habe eine mehr oder weniger konkrete Frage:

Und zwar habe ich eine Kollisionsberechnung geschrieben für 2 Rechtecke, also prüfen ob zwei Rechtecke ineinanderliegen (X/Y Breite Höhe)

jetzt ist mein Problem: Wie berechne ich die Kollision von nicht Rechtiwnkligen Flächen (im allgemeinen QUADS)?
also meinetwegen

A1(0,0)
A2(1,0)
A3(2,1)
A4(0,1)

und

B1(3,0)
B2(5,0)
B3(5,1)
B4(4,1)

??
Ich bin momentan total überfragt...

[sirius]

Mein erster Ansatz wäre die Schnittpunkte von den Seiten zu berechnen.

Edit: Ich meine, wenn man jede Seite des einen Viereckes mit jeder Seite des anderen Viereckes nimmt. Dann wüde ich schauen, ob etwas Sinnvolles dabei herauskommt und der Ansatz weiter verfolgt werden kann.

[Green]

Hm ich glaube damit gewinne ich nix:

wenn ich jetzt was weiss ich A1A2 und B1B2 Schneiden lasse, dann berechne ich den Schnittpunkt und dann muss ich prüfen ob dieser innerhalb des QUADS liegen.
Gleiches Problem wie vorher...

Weil es reicht ja zu wissen das keine der Ecken A1-4 sich in B befindet, und keine der Ecken B1-4 sich in A befindet um eine Kollision auszuschliessen...

[sirius]

Ja klar, das wäre nur ein min-max-Vergleich um zu wissen, ob ein Geradenschnittpunkt auch ein Streckenschnittpunkt ist.

Wieviel willst du eigentlich dann noch wissen?
Irgendwo hatte ich auch mal einen Algorithmus gesehen um zu prüfen, ob ein Punkt in einer Fläche ist.

btw: Windows hat diese ganzen Algorithmen mit Flächen auch implementiert. Musst nur die Regions nutzen.

[Green]

Zitat von sirius:

btw: Windows hat diese ganzen Algorithmen mit Flächen auch implementiert. Musst nur die Regions nutzen.

Regions? noch nie gehört...
wie geht das? geht das auch mit OpenGL oder wie funktionieren die??

[sirius]

Suche mal im Win-SDK nach CreateRegion (CreatePolygonRgn) und CombineRegion (CombineRGN)

[Green]

Zitat von sirius:

Suche mal im Win-SDK nach CreateRegion (CreatePolygonRgn) und CombineRegion (CombineRGN)

Win-SDK? was is das denn?
jetz bin ich föllig überfragt...

[sirius]

Das ist du in deiner Hilfe drin. Es ist halt nur nicht der Delphi-Teil der Hilfe, sondern der Windows-Teil. Die funktionen sind ja auch nicht von Delphi sondern von Windows.

Du kannst das ganze dir auch online anschauen. vielleicht findest du ja auch noch schönere Funktionen, wie "Point in Region"

[Medium]

Es gibt Testverfahren die Aussagen darüber treffen, ob ein Punkt in einem Polygon liegt oder nicht (hier in der DP gabs da einzwei mal was zu). Wenn du nun für jeden Punkt eines Polygons ausschließen kannst, dass er nicht innerhalb des 2. liegt und umgekehrt, hast du gewonnen. Sogar für n-Ecke zu gebrauchen.

Hmm, Edith flüstert mir gerade, dass sie sich dennoch überschneiden könnten. Im Zweifel wäre dann wirklich das sinnvollste, wenn man alle Strecken miteinander schneidet, oder mit Regions dran geht.