Orientamento di due vettori
Salve ragazzi, mi stavo leggendo un libro per l'implementazione di un algoritmo.
L'algoritmo in questione è: Dato un insieme A di punti nel piano determinare l'insieme convesso che li contiene tutti.
Tra i passi dell'algoritmo vi è il seguente:
prendi un segmento PQ
per ogni punto K diverso da P e da Q determina se K è a sinistra o a destra del segmento.
L'applicazione di questo passo come va effettuata?
Sicuramente è un problema geometrico, per questo posto qui il quesito.
Grazie per l'attenzione.
L'algoritmo in questione è: Dato un insieme A di punti nel piano determinare l'insieme convesso che li contiene tutti.
Tra i passi dell'algoritmo vi è il seguente:
prendi un segmento PQ
per ogni punto K diverso da P e da Q determina se K è a sinistra o a destra del segmento.
L'applicazione di questo passo come va effettuata?
Sicuramente è un problema geometrico, per questo posto qui il quesito.
Grazie per l'attenzione.
Risposte
Devi dare un'orientazione al segmento per iniziare altrimenti non puoi parlare di destra e sinistra rispetto agl'estremi del segmento!
Bè certamente ha ragione j18eos, devi stabilire un'orientazione.
Ma devi implementarlo?
In questo caso devi stabilire un sistema di coordinate.
Cioè se vuoi iniziare credo sia opportuno partire da insiemi convessi nel piano, quindi te lo rappresenti come ti torna meglio (matrici o altro) e ci applichi l'algoritmo.
Una volta che hai messo gli "assi" coordinanti puoi stabilire un'orientazione canonica e hai il concetto di sopra, sotto, destra, sinistra rispetto ad un punto.
Mi spiego meglio....immagina una matrice A formata da soli zeri (ad esempio una 10x10).
Per inserire un punto dici al programma di riempire ad esempio la cella (2,5) con un 1, quindi poni $a_(1,5)=1$.
Quindi il tuo primo punto è $P=(2,5)$.
Un punto $Q=(i,j)$ sarà a destra di $P$ se $i>5$, sarà sotto $P$ se $j>2$.
Spero che sia chiara l'idea, altrimenti spiego meglio mettendo anche qualche disegno.
(ma alla fine provando ad implementre vengono tante idee...)
Ma devi implementarlo?
In questo caso devi stabilire un sistema di coordinate.
Cioè se vuoi iniziare credo sia opportuno partire da insiemi convessi nel piano, quindi te lo rappresenti come ti torna meglio (matrici o altro) e ci applichi l'algoritmo.
Una volta che hai messo gli "assi" coordinanti puoi stabilire un'orientazione canonica e hai il concetto di sopra, sotto, destra, sinistra rispetto ad un punto.
Mi spiego meglio....immagina una matrice A formata da soli zeri (ad esempio una 10x10).
Per inserire un punto dici al programma di riempire ad esempio la cella (2,5) con un 1, quindi poni $a_(1,5)=1$.
Quindi il tuo primo punto è $P=(2,5)$.
Un punto $Q=(i,j)$ sarà a destra di $P$ se $i>5$, sarà sotto $P$ se $j>2$.
Spero che sia chiara l'idea, altrimenti spiego meglio mettendo anche qualche disegno.
(ma alla fine provando ad implementre vengono tante idee...)