schneidet eine Strecke ein Polygon

[Flogo]

Sorry wenn ich hier in die falsche Kategorie gerutscht bin aber ich war mir einfach nicht sicher wo es sonst reinsollte.

Also ich versuche rauszufinden, ob eine Strecke (keine Gerade) ein Polygon schneidet oder nicht. Eigentlich ist das ja nicht so schwer, wenn man jede Linie des Polygons mit der Strecke schneidet und bei einem gefundenen Schnittpunkt abbricht.
Allerdings ergeben sich mehr Probleme als ich erwartet habe:
Die Schnittpunkte können zum Beispiel durch Zufall direkt in einem Eckpunkt des Polygons landen. Diese müssen natürlich auch als Schnittpunkte gezählt werden, weil sonst zum Beispiel die Diagonale in einem Rechteck als nicht schneidend gezählt wird.
Andererseits soll in meinem Fall der Start- und Endpunkt der Gerade auch auf der Außenkante oder den Eckpunkten des Polygons liegen dürfen.

Ich hoffe mal ihr versteht mein Problem und könnt mir da auf die Sprünge helfen

[tripleeye]

Wenn du Probleme mit den Eckpunkten hast, wieso prüfst du dann nicht die Sonderfälle (Eckpunkte) zuerst?
Hast du da 2 Schnittpunkte gefunden kannst du bei einem kovexen Polygon sogar schon aufhören zu rechnen, ansonsten prüfst halt die einzelnen Seiten auf Kollision.

[Flogo]

Zitat:

Zitat von tripleeye

Wenn du Probleme mit den Eckpunkten hast, wieso prüfst du dann nicht die Sonderfälle (Eckpunkte) zuerst?

Wie genau meinst du das? Sorry ich steh grad voll aufm Schlauch! Ich hab mir ne Formel gebastelt, die checkt ob zwei Strecken sich schneiden oder nicht. Da sind entweder die Eckpunkte mit dabei oder nicht. aber die sollten ja einmal dabei sein und einmal nicht.

Zitat:

Zitat von tripleeye

Hast du da 2 Schnittpunkte gefunden kannst du bei einem kovexen Polygon sogar schon aufhören zu rechnen, ansonsten prüfst halt die einzelnen Seiten auf Kollision.

Mir würde es schon reichen einen Schnittpunkt zu finden weil die Strecke ja dann auf jeden Fall das Polygon schneidet. Ich will ja nicht wissen, ob ein Punkt in einem Polygon liegt oder außerhalb, sondern ob eine Strecke das Polygon schneidet. Oder hab ich da irgendwas falsch verstanden?

[Jens Schumann]

Hallo,
in diesem Buch steht die Lösung:

Sedgewick

Das Buch ist sehr empfehlenswert. Die Algorithmen werden in einer Art Pascal 5.0 Syntax erklärt

[Flogo]

Danke das ist nett gemeint aber ich kanns mir grad überhaupt nicht leisten wegen dieser Frage ein Buch für 50 € zu kaufen. (Ok gut ich könnte das Buch sicher auch nochmal für andere Sachen benutzen, aber trotzdem sind mir die 50 € grad zuviel)

Wenn du die Antwort schon in dem Buch gefunden hast, wie wäre es dann mit einem kleinen Tipp?
Ist das ein spezieller Algorithmus? bekomme ich einen Namen zum googeln?
Oder gibts dabei einen Trick den ich bis jetzt übersehen hab?

[tripleeye]

Also, Um zu prüfen, ob eine Strecke eine Diagonale ist, musst du ja nur die Anfangspunkte der Strecke auf Übereinstimmung mit den Eckpunkten des Polygons testen. So nach dem Motto:

Delphi-Quellcode:

// S(Xs;Ys) ist Startpunkt der Strecke
// P(Xp;Yp) ist Eckpunkt des Polygons
if (Xs=Xp) and (Ys=Yp) 
 then ;// Strecke startet auf Eckpunkt
// für Endpunkt und andere Ecken analog verfahren!

um das mit den doppelten Schnittpunkten zu prüfen, erstellst du einen Record, der die beiden Schnittpunkte aufnehmen kann, ist der neu gefunden schon drin, entfällt er.

Ich hoffe ich hab dich richtig verstanden

[Flogo]

Das mit der Diagonalen war nur ein Beispiel. Die Eckpunkte des Polygons (das übringens nicht unbedingt konvex ist) können auch an einer anderen Stelle der Strecke liegen, damit dieses Problem entsteht.

Ich versuchs mal anders/ausführlicher zu erklären:

Ich habe ein Polygon und eine Strecke.
Um zu testen ob die Strecke das Polygon schneidet, prüfe ich so lange ob sich eine Linie des Polygons mit der Strecke schneidet, bis ich einen Schnittpunkt finde. (Also bis eine der Linien die Strecke schneidet ;-) ).
Das Problem entsteht, wenn der Endpunkt einer Linie auf der anderen liegt.
Einerseits soll dieser Punkt nicht als Schnittpunkt gezählt werden, damit die Strecke auf der Kante oder einem Eckpunkt des Polygons starten kann. Das soll erlaubt sein, solange sie nicht weiter hinten das Polygon schneidet.
Andererseits soll dieser Punkt doch als Schnittpunkt gezählt werden, weil sonst eine Strecke, die direkt durch einen Eckpunkt des Polygons geht als nicht schneidend angesehen wird (weil in diesem Fall mit den beiden Polygonkanten rechts und links von diesem Punkt kein Schnittpunkt gefunden wird)

Oh ich seh grad ich hab fast das gleiche geschrieben wie am Anfang... naja vielleicht hilfts ja trotzdem

[tripleeye]

die schnittpunkte berechnest du einfach alle erst. dann nimmst du dir deine problemfälle vor, die ja immer dann auftreten, wenn die strecke einen eckpunkt schneidet (oder auf einer seite beginnt oder endet).
ich denke, man könnte dein Problem lösen, indem man dann jeder Seite des Polygons einen richtwinkel zuordnet. dies kann man z.b. dadurch erreichen, indem man den anstieg m der seite nach (y2-y1)/(x2-x1) berechnet und davon arctan bildet. falls es eine senkrechte seite ist, muss man halt manuell 90° zuweisen. zum ergebnis addiert man 90° oder zieht sie ab, je nachdem in welche richtung die fläche eingeschlossen wird.
nun hatt man eine art richtungsvektor der senkrecht auf der seite steht und in die richtung zeigt, wo die fläche des polygons eingeschlossen wird.
für die strecke macht man genau das gleiche, bis auf den schritt mit den +-90°. wichtig ist, dabei immer m nach (yend-ystart)/(xend-xstart) zu berechnen.
nun hat man 2 winkel. jetzt prüft man: ist [(winkel der strecke) > (winkel der seite)-90°] und [(winkel der strecke) < (winkel der seite)+90°], dann zeigt die strecke in das polygon hinein und du hast einen schnittpunkt. wenn nicht, hast du den gewünschten sonderfall.

falls du das halbwegs logisch findest, könnte ich dir noch skizzen posten, falls es aber unlogisch sein sollte, oder du es so verstehst, spar ich mir die mühe.

[nailor]

wenn du bei google nach kombinationen aus

line / ray / polygon / collision / intersection / distance

suchst, wirst du einige hochoptimierte algorithmen (viele in c(++)) aus der spiele-entwicklung stossen.

[Flogo]

Erstmal muss ich mich für die lange Pause hier entschuldigen.
Es hat etwas gedauert bis ich gemerkt habe, dass ich hier die falsche Frage gestellt habe. Es hat sich herausgestellt, dass der Fehler in meiner Testanwendung an einer anderen Funktion lag. In dieser Funktion sollte der Punkt gesucht werden, der einem bestimmten Punkt am nächsten liegt und innerhalb des Polygons liegt. Dabei sind leider (durch Trunc/Round) auch Punkte rausgekommen, die auf der Linie und leicht außerhalb lagen.
Alle Kolisionstests, die ich mit diesen Punkten gemacht habe, sind natürlich negativ ausgefallen. Wenn diese Funktion nur Punkte liefern würde, die wirklich innerhalb des Polygons liegen, kann man die Schnittpunktfunktion so bauen, dass sie auch Punkte auf der Linie als Schnittpunkte akzeptiert.
Trotzdem vielen Dank für eure Tipps :thumb:

Ich melde mich dann wenn ich an der anderen Funktion verzweifelt und kurz vorm Aufgeben bin ;-)