Polygon-Line Collision Detection

Question

Ich versuche eine Formel zu finden, um festzustellen, ob eine Linie ein Polygon schneidet. Ich habe es versucht, aber der Code unten funktioniert nicht richtig.

bool Check_Collision(float x1,float y1, float x2, float y2) 
{ 
     int j=MyPolyVector.size()-1; 
     for (int i=0;i<MyPolyVector.size();i++) 
     { 
       float x3=MyPolyVector[i].X; 
       float x4=MyPolyVector[j].X; 
       float y3=MyPolyVector[i].Y; 
       float y4=MyPolyVector[j].Y; 

       float denom= ((y4-y3)*(x2-x1))-((x4-x3)*(y2-y1)); 
       float ua = (((x4-x3)*(y1-y3))-((y4-y3)*(x1-x3)))/denom; 
       float ub = (((x2-x1)*(y1-y3))-((y2-y1)*(x1-x3)))/denom; 
       j=i; 

       if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) return true; 
     } 
     return false; 
} 

Answer 1

Ich denke, diese Verbindung für Sie interessant sein könnten, das Know-how zu erhalten: Point in Polygon Problem

Es gibt auch eine verknüpfte Ressource, für die C-Code: Point in Polygon - C Code

Diese Das Problem wird meistens im OpenGL-Kontext behandelt und die Hauptidee, um dies zu lösen, ist das Zählen der Schnittpunkte des Polygons und jeder geraden Linie, die durch Ihren Punkt zur Überprüfung geht.

Wie viel Geometrie müssen Sie überprüfen, ob ein Punkt in einem Polygon liegt?

PS: Ich habe gerade diesen Beitrag zu diesem Problem :-) Stackoverflow - Point in Polygon

Answer 2

kann ich Sie vorschlagen, einen Blick auf this book und auch für line Kreuzung 2D suchen habe und im Bereich vor Ihrer Berechnung zu prüfen.

Außerdem erfordert Ihr Code eine Division durch Nullprüfung und weitere Überlegungen zu reziproken Linienabmessungen und Toleranzen.

Answer 3

Es sieht so aus, als ob Sie falsche Gleichungen für die Linienüberschneidungen haben. Ich denke, dass die richtigen Gleichungen aufgeführt sind here.

Das heißt, ein guter Ansatz für dieses Problem ist es, zu sehen, ob die Linie eines der Liniensegmente auf dem Polygon schneidet. Um dies zu testen, berechnen Sie den Schnittpunkt für die Linie mit jeder Linie der Polygonkante, und wenn dieser Punkt innerhalb des Segments des Polygons liegt, dann gibt es einen Schnittpunkt (sehen Sie, ob der Punkt innerhalb der durch die Endpunkte des Segments). (Und vielleicht ist das, was Sie versuchen zu tun, aber es ist ein bisschen schwer zu sagen, da Sie keine Erklärung geben.)