Numerische Stabilität von Punkt-in-Dreieck-Test mit baryzentrischen Koordinaten

Question

Während ich verschiedene Methoden für Punkt-in-Dreieck-Tests (2D-Fall) untersuchte, fand ich, dass die Methode, die baryzentrische Koordinaten verwendet, die am häufigsten verwendete ist. Here ist eine StackOverflow-Antwort, die es erklärt.

Warum ist diese Methode am meisten bevorzugt? Es hat wahrscheinlich mit weniger Berechnungen zu tun, aber was ist mit der numerischen Stabilität? Ist dieser Algorithmus besser geeignet als beispielsweise die "side side" -Technik für Fälle, in denen der Punkt besonders nahe der Grenze liegt?

Answer 1

Wenn Sie lösen es:

p = p0 + (p1 - p0) * s + (p2 - p0) * t 
s = <0.0,1.0> 
t = <0.0,1.0> 
s+t<=1.0 

Während SOLWING dieses System:

p.a = p0.a + (p1.a - p0.a) * s + (p2.a - p0.a) * t 
p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t 
---------------------------------------------------- 

Sie haben zwei algebraische Optionen:

I. t = (p.a - p0.a - (p1.a - p0.a) * s)/(p2.a - p0.a) 
II. p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t 
---------------------------------------------------- 
II. p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * (p.a - p0.a - (p1.a - p0.a) * s)/(p2.a - p0.a) 
II. s = (p.b-p0.b)/((p1.b-p0.b) + ((p2.b-p0.b)*(p.a-p0.a-(p1.a-p0.a)/(p2.a-p0.a))) 
... 

Und:

I. s = (p.a - p0.a - (p2.a - p0.a) * t)/(p1.a - p0.a) 
II. p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t 
---------------------------------------------------- 
... 

Welches gibt Ihnen 2 algebraische Lösungsoptionen. Um Stabilität zu gewährleisten, sollten Sie mit genügend großen Größen teilen. Sie sollten also die Achsen (a,b ->x,y) wählen und die Reihenfolge so festlegen, dass Sie nicht durch Null- oder kleine Magnitudenzahlen dividieren. Ordnung, Punkt um, so dass die inverse Matrix axises berechenbar ist

Um dies zu vermeiden Sie Matrix-Ansatz

p.a = p0.a + (p1.a - p0.a) * s + (p2.a - p0.a) * t 
p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t 
-------------------------------------------------- 
|p.a| | (p1.a - p0.a) , (p2.a - p0.a) , p0.a | | s | 
|p.b| = | (p1.b - p0.b) , (p2.b - p0.b) , p0.b | * | t | 
| 1 | |  0  ,  0  ,  1 | | 1 | 
-------------------------------------------------------- 
| s |   | (p1.a - p0.a) , (p2.a - p0.a) , p0.a | | p.a | 
| t | = inverse | (p1.b - p0.b) , (p2.b - p0.b) , p0.b | * | p.b | 
| 1 |   |  0  ,  0  , 1 | | 1 | 
------------------------------------------------------------------ 

Sie für mehr Optionen haben auch hier nutzen können. Wenn Sie einen subdeterminanten Ansatz für eine inverse Matrixlösung verwenden, dann sollte nur der letzte Teilungsschritt eine Rolle spielen. So können Sie die Aufträge auswählen, bis Sie eine Determinante ungleich Null haben.