Linie - kurvige Linie Kollisonserkennung bei Polygonen

[Marti]

Hallo.

Ich würde ganz gerne etwas tiefer in die Kollisionserkennung einsteigen. Wenn ich nach der Methode mit den Polygonen hergehe, würde das wie folgt aussehen:

1. Umfasse Dein Objekt so genau wie möglich mit Linien. Entweder manuell oder die Cleveren schreiben einen eigenen Algorythmus, der das erledigt(ich mach es manuell). Die Linien bilden mein Polygon-Objekt, dass Java bereit stellt.

2. Die vorläufige Kollisionserkennung erfolgt dann dadurch, dass ich mit dem Polygon-Objekt eine Überschneidung mit der BB anderer Polygone durchführe. Wenn das true zurückliefert, erfolgt eine genaue Kollisionserkennung, in der eine Überschneidung der Linien der jeweiligen Polygone überprüft wird.
Dazu könnte ich a: Das Line-Objekt verwendene, dass mir bequem schon die Methode mitliefert ob sie sich mit einer anderen Linie überschneidet,
oder b:ich schreibe meine eigene line-line-Kollisionserkennung.

Ich hoffe, dass ich das einigermaßen überblicke.

Nun meine Frage: Gekrümmte Linien werden üblicherweise auch in ein Vieleck gepresst. Was ist aber, wenn meine gekrümmte Linie z.B. eine Parabel darstellt und sich dementsprechend mathematisch elegant beschreien läßt über eine funktion. Dann müßte ich ja nur noch die Funktion meiner Linie einsetzen und prüfen ob die Schnittpunkte in dem betreffenden Intervall liegen. Könnte man doch so machen, oder?

Grüße

Marti

 

[Marco13]

Erstmal vorneweg: Ich personlich finde die Polygon-Klasse aus AWT die ... (*kurz überleg*) joa, die grausligste Klasse in der ganzen Standard-API (mit einigem Abstand folgen die GridBugConstraints ). Public Arrays aus ints, getrennt nach x und y :autsch: :noe: ... Ein GeneralPath (EDIT: bzw. Path2D) ist da etwas "sauberer", aber welche Klasse für (ggf. eigene, und ggf. hoch-spezifische) Kollisionserkennungen geeignet sind, sollte man sich überlegen...

Das mit der Parabel stimmt an sich. Für "Spezialfälle" kann man das so machen. Man wird zwar selten eine "unendlich große" Parabel haben, aber grundsätzlich funktionieren würde das. Vor- und Nachteile muss man auch hier abwägen: Man kann dann mit einigem (mathematischen- und Implementierungs-) Aufwand eine Methode schreiben, die Linie-Parabel-Schnitte erkennt, aber je nachdem, wie di umliegende Infrastruktur aussehen soll, muss derjenige, der auf Kollisionen testet, dann eben wissen, dass das eine eine Parabel und das andere eine Linie ist. Und der Schnitt Parabel-Parabel würde schon nicht mehr (so einfach) funktionieren, d.h. dafür müßte man die Parabeln dann wieder auf die "Basisform" einer Folge von Liniensegmenten runterbrechen.

 

[Marti]

Danke für den Hinweis auf Path2d. Mein Objekt könnte im Grunde einfach von dieser Klasse erben und mir stünde dann alles nötige zur Verfügung.
Hmm... ich verstehe den Einwand

Man wird zwar selten eine "unendlich große" Parabel haben

nicht so recht. Vielleicht gehe ich etwas naiv an die Sache dran, aber ich habe entweder keine Berührung, oder einen Berührungspunkt oder 2 Schnittpunkte. Wenn ich z.B. 2 Schnittpunkte habe, müßte ich nur noch prüfen, ob die in einem für mich relevanten Intervall liegen.

Aber: Path2D bietet mir auch die Möglichkeit Bezierkurven zu zeichnen und dazu finde ich jetzt zumindest wieder reichlich Lesestoff im Internet bez. Kollisionsprüfungen. Ich glaub das ist es.

Nachtrag: Die Kurve wird dann auch wieder nur in Teilsegmente zerlegt, naja dann kann ich das auch gleich so zeichnen.

 

[Marco13]

Mein Objekt könnte im Grunde einfach von dieser Klasse erben und mir stünde dann alles nötige zur Verfügung.

Oder eine Form von Komposition - die ist der Vererbung häufig vorzuziehen.

Hmm... ich verstehe den Einwand nicht so recht. Vielleicht gehe ich etwas naiv an die Sache dran, aber ich habe entweder keine Berührung, oder einen Berührungspunkt oder 2 Schnittpunkte. Wenn ich z.B. 2 Schnittpunkte habe, müßte ich nur noch prüfen, ob die in einem für mich relevanten Intervall liegen.

Ne, stimmt schon: Wenn man eine Parabel mit einer Geraden schneidet, hat man keine Berührung, oder einen Berührungs/Schnittpunkt, oder zwei. Der Rest ist abhängig davon, ob es um "Parabelsegmente" oder Geradensegmente geht...

QUOTE
Aber: Path2D bietet mir auch die Möglichkeit Bezierkurven zu zeichnen und dazu finde ich jetzt zumindest wieder reichlich Lesestoff im Internet bez. Kollisionsprüfungen. Ich glaub das ist es.

Nachtrag: Die Kurve wird dann auch wieder nur in Teilsegmente zerlegt, naja dann kann ich das auch gleich so zeichnen.

Sie wird in Teilsegmente zerlegt, um sie zeichnen zu können - aber man kann auch rein Formal auf der "formelmäßigen" Darstellung rumrechnen. Im Vergleich zu Schnitt Linie-Linie oder Linie-Parabel könnte das aber kompliziert werden...

 

[Steev]

Ich glaube nicht, dass du das manuelle machen willst Das kann recht komplex werden. Ich habe mal etwas ähnliches geschrieben, wo ich als Kurven bézier-Kurven verwende, die ich rekursiv mit einer Genauigkeit von n zerlege. Optional könnte man natürlich Splines verwenden, was die ganze Geschichte aber unnötig Komplex macht...

SourceForge.net Repository - [rpgenesis] Index of /trunk/src/RPGenesis/com/rpgenesis/geom

Gruß
Steev

 

[Marti]

Oder eine Form von Komposition - die ist der Vererbung häufig vorzuziehen

.
Ja richtig.
@Steev: Danke für den Link bzw. die bereitgestellte Bibliothek. Sehr ausführlich kommentiert. Ich glaub damit hat sich im Grunde schon jede Frage für mich erledigt. Selbst die rekursive Funktion für die Bézierkurve habe ich verstanden.

 

[Marti]

Ich glaube nicht, dass du das manuelle machen willst

Ich galube Du hast Recht. Mal unabhängig von den Kurven, wäre es natürlich schöner einen Algorythmus zu haben, zumal ich meine Objekte evtl. auch nochmal neu zeichne, bzw. neue hinzu kommen.
Gibt es einen Algorythmus der mir ein Polygon für ein Objekt liefert?
Mein Ansatz wäre folgender :
Ich suche nach dem Punkt der am weitesten links/oben liegt, und scanne dann nach rechts meinen Rand ab. Also all jene Pixel, die einen unsichtbaren nachbarn haben. Diese Randpixel schiebe ich in Array und berechne ob sie auf einer Linie liegen. Gibt es Abweichungen, setze ich einen Knotenpunkt (wobei man da evtl. noch einen Toleranzwert nehmen könnte um z.B. eine 2-Pixel-Einkerbung zu vernachlässigen.)
Den Knotenpunkt schiebe ich dann in meine Punktearray und das Spiel beginnt von neuem.
Naja theoretisch keine große Sache.Theoretisch.
Kurze Erläuterung: Ich geh jetzt natürlich schon von einem fertig gemalten Bild aus, dass ich in ein Polygon fassen möchte.

 

[Steev]

Wenn ich dich richtig verstehe dann willst du ein Bild in eine Vektorgrafik konvertieren?
Das ist nicht unbedingt so einfach. Ich habe so etwas mal anhand einer abgeänderten Form der Odd-Parity-Regel gemacht. Allerdings hat so etwas fast immer den Nachteil, dass man zu viele Vektorenpunkte erzeugt und damit unnötig Rechenleistung verschenkt. Daher bin ich dann hingegangen und habe mir ein kleines Programm geschrieben, mit dem ich mit der Maus ein Polygon erstellen kann und ein Hintergrund laden kann. Dann habe ich mir das Polygon mithilfe der Serialisierung abgespeichert und in mein Programm geladen. Der Vorteil dabei ist, dass man immer selbst Einfluss darauf hat, wie das Polygon aufgebaut ist. Eine Rastergrafik in ein Polygon zu konvertieren hat (fast) immer den Nachteil, dass man relativ schnell an Grafiken kommt, wo das nicht richtig oder garnicht funktioniert.

Gruß
Steev

 

[Marti]

Ah, verstehe. Du lädst Dir Dein Bild als Blaupause rein und zeichnest seine Umrandung ab.
Gut, die andere Methode hätte ich vermutlich auch nicht hinbekommen.