Come si può stabilire se un punto é interno ad un triangolo?
Ho 3 punti:
A(xa,ya);
B(xb,yb);
C(xc,yc);
e un quarto generico X(x,y)
Come faccio a capire se X é interno al triangolo ABC oppure no?
Ho bisogno di un algoritmo semplice da implementare in un software. Vorrei riprodurre su c una funzione di matlab che mi permette, data una serie di punti P(x,y,z), di tracciare una triangolazione e di stimare la z' di un punto X'(x',y').
ciao e grazie
A(xa,ya);
B(xb,yb);
C(xc,yc);
e un quarto generico X(x,y)
Come faccio a capire se X é interno al triangolo ABC oppure no?
Ho bisogno di un algoritmo semplice da implementare in un software. Vorrei riprodurre su c una funzione di matlab che mi permette, data una serie di punti P(x,y,z), di tracciare una triangolazione e di stimare la z' di un punto X'(x',y').
ciao e grazie
Risposte
Innanzitutto, devi decidere l'orientazione dei vertici.
Supponiamo che \(A\), \(B\) e \(C\) siano etichettati in senso antiorario e che \(A\) sia il vertice più in basso e più a sinistra.
[Se non sei in questa situazione, riordina e rietichetta i vertici.]
A questo punto puoi scrivere le equazioni delle rette passanti per \(A\) e \(B\), per \(B\) e \(C\), per \(C\) ed \(A\) (l'ordine dei verici è importante); chiamale \(r_{A,B}\), \(r_{B,C}\) ed \(r_{C,A}\); le loro equazioni sono, rispettivamente:
\[
\begin{split}
r_{A,B} &:\ -(y_B-y_A)\, (x-x_B)+(x_B-x_A)\, (y-y_B)=0,\\
r_{B,C} &:\ -(y_C-y_B)\, (x-x_C)+(x_C-x_B)\, (y-y_C)=0,\\
r_{C,A} &:\ -(y_A-y_C)\, (x-x_A)+(x_A-x_C)\, (y-y_A)=0
\end{split}
\]
ed è facile verificare che il triangolo chiuso di vertici \(A,B,C\), chiamalo \(\mathcal{T}(A,B,C)\), è l'insieme dei punti \(X=(x,y)\) tali che:
\[
\tag{1} \begin{cases}
-(y_B-y_A)\, (x-x_B)+(x_B-x_A)\, (y-y_B) \geq 0\\
-(y_C-y_B)\, (x-x_C)+(x_C-x_B)\, (y-y_C)\geq 0\\
-(y_A-y_C)\, (x-x_A)+(x_A-x_C)\, (y-y_A)\geq 0
\end{cases}
\]
Quindi \(X\in \mathcal{T}(A,B,C)\) se e solo se le coordinate di \(X\) soddisfano le (1).
Il triangolo aperto di vertici \(A,B,C\), chiamalo \(\mathcal{T}^\circ (A,B,C)\), è l'insieme dei punti \(X=(x,y)\) tali che:
\[
\tag{2} \begin{cases}
-(y_B-y_A)\, (x-x_B)+(x_B-x_A)\, (y-y_B) > 0\\
-(y_C-y_B)\, (x-x_C)+(x_C-x_B)\, (y-y_C) > 0\\
-(y_A-y_C)\, (x-x_A)+(x_A-x_C)\, (y-y_A) > 0
\end{cases}
\]
Quindi \(X\in \mathcal{T}^\circ (A,B,C)\) se e solo se le coordinate di \(X\) soddisfano le (2).
Supponiamo che \(A\), \(B\) e \(C\) siano etichettati in senso antiorario e che \(A\) sia il vertice più in basso e più a sinistra.
[Se non sei in questa situazione, riordina e rietichetta i vertici.]
A questo punto puoi scrivere le equazioni delle rette passanti per \(A\) e \(B\), per \(B\) e \(C\), per \(C\) ed \(A\) (l'ordine dei verici è importante); chiamale \(r_{A,B}\), \(r_{B,C}\) ed \(r_{C,A}\); le loro equazioni sono, rispettivamente:
\[
\begin{split}
r_{A,B} &:\ -(y_B-y_A)\, (x-x_B)+(x_B-x_A)\, (y-y_B)=0,\\
r_{B,C} &:\ -(y_C-y_B)\, (x-x_C)+(x_C-x_B)\, (y-y_C)=0,\\
r_{C,A} &:\ -(y_A-y_C)\, (x-x_A)+(x_A-x_C)\, (y-y_A)=0
\end{split}
\]
ed è facile verificare che il triangolo chiuso di vertici \(A,B,C\), chiamalo \(\mathcal{T}(A,B,C)\), è l'insieme dei punti \(X=(x,y)\) tali che:
\[
\tag{1} \begin{cases}
-(y_B-y_A)\, (x-x_B)+(x_B-x_A)\, (y-y_B) \geq 0\\
-(y_C-y_B)\, (x-x_C)+(x_C-x_B)\, (y-y_C)\geq 0\\
-(y_A-y_C)\, (x-x_A)+(x_A-x_C)\, (y-y_A)\geq 0
\end{cases}
\]
Quindi \(X\in \mathcal{T}(A,B,C)\) se e solo se le coordinate di \(X\) soddisfano le (1).
Il triangolo aperto di vertici \(A,B,C\), chiamalo \(\mathcal{T}^\circ (A,B,C)\), è l'insieme dei punti \(X=(x,y)\) tali che:
\[
\tag{2} \begin{cases}
-(y_B-y_A)\, (x-x_B)+(x_B-x_A)\, (y-y_B) > 0\\
-(y_C-y_B)\, (x-x_C)+(x_C-x_B)\, (y-y_C) > 0\\
-(y_A-y_C)\, (x-x_A)+(x_A-x_C)\, (y-y_A) > 0
\end{cases}
\]
Quindi \(X\in \mathcal{T}^\circ (A,B,C)\) se e solo se le coordinate di \(X\) soddisfano le (2).
Grazie mille! Sembra un po' complicato da implementare... non c'é nulla di più immediato?
La somma delle aree dei triangoli $ABX$, $ACX$ e $BCX$ è uguale all'area del triangolo $ABC$ se il punto è interno o al limite sul bordo, viceversa è maggiore.
Può funzionare?
Può funzionare?
In pratica dovrei iscivere in C# la funzione seguente:
ma come al solito l'informazione é nascosta o resa disponibile con grande ritardo e usata per far denaro...
compliementi mondo moderno
F = TriScatteredInterp(X,Y,Z); vettore_Z1 = F(vettore_X1,vettore_Y1);
ma come al solito l'informazione é nascosta o resa disponibile con grande ritardo e usata per far denaro...
compliementi mondo moderno
Scusa balestra_romani non ho capito cosa vuoi dire.
"Palliit":
Scusa balestra_romani non ho capito cosa vuoi dire.
Anche io sono confuso.
P.S: Il tuo metodo non so se sia più rapido di quello di Gugo ma mi piace
[SP (Solo Per)]
le operazioni di gugo, sono un'istanza del problema dell'Inviluppo Convesso.
Se si vuole fare un confronto computazionale immediato, si può prendere l'Algoritmo di Graham, dove avendo già l'insieme convesso (perciò a fine iterazione) si aggiunge un punto $X$ e si richiama la funzione di decisione per sapere se un tale punto fa parte dell'insieme o meno.
[/SP]
le operazioni di gugo, sono un'istanza del problema dell'Inviluppo Convesso.
Se si vuole fare un confronto computazionale immediato, si può prendere l'Algoritmo di Graham, dove avendo già l'insieme convesso (perciò a fine iterazione) si aggiunge un punto $X$ e si richiama la funzione di decisione per sapere se un tale punto fa parte dell'insieme o meno.
[/SP]
In effetti, usando il principio dell'algoritmo di Graham tutto quello che serve è calcolare il segno dell'area con segno dei 4 triangoli.
Grazie dell'apprezzamento, vict85
Qualcuno mi spiega come funziona questo Algoritmo di Graham?
"vict85":
In effetti, usando il principio dell'algoritmo di Graham tutto quello che serve è calcolare il segno dell'area con segno dei 4 triangoli.
la mia era una piccola nota fine a se stessa. Era per dare un'idea meramente computazionale confrontadolo con un algoritmo conosciuto che, se istanziato, compie le stesse operazioni descritte da guggo. La tua idea forse è applicabile ma a dire il vero non ci avevo pensato.
Si può modificare Graham come ho descritto velocemente, tenendo solo conto del passo di backtrack, dove un punto è eliminato se interno/sul bordo (che corrisponde a risposta affermativa del problema di balestra_romani) in caso contrario l'algoritmo continuerebbe, avendo trovato un nuovo punto esterno che sarebbe un'iterazione valida dell'algoritmo, ma risposta negativa per il problema.
La complessità di gugo_algorithm e graham_algorithm penso siano quasi uguali all'incirca $O(3n)$ è tutto praticamente costante.
Se interessa si può modificare Graham basterebbe confrontare cosa compiono le operazioni di:
F = TriScatteredInterp(X,Y,Z); vettore_Z1 = F(vettore_X1,vettore_Y1);
e se la complessità è minore.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo