Probleme mit der arithmetischen Genauigkeit beim Testen auf den Schnittpunkt zweier Liniensegmente

Question

Ich habe einen Code geschrieben, der den Schnittpunkt zweier Liniensegmente in der Ebene testet. Ich werde dich nicht mit allen Details belästigen.

Der Code benötigt zwei Liniensegmente, die jeweils durch zwei Endpunkte beschrieben werden, und passt dann jedes Segment an eine Linie an, indem a und b in y = a*x + b angepasst werden. Dann findet es den Schnittpunkt der beiden Linien durch x = (b2 - b1)/(a2 - a1). Zuletzt testet es, ob der Schnittpunkt x in den beiden Liniensegmenten enthalten ist.

Der relevante Teil sieht wie folgt aus:

# line parameterization by a = Delta y/Delta x, b = y - a*x 
a1 = (line1.edge2.y - line1.edge1.y)/(line1.edge2.x - line1.edge1.x) 
b1 = line1.edge1.y - a1 * line1.edge1.x 
a2 = (line2.edge2.y - line2.edge1.y)/(line2.edge2.x - line2.edge1.x) 
b2 = line2.edge1.y - a2 * line2.edge1.x 
# The intersection's x 
x = - (b2 - b1)/(a2 - a1) 
# If the intersection x is within the interval of each segment 
# then there is an intersection 
if (isininterval(x, line1.edge1.x, line1.edge2.x) and 
    isininterval(x, line2.edge1.x, line2.edge2.x)): 
    return True 
else: 
    return False 

Der Kürze halber ich eine Menge Tests fallen gelassen besonderen Fällen wie Handhabung, wenn die Kanten sind parallel zueinander (a1==a2), wenn sie auf der gleichen Linie sind, wenn eine Kante mit der Länge 0 ist, wenn die Kante entlang der vertikalen Achse (a dann unendlich wird) usw.

die Funktion ist einfach isininterval

def isininterval(x0, x1, x2): 
    """Tests if x0 is in the interval x1 to x2""" 
    if x1 <= x0 <= x2 or x2 <= x0 <= x1: 
     return True 
    else: 
     return False 

Nun die Frage: Ich finde, dass der Test aufgrund von Rundungsfehlern zu falschen Ergebnissen führt, wenn der Schnittpunkt mit der Segmentkante übereinstimmt.

Zum Beispiel, mit line1 zwischen (0,0) und (3,5) und line2 zwischen (3,5) und (7,1) der resultierende Schnittpunkt x ist 2.9999999999999996, die die falsche Antwort gibt. Sollte gewesen sein 3.

Können Sie bitte eine Lösung vorschlagen?

Answer 1

Dies ist ein Problem/eine Funktion der Fließkommaarithmetik. Es gibt Möglichkeiten, den Fehler zu minimieren, indem Sie bestimmte Anweisungen bestellen, aber am Ende erhalten Sie ungefähre Antworten, weil Sie möglicherweise unendliche Zahlen mit einer endlichen Anzahl von Bits darstellen.

Sie müssen definieren, welche Funktionen Sie erstellen, so dass sie diese Fehler tolerieren. Wenn Sie Ihr Beispiel betrachten, ist der Unterschied zwischen dem "richtigen" Wert und dem, was Sie erhalten haben, in der Reihenfolge 1e-16 - extrem extrem niedrig.

Mit Ungleichheit und vor allem Gleichheit, es ist es wert, die Einschränkungen für genaue/Bissanpassung zu entspannen. Wenn Sie z. B. das x == 3 testen möchten, schreiben Sie dies als abs(x - 3) < EPSILON, wobei EPSILON = 1e-6 oder EPSILON = 1e-9. Grundsätzlich ist der Unterschied zwischen dem, was Sie haben wollen und dem, was Sie haben, kleiner als ein sehr kleiner Wert. Dito, für die Ungleichheit könnten Sie das 3 - EPSILON <= x oder x <= 3 + EPSILON testen.