Algorytm gesucht: überprüfen, ob eine strecke einen poly schneidet
-
Habe die koordinaten der endpunkte der Strecke und der Punkte des Poly. (Alles 2D)
Ich habe einen eigenen Algorytm geschrieben, doch sollte die strecke 2 punkte des Poly verbinden, ohne das Poly selbst zu schneiden (beispiel kommt) - gehts nicht.
Ich suche nach einen funktionierenden Algorytm, die Zeit drängt...
http://basic.cybton.com/temp/uups.JPG <<== das Beispiel
-
Hallo,
um solche Überprüfungen zu machen musst du zuerst dein Polygon konvex machen.
Dann ist es einfach. Sonst nicht. Gibt es überhaupt eine Möglichkeit praktikabel zu überprüfen ob eine Linie ein konkaves Polygon schneidet?
-
Sry, was heisst konvex?
(Meine Geometriekentnisse: 10kl gym
)
-
Kurz gesagt: Du darfst keine Wölbungen nach innen haben.
Viele Engines können überhaupt nur konvexe Gebilde rendern. konkave müssen in zwei konvexe aufgeteilt werden. (zB: HL-Engine)
MfG SideWinder
-
wenn eine der strecken die das poly bilden geschnitten wird, dann wird das poly geschnitten. schnittpunkt von zwei strecken sollte doch trivial sein bzw google....
-
rapso schrieb:
wenn eine der strecken die das poly bilden geschnitten wird, dann wird das poly geschnitten. schnittpunkt von zwei strecken sollte doch trivial sein bzw google....
Ja, das habe ich. Das Hacken - die Strecke darf die Ecken des Poly Berühren, und das heißt schneiden. Ich habe bestimmte "sicherung" gemacht, damit das nicht so passiert, die nimmt aber an, dass wenn eine strecke zwei ecken des Poly schneidet, schneidet sie den Poly, und dass ist wie man im Beispiel sieht nicht so.
Viele Engines können überhaupt nur konvexe Gebilde rendern. konkave müssen in zwei konvexe aufgeteilt werden. (zB: HL-Engine)
Dies ist eine Wettbewerbsaufgabe - ich darf keine Third-Party sachen benutzen und habe auch kein Engine mit den ganzen Funktionen.
Kannst du mir bitte einen link zu so einen Algorytmus geben, damit ich das implementieren kann?
-
verkürze die strecken des oplys leicht vor dem testen... kann zwar immer noch zu fehlern führen, dürfte aber zu 99% laufen.
-
rapso schrieb:
verkürze die strecken des oplys leicht vor dem testen... kann zwar immer noch zu fehlern führen, dürfte aber zu 99% laufen.
Naja, aber daß problem das isch vorgeführt habe wäre immer noch da.
Es ist so, dass ich stattdessen einfach die seiten aus der prüfung ausließ, ein ende deren die strecke berührt. Wenn aber die Strecke von einer Ecke bis zum anderen durch den Poly durchleuft - gibts ein problem.
Deswegen habe ich vorher angenommen, dass wen zwei ecken berührt sind, ist der Poly "durchstrahlt" - ist aber jetzt nicht so.Ich habe eine Idee!!!!!!!!!!!
Ich werde, wenn zwei Ecken berührt sind, eine weitere prüfung machen: ich werde zwischen jeden zwei Ecken des Polys eine Strecke ziehen, und dann Prüfen, ob welche davon durchscnitten (nicht berührt!) wurden.
Das dürfte funkzionieren! Aber braucht einen mörderischen Performance wenn der Poly groß ist .... Naja, ist ja nur wettbewerb ^^
-
die aufgabe is aber cool
und wenns dann läuft siehts richtig gut aus, wie der typ gucken kann (sofern es um den bwinf geht )
-
Meine Theorie hat nicht funkzioniert... standing by for suggestions..
-
Lass mich dein Problem noch einmal formulieren um sicher zu sein, dass wir über das gleiche sprechen : Du hast ein Polygon und eine Linie. Es soll festgestellt werden ob die Linie das Poly schneidet, das heist unendlich viele Punkte gemeinsam haben. (Sollte eine Seite des Polys auf der Linie liegen so wird es als Schnitt gezählt.)
Trivial ist es wie bereits erwähnt bei einen konvexem Poly. Hier braucht man nur die Schnittpunkte mit den Seiten des Polys zu betrachten. Keiner => Kein Schnitt, Einer => Tangete (= kein Schnitt), Zwei => Schnitt, Unendlich (= Seite liegt auf der Linie) => Kein Schnitt.
Jedes Dreieck ist konvex. Wenn wir also das Poly in Dreiecke zerlegen haben wir ein triviales Problem.
Jedes Poly kann in ein Dreieck und ein Poly mit einem Eck weniger zerlegt werden.
Dies gibt uns ein Algo in linearer Zeit.
