Punto all'interno di un triangolo
Premesso che non sono (piu') uno studente chiedo un aiuto per un'applicazione pratica, un programma che sto scrivendo.
Visto che sono da parecchi anni lontano dai testi scolastici faccio un po' fatica a ricordare anche formule probabilmente elementari ma che solo ora mi servono per alcuni algoritmi.
In questo caso mi chiedevo come fare a scoprire se un punto dato P(Xp, Yp) e' interno, o meno, alla superfice interna di un triangolo di cui sono noti i tre vertici A, B, C.
Come limitazione, e magari per semplificare la soluzione, diro' che i triangoli pur diversi hanno sempre la caratteristica di avere due lati di eguale lunghezza, infatti o sono triangoli rettangoli, con i due cateti uguali, o triangoli isosceli.
Se qualcuno mi puo' dare qualche indiizio lo ringrazio in anticipo.
Visto che sono da parecchi anni lontano dai testi scolastici faccio un po' fatica a ricordare anche formule probabilmente elementari ma che solo ora mi servono per alcuni algoritmi.
In questo caso mi chiedevo come fare a scoprire se un punto dato P(Xp, Yp) e' interno, o meno, alla superfice interna di un triangolo di cui sono noti i tre vertici A, B, C.
Come limitazione, e magari per semplificare la soluzione, diro' che i triangoli pur diversi hanno sempre la caratteristica di avere due lati di eguale lunghezza, infatti o sono triangoli rettangoli, con i due cateti uguali, o triangoli isosceli.
Se qualcuno mi puo' dare qualche indiizio lo ringrazio in anticipo.
Risposte
Ti ringrazio.
Sono andato a vedere, mi sembra piu' complicato del previsto ma quello che mi ha lasciato perplesso e' il finale della dimostrazione: "However, if it contains three points, the point may lie either in the interior or in the exterior. "
Forse e' il mio inglese che mi tradisce ma letto cosi' sembra che anche ottenendo tre punti non sarei ancora certo del risultato.
Nell'attesa di una risposta avevo provato a risolvere il problema e credevo di esserci riuscito ma a questo punto mi viene il dubbio che l'ho fatta troppo semplice.
Io pensavo di poter usare questo sistema (vedere immagine)
Trovo le due rette parallele agli assi passanti per il punto
che voglio controllare P.
Con due sistemi distinti, trovo i punti di intersezione tra ognuna di queste rette e le rette pasanti per i vertici che formano il triangolo quindi diciamo le rette A-B B-C e A-C
Trovero' due punti di intersezione, per esempio se stiamo lavorando con la retta parallela all'asse delle X, ho chiamato i1 e i2 i due punti.
A questo punto per sapere se il mio punto P e' intermedio lavoro sulle differenze:
Se facendo (Xi1 - Xp) * (Xi2 - Xp) il risultato e' minore di zero, vuol dire che le differenze hanno segno invertito e quindi il valore Xp e' intermedio tra Xi1 e Xi2.
Poi faccio la stessa cosa per la retta parallela all'asse delle Y, e verifico se anche il punto Yp e' intermdio tra Yj1 e Yj2 e se anche questo e' vero il punto P dovrebbe essere interno al triangolo. Mentre invece un altro punto come P2 pur avendo i soliti due punti di intersezione questi non sarebbero intermedi.
A questo punto pero' mi chiedo se non ci sia qualcosa di sbagliato in questo procedimento.
Sono andato a vedere, mi sembra piu' complicato del previsto ma quello che mi ha lasciato perplesso e' il finale della dimostrazione: "However, if it contains three points, the point may lie either in the interior or in the exterior. "
Forse e' il mio inglese che mi tradisce ma letto cosi' sembra che anche ottenendo tre punti non sarei ancora certo del risultato.
Nell'attesa di una risposta avevo provato a risolvere il problema e credevo di esserci riuscito ma a questo punto mi viene il dubbio che l'ho fatta troppo semplice.
Io pensavo di poter usare questo sistema (vedere immagine)
Trovo le due rette parallele agli assi passanti per il punto
che voglio controllare P.
Con due sistemi distinti, trovo i punti di intersezione tra ognuna di queste rette e le rette pasanti per i vertici che formano il triangolo quindi diciamo le rette A-B B-C e A-C
Trovero' due punti di intersezione, per esempio se stiamo lavorando con la retta parallela all'asse delle X, ho chiamato i1 e i2 i due punti.
A questo punto per sapere se il mio punto P e' intermedio lavoro sulle differenze:
Se facendo (Xi1 - Xp) * (Xi2 - Xp) il risultato e' minore di zero, vuol dire che le differenze hanno segno invertito e quindi il valore Xp e' intermedio tra Xi1 e Xi2.
Poi faccio la stessa cosa per la retta parallela all'asse delle Y, e verifico se anche il punto Yp e' intermdio tra Yj1 e Yj2 e se anche questo e' vero il punto P dovrebbe essere interno al triangolo. Mentre invece un altro punto come P2 pur avendo i soliti due punti di intersezione questi non sarebbero intermedi.
A questo punto pero' mi chiedo se non ci sia qualcosa di sbagliato in questo procedimento.
Ciao Paolo, ora devo uscire e non ho tempo di guardare nel dettaglio la tua risposta, però avevo provato il metodo al link che avevo segnalato e mi è sembrato corretto.
Lascia perdere il pezzo iniziale e finale, devi solo calcolare $a$ e $b$ e verificare che siano soddisfatte le tre condizioni: $a>0$, $b>0$, $a+b<1$. Si gioca tutto sulla differenza di coordinate per cui è anche facilmente implementabile.
Ciao
Lascia perdere il pezzo iniziale e finale, devi solo calcolare $a$ e $b$ e verificare che siano soddisfatte le tre condizioni: $a>0$, $b>0$, $a+b<1$. Si gioca tutto sulla differenza di coordinate per cui è anche facilmente implementabile.
Ciao
Beh e' incoraggiante, anche il mio metodo si basa sulla differenza delle coordinate.
Non capisco bene pero' di quella pagina quando parlando di Det (il determinante), pensavo fosse il delta ma leggendo il link specifico Determinant e' venuta fuori una spiegazione che mi sembra molto complicata.
Non capisco bene pero' di quella pagina quando parlando di Det (il determinante), pensavo fosse il delta ma leggendo il link specifico Determinant e' venuta fuori una spiegazione che mi sembra molto complicata.
"Paolone64":
Sono andato a vedere, mi sembra piu' complicato del previsto ma quello che mi ha lasciato perplesso e' il finale della dimostrazione: "However, if it contains three points, the point may lie either in the interior or in the exterior. "
Il problema è che hai letto la frase a metà. La frase completa era
If the convex hull of the triangle vertices plus the point is bounded by four points, the point lies outside the triangle. However, if it contains three points, the point may lie either in the interior or in the exterior.
Si riferisce quindi all'inviluppo convesso dei quattro punti. Questo inviluppo può avere 3 o 4 punti sul bordo. Se ne ha quattro, allora il punto è necessariamente esterno, mentre se ne ha 3, ci sono due casi:
1. il punto è interno e quindi l'inviluppo è uguale al triangolo
2. il triangolo formato da due punti del triangolo più quello che si sta testando contiene il triangolo iniziale e il punto è esterno al triangolo.
Per curiosità, come mai ti serve verificare se un punto è interno ad un triangolo? Se stai ad esempio calcolando l'intersezione tra un raggio (retta) e un triangolo esistono metodi specifici molto migliori.
Applicando il metodo indicato in quel link pervengo a questo algoritmo.
Siano $A=(x_A,y_A)$, $B=(x_B,y_B)$ e $C=(x_C,y_C)$ i tre vertici del triangolo.
Sia $P=(x,y)$ il punto che si vuole verificare se interno al triangolo.
Calcolo:
$D1=(x-x_A)(y_C-y_A)-(y-y_A)(x_C-x_A)$
$D2=(x_A-x)(y_B-y_A)-(y_A-y)(x_B-x_A)$
$D=(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)$
$a=(D1)/D$; $b=(D2)/D$
Se $a>0$ and $b>0$ and $a+b<1$ allora P è interno al triangolo. Altrimenti è esterno (o sul bordo).
Esempio
$A=(1,1)$, $B=(4,2)$ e $C=(2,5)$
$P=(3,2)$
$D1=7$; $D2=1$; $D=11$; $a=0.636$; $b=0.091$; il punto è interno.
$P=(1,3)$
$D1=-2$; $D2=6$; $D=11$; $a=-0.182$; $b=0.545$; il punto è esterno.
Siano $A=(x_A,y_A)$, $B=(x_B,y_B)$ e $C=(x_C,y_C)$ i tre vertici del triangolo.
Sia $P=(x,y)$ il punto che si vuole verificare se interno al triangolo.
Calcolo:
$D1=(x-x_A)(y_C-y_A)-(y-y_A)(x_C-x_A)$
$D2=(x_A-x)(y_B-y_A)-(y_A-y)(x_B-x_A)$
$D=(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)$
$a=(D1)/D$; $b=(D2)/D$
Se $a>0$ and $b>0$ and $a+b<1$ allora P è interno al triangolo. Altrimenti è esterno (o sul bordo).
Esempio
$A=(1,1)$, $B=(4,2)$ e $C=(2,5)$
$P=(3,2)$
$D1=7$; $D2=1$; $D=11$; $a=0.636$; $b=0.091$; il punto è interno.
$P=(1,3)$
$D1=-2$; $D2=6$; $D=11$; $a=-0.182$; $b=0.545$; il punto è esterno.
Ti ringrazio molto Cenzo, mi hai sviluppato i calcoli in modo che siano comprensibili subito. Avevo cercato in queste ore di ripassare matrici e vettori (ai miei tempi li avevo studiati) ma cosi' e' molto piu' semplice.
Riguardo al programma si tratta di una patcher library per tomb raider next generation, l'editor dei livelli di tomb raider piu' esattamente.
Nel gioco originale Lara vive in un mondo formato da mattoni di costruzioni formato da cubi di (in proporzione) due metri di lato.
Volevo consentire di usare mattoni piu' piccoli e soprattutto zone sensibili (triggers) che agissero anche solo su porzioni iinferiori del quadrato di base.
Avevo gia' creato striscie e mini quadretti e anche cerchi, ma mi mancavano i triangoli.
In pratica il calcolo in oggetto mi serve per sapere se il pivot di lara e' nel triangolo di attivazione, che puo' variare di volta in volta.
Qui c'e' il mio sito: http://www.TrLevelManager.net/ng.htm
Grazie per il tempo (e fatica) dedicatemi
Paolo
Riguardo al programma si tratta di una patcher library per tomb raider next generation, l'editor dei livelli di tomb raider piu' esattamente.
Nel gioco originale Lara vive in un mondo formato da mattoni di costruzioni formato da cubi di (in proporzione) due metri di lato.
Volevo consentire di usare mattoni piu' piccoli e soprattutto zone sensibili (triggers) che agissero anche solo su porzioni iinferiori del quadrato di base.
Avevo gia' creato striscie e mini quadretti e anche cerchi, ma mi mancavano i triangoli.
In pratica il calcolo in oggetto mi serve per sapere se il pivot di lara e' nel triangolo di attivazione, che puo' variare di volta in volta.
Qui c'e' il mio sito: http://www.TrLevelManager.net/ng.htm
Grazie per il tempo (e fatica) dedicatemi
Paolo
Ricordo di aver giocato Tomb Raider nel lontano '98. Lo trovavo un po' claustrofobico.. preferivo gli adventure della Lucas..
Prego Paolo, buon lavoro!
Ciao
Prego Paolo, buon lavoro!
Ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo