Was ist falsch an meinem Schnittpunktprüfalgorithmus?

Question

Ich weiß, dass es viele Seiten gibt, die erklären, wie man nach einer Schnittmenge von zwei Zeilen sucht, aber ich finde es absolut langweilig, einfach Code für solch eine einfache mathematische Aufgabe zu kopieren und einzufügen. Je mehr es mich frustriert, dass ich meinen Code nicht zur Arbeit bekommen kann. Ich kenne Fragen mit "Was ist falsch in meinem Code?" sind dumm, aber ich weiß nicht, was zur Hölle ist falsch mit meiner Mathematik/Code, auch mein Code ist schön dokumentiert (außer der zugegebenermaßen schlechten Variablennamen), also denke ich, es sollte jemand sein, der an der Mathematik dahinter interessiert ist :

bool segment::checkforIntersection(QPointF a, QPointF b) { //line 1: a+bx, line 2: c+dx, note that a and c are called offset and bx and dx are called gradients in this code 
QPointF bx = b-a; 
double firstGradient = bx.y()/bx.x(); //gradient of line 1 
//now we have to calculate the offset of line 1: we have b from a+bx. Since QPointF a is on that line, it is: 
//a + b * a.x = a.y with a as free variable, which yields a = a.y - b*a.x. 
//One could also use the second point b for this calculation. 
double firstOffset = a.y() - firstGradient * a.x(); 
double secondGradient, secondOffset; 
for (int i = 0; i < poscount-3; i++) { //we dont check with the last line, because that could be the same line, as the one that emited intersection checking 
    QPointF c = pos[i]; 
    QPointF d = pos[i+1]; 
    QPointF dx = d-c; 
    secondGradient = dx.y()/dx.x(); //same formula as above 
    secondOffset = c.y() - secondGradient * c.x(); 
    //a+bx=c+dx <=> a-c = (d-b)x <=> (a-c)/(d-b) = x 
    double x = (firstOffset - secondOffset)/(secondGradient - firstGradient); 
    //we have to check, if those lines intersect with a x \in [a.x,b.x] and x \in [c.x,d.x]. If this is the case, we have a collision 
    if (x >= a.x() && x <= b.x() && x >= c.x() && x <= d.x()) { 
     return true; 
    } 
} 
return false; 
} 

Was dies tut, hat es 4 Punkte a, b, c, d (Zeile 1: a - b, Zeile 2: c - d) haben (die for-Schleife ignorieren), die ein absoluter x- und y-Wert. Zuerst berechnet es die Steigung der Linien durch Berechnung von Delta/Delta. Dann berechnet er den Offset, indem er den Punkt a (bzw. c) auf den Linien verwendet. Auf diese Weise transformierten wir die 4 Punkte in eine mathematische Darstellung dieser Linien als Gleichung a + bx, während ax von 0 bedeutet, dass wir am ersten Punkt (a/c) sind und ax von 1 bedeutet, dass wir uns am zweiten Punkt befinden (b/d). Als nächstes berechnen wir den Schnittpunkt dieser beiden Linien (Grundalgebra). Danach überprüfen wir, ob der X-Wert der Kreuzung gültig ist. Nach meinem Verständnis ist das alles korrekt. Sieht jemand den Fehler?

Dies wurde empirisch als inkorrekt überprüft. Der Code gibt keine falschen Positive (sagt, es gibt einen Schnittpunkt, wenn es nicht gibt), aber es gibt falsche Negative (sagt, es gibt keinen Schnittpunkt, wenn es tatsächlich ist). Wenn es heißt, dass es eine Kreuzung gibt, ist es richtig, aber wenn es sagt, dass es keine Kreuzung gibt, kann man meinem Algorithmus nicht immer glauben.

Auch hier habe ich online nachgesehen, aber die Algorithmen sind anders (mit ein paar Orientierungstricks und etwas), ich wollte nur meinen eigenen Algorithmus erstellen, ich wäre so froh, wenn jemand helfen könnte. :)

Edit: Hier ist ein minimal reproduzierbar nicht funktionierendes Beispiel, diesmal ohne Qt aber mit nur C++:

#include <iostream> 
#include <math.h> 

using namespace std; 
class Point { 
private: 
    double xval, yval; 
public: 
    // Constructor uses default arguments to allow calling with zero, one, 
    // or two values. 
    Point(double x = 0.0, double y = 0.0) { 
     xval = x; 
     yval = y; 
    } 

    // Extractors. 
    double x() { return xval; } 
    double y() { return yval; } 

    Point sub(Point b) 
    { 
     return Point(xval - b.xval, yval - b.yval); 
    } 
}; 

bool checkforIntersection(Point a, Point b, Point c, Point d) { //line 1: a+bx, line 2: c+dx, note that a and c are called offset and bx and dx are called gradients in this code 
    Point bx = b.sub(a); 
    double firstGradient = bx.y()/bx.x(); //gradient of line 1 
    //now we have to calculate the offset of line 1: we have b from a+bx. Since Point a is on that line, it is: 
    //a + b * a.x = a.y with a as free variable, which yields a = a.y - b*a.x. 
    //One could also use the second point b for this calculation. 
    double firstOffset = a.y() - firstGradient * a.x(); 
    double secondGradient, secondOffset; 
    Point dx = d.sub(c); 
    secondGradient = dx.y()/dx.x(); //same formula as above 
    secondOffset = c.y() - secondGradient * c.x(); 
    //a+bx=c+dx <=> a-c = (d-b)x <=> (a-c)/(d-b) = x 
    double x = (firstOffset - secondOffset)/(secondGradient - firstGradient); 
    //we have to check, if those lines intersect with a x \in [a.x,b.x] and x \in [c.x,d.x]. If this is the case, we have a collision 
    if (x >= a.x() && x <= b.x() && x >= c.x() && x <= d.x()) { 
     return true; 
    } 
    return false; 
} 

int main(int argc, char const *argv[]) { 
    if (checkforIntersection(Point(310.374,835.171),Point(290.434,802.354), Point(333.847,807.232), Point(301.03,827.172)) == true) { 
     cout << "These lines do intersect so I should be printed out\n"; 
    } else { 
     cout << "The algorithm does not work, so instead I do get printed out\n"; 
    } 
    return 0; 
} 

So wie zB ich die Punkte nahmen ~ (310.835) - (290.802), und (333,807) - (301,827). Diese Linien schneiden sich:

\documentclass[crop,tikz]{standalone} 
\begin{document} 
\begin{tikzpicture}[x=.1cm,y=.1cm] 
\draw (310,835) -- (290,802); 
\draw (333,807) -- (301,827); 
\end{tikzpicture} 
\end{document} 

Proof of intersection jedoch, wenn die oben C++ Code ausgeführt wird, heißt es, dass sie sich nicht schneiden

Answer 1

(Sie mir ein Pedant nennen können, aber die Terminologie ist wichtig)

Wenn Sie, wenn die Linie Segmente sehen wollen, dann auf die Parameterdarstellung verlassen schneiden von Ihre beiden Segmente, um das System in den beiden Parametern lösen und sehen, wenn sowohl die Lösung für beiden Parameter fällt in [0,1] Bereich.

Parametric-Darstellung für Segment [a, b], komponentenweise

{x, y}(t) = {(1-t)*ax+t*bx, (1-t)*ay+t*by} mit t im [0,1] Bereich

Quick-Check - bei t=0 Sie bekommen ein, bei t=1 Sie b erhalten, ist der Ausdruck linear in t, also hast du es.

Also, Ihr (a, b) (c, d) Schnitt Problem wird:

// for some t1 and t2, the x coordinate is the same 
(1-t1)*ax+t*bx=(1-t2)*cx+t2*dx; 
(1-t1)*ay+t*by=(1-t2)*cy+t2*dy; // and so is the y coordinate 

Lösen Sie das System in t1 und t2. Wenn t1 im Bereich [0,1] ist, liegt der Schnittpunkt zwischen a und b, das gleiche gilt für t2 in Bezug auf c und d.

Es wird als Übung für den Leser die Studie von dem, was Auswirkungen auf das System über den folgenden Bedingungen haben und was für einen robusten Algorithmus Kontrollen sollten durchgeführt werden:

1. Segment Entartung - übereinstimmend endet für eines oder beide Segmente
2. kollineare Segmente mit nicht-void Überlappung. Insbesondere dann, wenn es ein einziger Punkt der Überlappung ist (erforderlich, wird dieser Punkt eines des Endes sein)
3. kollinearen Segmente ohne Überlappung
4. parallele Segmente

Answer 2

Zuerst berechnet er die Steigung der Geraden durch die Berechnung DeltaY/deltax.

Und was passiert, wenn deltax sehr nahe bei Null ist?

Schauen Sie, was Sie tun, ist, sich schlecht konditionierten Situationen auszusetzen - immer Divisionen Angst und gerade Vergleich mit 0.0, wenn es darum geht, Computational Geometry.

Alternative:

1. zwei Linien schneiden, wenn sie nicht
2. zwei unterschiedliche Linien parallel parallel sind, wenn ihre Definition Vektoren, die ein Null-Kreuzprodukt hat.

Kreuz-Produkt Ihrer (a,b) x (c,d) = (ax-bx)*(cy-dy)-(ay-by)*(cx-dx) - wenn diese nahe genug an Null ist, für alle praktischen Zwecke gibt es keine Überschneidung zwischen den Linien (die Kreuzung so weit weg ist es spielt keine Rolle).

Nun, das bleibt, was gesagt werden: „sind jene Linie distinct“

• es muss eine sein Testen Sie, bevor Sie das Cross-Produkt berechnen. Noch mehr müssen Sie degenerierte Fälle behandeln (eine oder beide der Linien werden zu einem Punkt durch übereinstimmende Enden reduziert - wie a==b und/oder c==d)
• der Test "nah genug zu Null" ist mehrdeutig, wenn Sie nicht ' t normalisieren Sie Ihre Definitionsvektoren - stellen Sie sich einen 1 Lichtsekundenlangen Vektor vor, der die erste Linie und einen 1 Parsek-Längenvektor für die andere definiert (Welcher Test für 'Nähe zu Null' sollten Sie in diesem Fall verwenden?)
  Um die beiden Vektoren zu normalisieren , wenden Sie einfach eine Abteilung an ... ^{(eine Abteilung, die Sie sagen? Ich zittere bereits mit der Furcht)} ... mmm .. Ich sagte, das resultierende Kreuzprodukt mit hypot(ax-bx, ay-by)*hypot(cx-dx,cy-dy) zu teilen (sehen Sie, warum die Entartungsfälle müssen im Voraus behandelt werden?)
• nach der Normalisierung Noch einmal, was wäre ein guter "Nähe zu Null" -Test für das resultierende Kreuzprodukt? Nun, ich denke, ich kann die Analyse für eine weitere Stunde fortsetzen (zB wie weit der Schnittpunkt im Vergleich zum Ausmaß des Polygons {a, b, c, d} wäre), aber ... seit dem Kreuz - Produkt von zwei einheitlichen Vektoren (nach Normalisierung) ist sin(angle-between-versors), können Sie Ihren gesunden Menschenverstand verwenden und sagen: "Wenn der Winkel weniger als 1 Grad ist, wird dies gut genug sein, um die beiden Linien parallel zu betrachten? Nein? Was etwa 1 arcsecond?“