Denkansätze Ideen für etwas (Koordinatenberechnung, Schnittmengen)

[Zwaps]

Hiho.

Also es geht hier um ein PHP/MySQL Problem, an dem ich derzeit arbeite.
Stellt euch eine Art Karte vor, 2D erstmal, auf der man einen Punkt hat (X/Y)

Nun gibt es auch Objekte/Polygone, die in ihrem Aussehen unbegrenzt sein sollen. Ich dachte derzeit daran, Punkte in einer Datenbank zu speichern.
Anhand dieser Punkte erhält man halt dann ein Objekt mit soundso viel Ecken etc.

Bis dato kein Problem. Jetzt müsste ich aber berechnen, ob der Punkt A innerhalb / ausserhalb dieses Objektes liegt.
Es gibt da einige Ansatzweisen, aber da ich mit PHP arbeite und es recht schnell halten will, würde ich mal eure Meinung einfragen. Viele haben sicher schonmal ähnliches gemacht in der Spieleprogrammierung etc. Es wäre auch nur eine einfache Kollisionsdetektion.

Was nicht geht ist Gebiete in Rechtecke einzufassen und dann zu prüfen, es muss also schon pixelgenau sein. Da wir aber nur einen Punkt und ein paar Linien haben, dürfte es doch eine mathematische Lösung geben, denke ich.

 

[EnimaN]

das musst du schon etwas genauer beschreiben, damit eine gute optimierung möglich ist - es wäre zum beispiel interessant ob die mengen, die du mit deinem polygonzug beschreiben willst immer konvex oder hin und wieder auch kokav sein können... überhautp solltest du das problem wohl etwas weiter beschreiben

 

[4GT~DosX]

Die "in Rechtecke einfassen Methode" bietet sich an, da sie das Programm stark beschleunigt, wenn große Anzahlen an Punkten überprüft werden müssen. Viele könnten gleich von vornherein ausgeschlossen werden.
Einfach einzubauen ist's auch:

Nimm höchsten Punkt des Objekts, schaue ob Punkt < höchster Objekt Punkt
Nimm tiefsten Punkt des Objekts, schaue ob Punkt > tiefster Objekt Punkt
Das ganze dann noch mit rechts und links...
Wenn der Punkt alle Bedingungen erfüllt muss anschließend eben Pixelgenau überprüft werden, andernfalls spart man sich die Pxielgenaue- und aufwendigere Arbeitsweise.

Das pixelgenaue wird dann schwieriger: ich denke mal man braucht die am Nähesten liegenden Eckpunke des Polygons und dann Geometrie

 

[Zwaps]

Da es sich immer nur um einen Punkt handelt, werde ich wohl folgendes Versuchen:

1. Annäherung: Ist das Objekt überhaupt in der Nähe
2. Annäherung: Berechnung eines Radius um einen Mittelpunkt/Vergleich und einer Seite
3. Bestimmung welche 2 Punkte am nächsten liegen.
4. Linie ziehen
5. Kollisionsdetektion

 

[EnimaN]

3. Bestimmung welche 2 Punkte am nächsten liegen.

das reicht aber nicht aus - die linie zwischen den zwei nächsten punkten muss doch nichts mit dem zu untersuchenden punkt zu tun haben...

 

[Koestritzer]

was mir dazu so einfällt:
1. bounting rectangles/circles wenn es viele polygone sind, das beschleunigt das ganze enorm. du testest dann erstmal gegen die bounding rects, wenn es zu einer kollision kommt machst du es genau.

2. zum algo selber: die frage ist wann liegt ein punkt innerhalb eines polygons?

dazu folgender grundgedanke: ein polygon besteht aus einer anzahl punkten, es kann im oder gegen den uhrzeigersinn beschrieben werden. wenn man die punkte durchläuft und zwischen ihnen einge gerade konstruiert liegt der punkt innerhalb des polygons wenn er bei allen geraden auf der innenseite liegt (wenn man davon ausgeht dass man es im uhrzeigersinn durchläuft wäre das die rechte seite).

man muss also die geradengleichung so umformen dass man feststellen kann ob der punkt auf der linken seite einer geraden liegt.

 

[Zwaps]

Wie gesagt, ich habe mich gefragt ob man wirklich _alle_ Geraden abgleichen muss. Im Prinzip reicht es doch, einfach die Gerade zu nehmen, die am nächsten zum Punkt liegt, oder?

 

[4GT~DosX]

Die Frage ist in diesem Falle wie du den Abstand vom Punkt zur Geraden berechnest.
Mir kommt in diesem Zusammenhang in den Sinn, dass der Abstand Gerade <-> Punkt mit dem Lot der Gerade gemessen wurde.
Folgendes Beispiel:

Die rein logisch am nähesten liegende Gerade ist eine der beiden rechts oben. Wie willst du nun aber berechnen welche davon näher liegt? Mit dem Lot der Geraden erreicht man den Punkt nicht.

 

[Koestritzer]

du musst alle geraden checken, sonst wird das nix bei dem ansatz

 

[Zwaps]

Gibt es da keinen anderen Ansatz, irgendwas tolles geometrisches?

 

[Koestritzer]

keine ahnung, das war nur das was mir gerade so durch den kopf gegangen ist bei dem problem. google ist dein freund, schau dort mal nach.

alternativ kannste dir ja mal diverse open source 3d engines anschauen und die implementation der ray bzw polygon klassen untersuchen und dir halt anschauen wie die es machen. musst das ganze dann halt nur noch auf 2d umsetzen.

 

[Syzygy]

Original geschrieben von 4GT~DosX
Die Frage ist in diesem Falle wie du den Abstand vom Punkt zur Geraden berechnest.
Mir kommt in diesem Zusammenhang in den Sinn, dass der Abstand Gerade <-> Punkt mit dem Lot der Gerade gemessen wurde.
Folgendes Beispiel:

Die rein logisch am nähesten liegende Gerade ist eine der beiden rechts oben. Wie willst du nun aber berechnen welche davon näher liegt? Mit dem Lot der Geraden erreicht man den Punkt nicht.

du erreichst den schon, nur liegt das Lot nicht zwischen den beiden gegebenen Objektpunkten. Man findet aber die Gerade welche am nähesten am Punkt vorbeigeht durch diese "Verlängerung"... nur obs ihm was nutzt ist die andere Frage...

 

[Ricky Spanish]

also mir würden da jetzt zwei möglichkeiten einfallen, dass (relativ) einfach und schnell zu lösen:
mit nem sweepline algorithmus oder mit einem segment-baum, wobei sich für das problem mit mehreren polygonen eher der sweep anbieten würde. den segment baum würde ich dann nehmen, wenn es lediglich ein polygon zu betrachten gibt...
hoffe das hilft dir n bissl weiter.

gruß
m.a.k.