Punto nel poligono
come faccio a determinare se un punto è all' interno o all ' esterno di un poligono irregolare di n punti di cui conosco le coordinate degli n punti che lo pongono
Risposte
Variante al metodo proposto da Lupo Grigio:
Consideriamo un qualunque punto $O$ interno al poligono $P$ di $n$ lati. Per ciascuno dei vertici $V_0 ... V_{n-1}$ di $P$ consideriamo i segmenti $r_0 ... r_{n-1}$ che uniscono $O$ a $V_{0} ... V_{n-1}$ rispettivamente. Fissiamo un riferimento ortogonale bidimensionale in modo tale che $r_0$ coincida con l'asse delle ascisse $x$. Sia $theta_i$ la seconda coordinata polare di $V_i \quad \forall i=1...n-1$.
Consideriamo adesso un generico punto $A$ del piano. Sia $theta$ la 2° coordinata polare di $A$. Scegliamo $i$ tale che: $theta_i \leq theta \leq theta_{i+1}$ ; avremo così che $A$ è contenuto nel cono di $R^2$ sotteso dalle rette passanti per i segmenti $r_i$, $r_{i+1}$. Ne segue che $A \in P$ se e soltanto se $A$ è contenuto nel triangolo $OV_iV_{i+1}$ ovvero se e solo se $A$ è combinazione affine dei punti: $O$, $V_i$, $V_{i+1}$, che è condizione verificabile imponendo:
$A = t\cdot O + s\cdot V_i + k\cdot V_{i+1}$ con $t, s, k \geq 0$, $t+s+k = 1$.
Ciao
Consideriamo un qualunque punto $O$ interno al poligono $P$ di $n$ lati. Per ciascuno dei vertici $V_0 ... V_{n-1}$ di $P$ consideriamo i segmenti $r_0 ... r_{n-1}$ che uniscono $O$ a $V_{0} ... V_{n-1}$ rispettivamente. Fissiamo un riferimento ortogonale bidimensionale in modo tale che $r_0$ coincida con l'asse delle ascisse $x$. Sia $theta_i$ la seconda coordinata polare di $V_i \quad \forall i=1...n-1$.
Consideriamo adesso un generico punto $A$ del piano. Sia $theta$ la 2° coordinata polare di $A$. Scegliamo $i$ tale che: $theta_i \leq theta \leq theta_{i+1}$ ; avremo così che $A$ è contenuto nel cono di $R^2$ sotteso dalle rette passanti per i segmenti $r_i$, $r_{i+1}$. Ne segue che $A \in P$ se e soltanto se $A$ è contenuto nel triangolo $OV_iV_{i+1}$ ovvero se e solo se $A$ è combinazione affine dei punti: $O$, $V_i$, $V_{i+1}$, che è condizione verificabile imponendo:
$A = t\cdot O + s\cdot V_i + k\cdot V_{i+1}$ con $t, s, k \geq 0$, $t+s+k = 1$.
Ciao
Primo step: con opportuna traslazione di assai [cosa sempre possibile...] si posiziona il centro del poligono nel punto del piano [0,0]
Secondo step: passando in coordinate polari [$r,theta$], detto $r_1$ il raggio del cerchio circoscritto al poligono, con opportuna rotazione degli assi [cosa sempre possibile...] si posiziona uno dei vertici del poligono nel punto del piano $r=r_1$, $theta=0$
Se $n$ è il n umero dei lati del poligono, il raggio del cerchio inscritto al poligono verrà ad essere...
$r_0=r_1*cos(pi/n)$ (1)
Dato ora un punto di coordinate [$r,theta$] si procede come segue...
a) se $r
b) se $r>r_1$ il punto è sicuramente esterno al poligono
c) se $r_0
cordiali saluti
lupo grigio
an old wolf may lose his teeth, but never his nature
Secondo step: passando in coordinate polari [$r,theta$], detto $r_1$ il raggio del cerchio circoscritto al poligono, con opportuna rotazione degli assi [cosa sempre possibile...] si posiziona uno dei vertici del poligono nel punto del piano $r=r_1$, $theta=0$
Se $n$ è il n umero dei lati del poligono, il raggio del cerchio inscritto al poligono verrà ad essere...
$r_0=r_1*cos(pi/n)$ (1)
Dato ora un punto di coordinate [$r,theta$] si procede come segue...
a) se $r
b) se $r>r_1$ il punto è sicuramente esterno al poligono
c) se $r_0
cordiali saluti
lupo grigio
an old wolf may lose his teeth, but never his nature
non so se è giusto quello che dico perchè non ci ho pensato molto... cmq se hai tutti i punti, hai anche tutte le rette dei lati no. poi prendi il tuo punto fuori o dentro che sia e ricavi tutte le rette per quel punto e un vertice del poligono.
quindi hai n rette che proverai a mettere a sistema con le altre n rette dei lati (2 alla volta) e se hai intersezioni il punto è fuori, se non le hai è dentro!
boh vedi se va bene
quindi hai n rette che proverai a mettere a sistema con le altre n rette dei lati (2 alla volta) e se hai intersezioni il punto è fuori, se non le hai è dentro!
boh vedi se va bene
il calcolo dell' area semmai successivamente
ora mi serve per determinare se un poligono è all' interno di un altro
per un programma che sto facendo
il numero di calcoli non è un limite dato che li faccio fare al computer
ma non riesco a capire che proprietà ha un punto che sta dentro un poligono rispetto ad uno esterno
ora mi serve per determinare se un poligono è all' interno di un altro
per un programma che sto facendo
il numero di calcoli non è un limite dato che li faccio fare al computer
ma non riesco a capire che proprietà ha un punto che sta dentro un poligono rispetto ad uno esterno
"nightingales":
come faccio a determinare se un punto è all' interno o all ' esterno di un poligono irregolare di n punti di cui conosco le coordinate degli n punti che lo pongono
Sembra problema molto complicato, non credo esista un algoritmo semplice e efficace per ogni $n$...
Mi fa venire in mente il metodo Monte Carlo per il calcolo approssimato di un area, per caso è nei tuoi scopi?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo