-
.Il quesito: dati due punti P1 e P2 sul piano xy distinti, dato un terzo punto A, stabilire se quest'ultimo si trova a "destra" o a "sinistra" della retta su cui giacciono i punti precedenti. 
L'algoritmo del riconoscimento della posizione di un punto rispetto ad un lato vedrete è banalissimo, ma rappresenta uno dei mattoncini base su cui si basano la maggior parte degli algoritmi che risolvono questioni riguardanti i poligoni.
In realtà nel caso specifico, il concetto di destra e di sinistra è ampiamente relativo dato che nel caso di segmento orizzontale potremmo parlare di "sopra" o "sotto" lo stesso.
Un concetto assoluto è invece il fatto che la retta su cui giace il segmento dato divide l'intero piano in tre parti (tutti i punti che stanno da una parte, tutti i punti che stanno dalla parte opposta e la terza parte il luogo dei punti che stanno sulla retta).
Occorre pertanto stabilire qualcosa di assoluto che ci possa far distinguere una parte dall'altra.
Il criterio è: il segno del prodoto vettoriale tra i due vettori orientati P1-P2 e P1-A
Se tale prodotto è positivo (e non ci interessa nemmeno il modulo del prodotto) allora A si trova nel semispazio positivo altrimenti nel semispazio negativo. Se invece il prodotto vettoriale è nullo allora il punto giace sulla retta.
Edited by afazio - 5/9/2012, 19:48
. -
.
dati:
P1(x1;Y1)
P2(x2,Y2)
A (x,Y)
il prodotto vettoriale P1P2 x P1A vale:
modulo: |P1P2 * P1A *sen(alfa)|
in cui alfa è l'angolo orientato ottenuto ruotando il primo vettore facendolo coincidere col secondo. Angoli antiorari positivi.
segno: coincidente col segno del vettore risultante secondo la famosa regola della mano destra. Il segno sarà positivo se il vettore ottenuto dal prodotto vettoriale è concorde con l'asse positivo delle z, altrimenti è negativo.
Ma senza per forza dover fare ricorso alla regola della mano destra, di difficile implementazione in un codice, è sufficiente guardare il segno assunto dal sen(alfa). Questo coicide col segno del prodotto vettoriale.
Indicando quindi con:
alfa1 l'angolo formato dal primo vettore rispetto ad un asse generico (che ovviamente faremo coincidere con l'asse x)
alfa2 l'angolo formato dal secondo vettore rispetto ad llo stesso asse generico
Avremo:
alfa = alfa2-alfa1
e siamo pertanto in grado di determinarci il segno del seno che rappresenta il risultato cercato.
Se poi stabiliamo che per noi sinistra significa "positivo" e che destra significa "negativo", possiamo dare la risposta al quesito iniziale.
Gli angoli alfa2 ed alfa1 li determiniamo con la funzione Arctan, opportunamente ampliata per ottenere l'angolo nel corretto quadrante.
Edited by afazio - 31/8/2012, 16:23. -
.
Scriviamo prima la funzione che mi restituisce l'angolo formato da un segmento rispetto all'asse delle x ma non ridotto.
I dati di ingresso della funzione sono le coordinate del punto di inizio del segmento e quelle del punto di fine.CODICEFunction arcotangente(X_i As Double, Y_i As Double, X_f As Double, Y_f As Double) As Double
Dim pi As Double
pi = 4 * Atn(1)
If X_i = X_f Then ' in questo caso il segmento è verticale e l'angolo puo essere + o - 90°
arcotangente = Sgn(Y_f - Y_i) * pi / 2
Else
arcotangente = Atn((Y_f - Y_i) / (X_f - X_i))
If (X_f - X_i) < 0 Then arcotangente = arcotangente + pi ' questa formula mi riporta l'angolo nel quadrante giusto.
End If
End Function
Adesso è sufficiente chiamare due volte la funzione precedente, una volta passandogli il segmento P1A ed una seconda volta il segmento P1P2.
Il segno del seno della differenza dei due angoli è la risposta che cerchiamo.
Il risultato sarà:
+1 se il punto si trova a "sinistra"
-1 se si trova a "destra"
0 se il punto giace sulla rettaCODICEPublic Function DestraSinistra(xi As Double, yi As Double, _
xf As Double, yf As Double, _
x As Double, y As Double) As Variant
DestraSinistra = Sgn(Sin(arcotangente(xi, yi, x, y) - arcotangente(xi, yi, xf, yf)))
End Function
è tutto. -
.
Ho predisposto un foglio excel di prova:
https://www.box.com/s/vsiksign4t95u5q47n8y
. -
Ncenzo .
User deleted
Ciao
non era più facile così...
scrivo l'equazione della retta passante per due punti: y=f(x)
Controllo se l'ordinata Yp del punto sia minore o maggiore di f(xp) cioè:
Yp > f(xp) allora è sopra o a sinistra
Yp< f(xp) allora è sotto o a destra
altrimenti è sulla retta (impostata una certa tolleranza).
Che dici?. -
.Ciao
non era più facile così...
scrivo l'equazione della retta passante per due punti: y=f(x)
Controllo se l'ordinata Yp del punto sia minore o maggiore di f(xp) cioè:
Yp > f(xp) allora è sopra o a sinistra
Yp< f(xp) allora è sotto o a destra
altrimenti è sulla retta (impostata una certa tolleranza).
Che dici?
Puo' funzionare, ma devi ancora prevedere altro controllo e cioè quello della retta verticale. Questo controllo ti farebbe aumentare il numero delle istruzioni.
Inoltre devi ancora chiederti cosa accade se il punto P1 si trova al di sopra e a destra del punto P2? Cioè se scambi la posizione tra P1 e P2; l'equazione della retta resta sempre quella, il valore assunto dalla funzione in p è sempre lo stesso, ma avendo variato il verso del vettore P1P2 cambia anche il concetto di destra e sinistra di sopra o sotto.
In sostanza per poter fissare il concetto di destra o di sinistra nel caso che ho proposto, dovremo proprio pensare alla nostra destra o sinistra ponendoci in piedi sul punto iniziale (P1) e guardando verso il secondo punto (P2), chiedendoci dove si trova il punto A rispetto a noi.
Se scambi P1 con P2 vedi che quello che era destra nel caso precedente, diventa sinistra dopo lo scambio. Questo non lo coglieresti con il metodo che proponi.
Come ho solo accennato prima, l'algoritmo della posizione di un punto rispetto al lato, se visto fine a se stesso è praticamente inutile, ma se visto all'interno di un algoritmo finalizzato a stabilire se un poligono è concavo o convesso diventa importante. Spero di poter trattare in un prossimo post proprio l'algoritmo "is Convex".
Comunque grazie. Intervento gradito.
Edited by afazio - 6/9/2012, 11:54. -
.
IL procedimento che ho descritto prima, si basa sul calcolo degli angoli formati dai vettori rispetto ad un asse di riferimento ed alla successiva estrazione del segno del seno.
Questo implica dover trattare bene la funzione arcotangente. Vi ricordo che le funzioni Atn o Arctg restituiscono l'angolo ridotto al 1° e 4° e cioè da -90 a +90 e, in ogni caso, va in errore per valori dell'angolo pari a +-90°.
Mi sono però ricordato che c'è una maniera di superare la questione degli angoli ricorrendo al prodotto vettoriale condotto con il calcolo matriciale.
Il prodotto vettore tra due vettori V1 e V2 posti sul piano xy ed aventi rispettivamente componenti (V1x;V1y) e (V2x;V2y) è dato dal determinate della matrice formata dalle componenti dei due vettori. il segno del determinate stablisce se il prodotto è concorde o discorde all'asse Z (è sottointeso che si adotta un sistema di riferimento levogiro).
IL codice si semplifica in:CODICEPublic Function SegnoProdottoVettore(xi As Double, yi As Double, _
xf As Double, yf As Double, _
x As Double, y As Double) As Variant
SegnoProdottoVettore = Sgn((xf - xi) * (y - yi) - (yf - yi) * (x - xi))
End Function
E' chiaro che se abbiamo necessita di un calcolo particolare sul foglio in cui ci serve sapere il segno del prodotto vettoriale, la funzione scritta, pursempre utilizzabile, risulta essere quasi inutile potendo scrivere nella cella direttamente la formula:
=SEGNO(C13*D14-D13*C14)
in cui nelle celle C13, D14, D13, D14 abbiamo preventivamente collocato le componenti del vettore (o le differenze tra le coordinate), ma se abbiamo necessità di determinarci quel segno nell'ambito di un ciclo che processa innumerevoli punti (come potrebbe essere quello per la determinazione del minimo poligono convesso di una decina di migliaia di punti), questa funzione diventa importantissima.
Edited by afazio - 14/10/2012, 15:25. -
.
Verificare se tre punti sono allineati
La funzione che ho scritto sopra puo servire anche per verificare se tre punti sono allineati o no. Conoscere se dati tre punti questi sono allineati puo servire all'interno di altri problemi come per esempio quello della determinazione del centro e del raggio di un cerchio passante per tre punti.
. -
rinny .
User deleted
esiste una matrice che mi permetta di vedere se il secondo vettore si trova a destra o a sinistra del primo ma per vettori in 3d?
Altrimenti come si potrebbe procedere per effettuare questo controllo in 3D?. -
.esiste una matrice che mi permetta di vedere se il secondo vettore si trova a destra o a sinistra del primo ma per vettori in 3d?
Altrimenti come si potrebbe procedere per effettuare questo controllo in 3D?
Si. E' sempre il segno del prodotto vettoriale tra i due vettori che in 3D hanno generalmente tre componenti.
Appena ho un po' di tempo lo illustro.. -
.
Non riesco a trovare la pagina del prof. Bourke che trattava della questione. Penso che a causa della ristrutturazione del sito alcune pagine siano state tolte. Riporto quel che ricordo.
Nel caso del prodotto vettore tra due vettori a e b giacenti nel piano XY, sappiamo che il risultato è ancora un vettore ortogonale al piano XY e quindi disposto secondo la direzione Z.
Se il risultato del prodotto vettore è concorde con in verso di Z allora diremo che il vettore b si trova a sinistra di a altrimenti si trova a destra.
Tutto questo è valido in un sistema di riferimento levogiro.
Nel caso più generale di prodotto tra due vettori nello spazio (aventi un punto in comune e quindi complanari), il risultato è ancora un vettore ma adesso ortogonale al piano che contiene i due vettori e quindi possiede tre componenti secondo i tre assi x, y e z.
In questo caso per poter parlare di punto a destra o a sinistra di un segmento occorre fissare un sistema di riferimento levogiro sul piano che contiene i due vettori ( o nel caso che ci interessa, punto e segmento orientato) avente origine sul punto in comune dei due vettori ed asse delle x' coincidente col primo vettore. Naturalmente gli assi y' e z' saranno fissati dalla condizione che y' deve stare sul piano che contiene i due vettori e z' tale che x'y'z' sia levogiro.
Dati quindi i tre punti A, B e C, per cui si vuole sapere se il punto C si trova a destra o a sinistra del segmento orientato AB, occorre per prima cosa ricavarsi le componenti della normale n al piano che contiene i tre punti A, B e C, quindi trovarsi le componenti del prodotto vettore R = AB X AC e confrontare se i segni di queste componenti sono concordi o discordi ai segni delle componenti della normale al piano.
Semplice no?
Spero di poter spiegare il procedimento con un esempio numerico illustrando anche il procedimento da seguire per ricavarsi sia le componenti della normale al piano che le componenti del prodotto vettoriale.
L'alternativa, a mio parere parecchio più complessa dal punto di vista computazionale, è quella di ricavarsi le coordinate dei tre punti nel sistema di riferimento del piano operando quindi una trasformazione di assi nello spazio 3D. Con questa trasformazione sparisce la coordinata Z' dei punti e si ricade nel caso piano.
Post Scriptum: ho dimenticato ad evidenziare il fatto che i moduli delle componenti del risultato del prodotto vettore in genere non sono uguali ai moduli delle componenti della normale ma in genere sono dei multipli di comune costante K. Basta quindi ricavarsi questa costante K come rapporto tra le corrispondenti componenti del vettore R e del vettore n. Se K è positivo allora si parla di punto a sinistra, altrimenti di punto a destra.. -
.
Siano dati i tre punti:
A( 3 ; 1; 1 )
B( 2 ; -3; -1 )
C( 1 ; -1; 4 )
(spero di non aver preso per caso tre punti allineati, caso mai lo scopriremo svolgendo l'esercizio)
Si chiede di sapere se il punto C si trova a sinistra o a destra del segmento orientato AB secondo la convenzione espressa nel post precedente.
Sia aX + bY +cZ +d = 0 l'equazione del piano π passante per i tre punti dati
Le componenti della normale n a π (e di qualsiasi altro piano parallelo) altro non sono che i coefficienti a, b e c, dell'equazione del piano, quindi:
n = (a ; b; c)
I coefficienti dell'equazione del piano si ricavano ponendo nullo il determinante che segue:
in cui x, y, z sono le coordinate del punto corrente appartenente al piano π mentre le rimanenti righe sono composte dalle coordinate dei tre punti A, B e C
La quarta colonna della matrice è formata da tutti coefficienti unitari.
Sostituendo i valori delle coordinate dei punti, avremo:
Ricavando il determinate della matrice, ordinando e raccogliendo i fattori con x, quelli con y, quelli con z, ed i termini noti, otteniamo i coefficienti a, b, c, d dell'equazione del piano passante per i tre punti dati.
Scriveremo l'equazione in maniera tale che il primo coefficiente sia sempre positivo (eventualmente moltiplichiamo il tutto per -1).
E con questo avremo note le componenti del vettore n normale al piano
Calcoliamo il determinate prendendo i termini della prima riga e moltiplicandoli per i determinanti dei minori complementari (attenzione al segno che è dato da (-1)(r+c) ), abbiamo l'equazione:
Da questa è facile vedere che i coefficienti dell'equazione (e quindi le componenti della normale al piano) sono i determinanti delle seguenti matrici:
In questa ultima immagine ho omesso di scrivere la parola det (e purtroppo anche i segni).
Edited by afazio - 17/8/2013, 20:53. -
.
Dati i due vettori u e v 
Il prodotto vettore w=uxv è dato dal determinante della matrice che segue
in cui i, j, k rappresentano i versori degli assi del sistema di riferimento.
Le componenti del vettore w sono pertanto:
A questo punto per capire se il punto C si trova a destra o a sinistra del segmento orientato AB basta confrontare il segno del determinante della matrice
che ci fornisce la componente secondo x del vettore w con il segno del coefficiente a dell'equazione del piano che contiene i tre punti.
Ma dato che il coefficiente a è preso sempre positivamente, basta vedere il segno del determinante della matrice
E' tutto. Vediamo di applicare quanto detto all'esempio che ho proposto.. -
.
Dati i tre punti:
A( 3 ; 1; 1 )
B( 2 ; -3; -1)
C( 1 ; -1; 4 )
vediamo se il punto C si trova a destra o a sinistra del segmento orientato AB
indico con u il vettore AB , con v il vettore AC e con w il prodotto vettoriale uxv
u = AB = [ (2-3) ; (-3-1) ; (-1-1) ] = [ -1 ; -4 ; -2]
v = AC = [ (1-3) ; (-1-1) ; ( 4-1) ] = [ -2 ; -2 ; 3]
wx = -4*3-((-2)*(-2)) = -16
Il punto C si trova a destra del segmento orientato A-->B
Chi ne ha voglia determini i coefficienti dell'equazione del piano.
E' tutto.. -
rinny .
User deleted
Ti ringrazio per le risposte dettagliate. L'equazione del piano dovrebbe essere
det x y z 1
3 1 1 1
2 -3 -1 1
1 -1 4 1
1 1 1 1 1
a= -3 -1 1 -3 -1
-1 4 1 -1 4
a= -1 + -1 + -12 - ( 1 + 4 + -3 ) = -16
3 1 1 3 1
b= 2 -1 1 2 -1
1 4 1 1 4
b= -3 + 1 + 8 - ( -1 + 12 + 2 ) = 7
3 1 1 3 1
c= 2 -3 1 2 -3
1 -1 1 1 -1
c= -9 + 1 + -2 - ( -3 + -3 + 2 ) = -6
3 1 1 3 1
d= 2 -3 -1 2 -3
1 -1 4 1 -1
d= -36 + -1 + -2 - ( -3 + 3 + 8 ) = 47
equazione -16 x 7 y -6 z 47
del piano
il coefficiente della x è negativo quindi vuol dire che nel nostro sistema di riferimento il punto c si trova a sinistra del segmento orientato a->b giusto?
Quello che non ho capito è perchè dobbiamo controllare la componente x per capire se il prodotto vettoriale punta verso l esterno come la normale, non dovremmo controllare il coefficiente z?
nel caso in cui i 3 punti si trovino tutti sull'asse xy ad es:
A=(2,4,0)
B=(4,1,0)
C=(1,1,0)
oppure
A=(4,1,0)
B=(2,4,0)
C=(1,1,0)
avremo sia il coefficiente x del prodotto vettoriale sia il coefficiente x della normale pari a zero quando nel primo caso il punto c si trova a destra mentre nel secondo a sinstra, dovremo quindi inserire dei controlli appositi giusto?
la strada che stavo tentando io per capire se il punto c sta a destra era di ruotrare il secondo vettore dell'angolo tra i due in senso antiorario e vedere se si sovrapponevano utilizzando la formula di rodriguez ma mi sono bloccata perchè non sapevo intorno a quale vettore ruotarlo
p.s scusa per le domande che probabilmente sono banali ma ho un pò di confusione in testa.
Algoritmi: a destra o a sinistra |
