computazionale geometria, tetraedro firmato il volume

Question

Non sono sicuro se questo è il posto giusto per chiedere, ma qui va ...

Versione corta: Sto cercando di calcolare l'orientamento di un triangolo un piano, formato dall'intersezione di 3 spigoli, senza calcolare esplicitamente i punti di intersezione.

Versione lunga: Ho bisogno di triangolare un PSLG su un triangolo in 3D. I vertici del PSLG sono definiti dalle intersezioni di segmenti di linea con il piano attraverso il triangolo e sono garantiti da trovarsi all'interno del triangolo. Supponendo che avessi i punti di intersezione, potrei proiettare in 2D e utilizzare un test point-line-side (o area con segno triangolare) per determinare l'orientamento di un triangolo tra 3 punti di intersezione.

Il problema è che non è possibile calcolare in modo esplicito i punti di intersezione a causa dell'errore a virgola mobile che si accumula quando trovo l'intersezione del piano di linea. Per capire se i segmenti di linea colpiscono il triangolo in primo luogo, sto usando alcuni predicati geometrici robusti disponibili liberamente, che danno il segno del volume di un tetraedro, o in modo equivalente a quale lato di un piano si trova un punto. Posso determinare se i punti finali del segmento di linea si trovano su lati opposti del piano attraverso il triangolo, quindi formare un tetraedro tra il segmento di linea e ciascun bordo del triangolo per determinare se il punto di intersezione si trova all'interno del triangolo.

Poiché non è possibile calcolare in modo esplicito i punti di intersezione, mi chiedo se esiste un modo per esprimere lo stesso calcolo dell'orientamento 2D in 3D utilizzando solo i punti originali. Se ci sono 3 bordi che colpiscono il triangolo che mi dà 9 punti in totale con cui giocare. Supponendo che ciò che sto chiedendo sia anche possibile (usando solo i test di orientamento 3D), allora suppongo che avrò bisogno di formare un sottoinsieme di tutti i possibili tetraedri tra quei 9 punti. Sto avendo difficoltà anche a visualizzare questo, per non parlare di distillarlo in una formula o un codice. Non riesco nemmeno a google perché non so quale possa essere la terminologia standard del settore per questo tipo di problema.

Qualche idea su come procedere? Grazie. Forse dovrei chiedere anche a MathOverflow ...

EDIT: Dopo aver letto alcuni dei commenti, una cosa che mi viene in mente ... Forse se potessi montare tetraedri non sovrapposti tra i 3 segmenti di linea, quindi l'orientamento di qualcuno di quelli che hanno attraversato l'aereo sarebbe la risposta che sto cercando. Oltre a quando i bordi racchiudono un semplice prisma triangolare, non sono sicuro che anche questo sottotema sia risolvibile.

MODIFICA: L'immagine richiesta.

Answer 1

Rispondo a entrambi su MO & SO, espandendo i commenti che ho fatto su MO.

La mia sensazione è che nessun trucco computazionale con volumi tetraedri firmati eviterà i problemi di precisione che sono la vostra principale preoccupazione. Questo perché, se si hanno segmenti strettamente attorcigliati, l'orientamento del triangolo dipende dal posizionamento preciso del piano di taglio.
[immagine rimossa; vedere qui]
Nell'esempio precedente, il piano superiore attraversa i segmenti nell'ordine (a, b, c) [ccw dall'alto]: (rosso, blu, verde), mentre il piano inferiore croci nel l'ordine inverso (c, b, a): (verde, blu, rosso). L'altezza del piano di taglio potrebbe essere determinata dall'ultimo bit di precisione.

Di conseguenza, penso che abbia senso andare avanti e calcolare i punti di intersezione nel piano di taglio, usando una precisione tale da rendere il calcolo esatto. Se le coordinate del punto finale del segmento e i coefficienti del piano hanno L bit di precisione, è necessario solo un piccolo aumento del fattore costante. Anche se non sono sicuro di quale sia esattamente questo fattore, è piccolo, forse 4. Non è necessario ad esempio, L bit, perché il calcolo sta risolvendo equazioni lineari. Quindi non ci sarà un'esplosione nella precisione richiesta per calcolare esattamente questo.

Buona fortuna!

(mi è stato impedito dal pubblicare l'immagine chiarire perché non ho la reputazione Vedere invece il MO answer..)

Edit: Non vedi la risposta MO, ma ecco l'immagine:

Answer 2

vorrei scrivere le equazioni vettoriali simboliche, si sa, con il punto e croce prodotti, per trovare la normale del triangolo intersezione. Quindi, il segno del prodotto punto di questa normale con il triangolo iniziale dà l'orientamento. Quindi finalmente puoi esprimerlo in un segno di forma (F (p1, ..., p9)), dove p1 a p9 sono i tuoi punti e F() è una brutta formula che include punti e prodotti incrociati di differenze (pi-pj) . Non so se questo può essere fatto più semplice, ma questo approccio generale fa il lavoro.

Answer 3

Come ho capito, ci sono tre linee che intersecano il piano e si desidera calcolare l'orientamento del triangolo formato dai punti di intersezione, senza calcolare i punti di intersezione stessi?

Se è così: voi avete un aereo

 
N·(x - x0) = 0 

e sei punti ...

 
l1a, l1b, l2a, l2b, l3a, l3b 

... formando tre linee

 
l1 = l1a + t(l1b - l1a) 
l2 = l2a + u(l2b - l2a) 
l3 = l3a + v(l3b - l3a) 

I punti di intersezione di queste linee al piano verificano a specifici valori di t, u, v, che chiamerò t _i, u _i, v _i

 
N·(l1a + ti(l1b - l1a) - x0) = 0 

     N·(x0 - l1a) 
ti = ---------------- 
     N·(l1b - l1a) 
(similarly for ui, vi) 

allora i punti specifici di intersezione sono

 
intersect1 = l1a + ti(l1b - l1a) 
intersect2 = l2a + ui(l2b - l2a) 
intersect3 = l3a + vi(l3b - l3a) 

Infine, l'orientamento del triangolo è

 
orientation = direction of (intersect2 - intersect1)x(intersect3 - intersect1) 

(x è cross-product) lavorare a ritroso di collegare i valori, e avrete un'equazione per l'orientamento basata solo su N , x e i sei punti.

Answer 4

Chiamiamo tuo triangolo vertici T[0], T[1], T[2], e gli endpoint del primo segmento di linea sono L[0] e L[1], il secondo è L[2] e L[3], e il terzo è L[4] e L[5]. Immagino tu voglia una funzione

int Orient(Pt3 T[3], Pt3 L[6]); // index L by L[2*i+j], i=0..2, j=0..1 

che restituisce 1 se le intersezioni hanno lo stesso orientamento del triangolo e -1 altrimenti. Il risultato dovrebbe essere simmetrico con interscambio di valori j, antisimmetrico con interscambio di valori i e indici T. Finché puoi calcolare una quantità con queste simmetrie, è tutto ciò che ti serve.

Cerchiamo

Sign(Product(Orient3D(T[i],T[i+1],L[2*i+0],L[2*i+1]) * -Orient3D(T[i],T[i+1],L[2*i+1],L[2*i+0])), i=0..2)) 

cui il prodotto deve essere ripreso permutazione ciclica degli indici (modulo 3). Credo che questo abbia tutte le proprietà di simmetria richieste. Orient3D è il test di orientamento del piano in quattro punti di Shewchuk, che presumo tu stia utilizzando.