Algoritmo per il calcolo di aree di poligoni concavi
Salve,
Vorrei porvi un quesito:
Esiste un Algoritmo certo per il calcolo di Aree di poligoni concavi?
Il contesto è questo, in un progetto per la mia università sto sviluppando un programma che riesca a partire da un insieme di vertici (ordinati) a dare tutte le proprietà del poligono corrispondente, nel calcolo delle aree ho provato a suddividere, a partire da un vertice, il poligono in "spicchi" (triangoli) per ognuno dei quali calcolo l'area con la formula di Erone e poi faccio la somma delle aree di tutti gli "spicchi" trovati, tale metodo però pare dare buoni risultati solo su poligoni convessi....
avete consigli a riguardo?
Grazie mille
Vorrei porvi un quesito:
Esiste un Algoritmo certo per il calcolo di Aree di poligoni concavi?
Il contesto è questo, in un progetto per la mia università sto sviluppando un programma che riesca a partire da un insieme di vertici (ordinati) a dare tutte le proprietà del poligono corrispondente, nel calcolo delle aree ho provato a suddividere, a partire da un vertice, il poligono in "spicchi" (triangoli) per ognuno dei quali calcolo l'area con la formula di Erone e poi faccio la somma delle aree di tutti gli "spicchi" trovati, tale metodo però pare dare buoni risultati solo su poligoni convessi....
avete consigli a riguardo?
Grazie mille
Risposte
"Denny8x":
Salve,
Vorrei porvi un quesito:
Esiste un Algoritmo certo per il calcolo di Aree di poligoni concavi?
Il contesto è questo, in un progetto per la mia università sto sviluppando un programma che riesca a partire da un insieme di vertici (ordinati) a dare tutte le proprietà del poligono corrispondente, nel calcolo delle aree ho provato a suddividere, a partire da un vertice, il poligono in "spicchi" (triangoli) per ognuno dei quali calcolo l'area con la formula di Erone e poi faccio la somma delle aree di tutti gli "spicchi" trovati, tale metodo però pare dare buoni risultati solo su poligoni convessi....
avete consigli a riguardo?
Grazie mille
Per i poligoni concavi il metodo funziona alla grande perchè, comunque scegli il vertice di partenza, sei sicuro che i lati degli "spicchi" e quindi gli "spicchi" stessi sono tutti interni al poligono. Per i poligoni concavi questo non accade (pensa ad una stella pentagonale, tipo puntale dell'albero di Natale
) e perciò il metodo non è buono.Metodi diretti per la risoluzione del tuo problema non ne conosco, ma comunque provo a suggerirti una strada (alquanto banale in verità, ed è molto probabile che tu ci abbia già pensato...).
L'unica cosa che mi viene in mente è unire i vertici di angoli concavi consecutivi del poligono in modo da scomporre la figura in parti convesse, calcolare l'area di ognuna e sommare per ottenere l'area totale. Per esemplificare pensa sempre alla stella pentagonale: il metodo che ti suggerisco è quello di ricavare cinque triangoli ed un pentagono unendo i vertici corrispondenti agli angoli concavi (insomma, quelli che non sono delimitati dalle "punte"), trovare le loro aree col metodo che hai progettato per i poligoni convessi e poi sommarle.
Non so se può andare bene in generale, è un'idea che mi è venuta così, di getto. Ci dovrai lavorare un po' su.
Spero di esserti sato utile.
Grazie per il consiglio, ho provato la strada che mi hai indicato tu in alcuni casi funziona esistono però casi in cui non è possibile applicare questo metodo (a volte andrebbe iterato ecc...
Mi è venuta ora un'idea...ma è ancora molto grezza... solitamente per il calcolo delle aree si usano gli integrali, ora provo a dare uno sguardo alle varie proprietà degli integrali e vedo se c'è qualcosa che leghi l'area di un poligono con l'integrale della sua "frontiera" o qualcosa del genere se avete idee io sono qui
se avete idee io sono qui
il problema e' stimolante, e credo esistano gia' algoritmi belli e pronti per calcolare l'area in questione, cmq se io ti dico come farei io , anche se per applicare sto metodo bisogna fare un po' di calcoli.
supponiamo intanto che:
i vertici siano dati ordinati ed in ordine orario
esempio:
A
B
C
D
E
F
dove i lati del poligono sono AB,BC,CD,DE,EF,FA
allora partiamo dal vertice che si trova piu' in basso (quello con minore ordinata) del poligono, supponiamo sia A
calcoliamo la retta contenente AC
vediamo se il punto B si trova a sinistra tale retta (con a geometria analitica dovrebbe essere fattibile)
allora,
se B si trova a sinistra della retta per AB --------> calcoliamo l'area del triangolo ABC e sommiamola al totale parziale
se B non si trova a sinistra della retta per AB --------> calcoliamo l'area del triangolo ABC e sottraiamola al totale parziale
poi
calcoliamo la retta contenente AD
vediamo se il punto C si trova a sinistra tale retta (con a geometria analitica dovrebbe essere fattibile)
allora,
se C si trova a sinistra della retta per AD --------> calcoliamo l'area del triangolo ACD e sommiamola al totale parziale
se C non si trova a sinistra della retta per AD --------> calcoliamo l'area del triangolo ACD e sottraiamola al totale parziale
andando avanti cosi' si dovrebbe tenere in conto delle concavita' del poligono....
spero chiaro e senza errori.
perfettibile (e' solo uno spunto)
supponiamo intanto che:
i vertici siano dati ordinati ed in ordine orario
esempio:
A
B
C
D
E
F
dove i lati del poligono sono AB,BC,CD,DE,EF,FA
allora partiamo dal vertice che si trova piu' in basso (quello con minore ordinata) del poligono, supponiamo sia A
calcoliamo la retta contenente AC
vediamo se il punto B si trova a sinistra tale retta (con a geometria analitica dovrebbe essere fattibile)
allora,
se B si trova a sinistra della retta per AB --------> calcoliamo l'area del triangolo ABC e sommiamola al totale parziale
se B non si trova a sinistra della retta per AB --------> calcoliamo l'area del triangolo ABC e sottraiamola al totale parziale
poi
calcoliamo la retta contenente AD
vediamo se il punto C si trova a sinistra tale retta (con a geometria analitica dovrebbe essere fattibile)
allora,
se C si trova a sinistra della retta per AD --------> calcoliamo l'area del triangolo ACD e sommiamola al totale parziale
se C non si trova a sinistra della retta per AD --------> calcoliamo l'area del triangolo ACD e sottraiamola al totale parziale
andando avanti cosi' si dovrebbe tenere in conto delle concavita' del poligono....
spero chiaro e senza errori.
perfettibile (e' solo uno spunto)
ho provato il tuo metodo su questo poligono però mi è parso non funzionare (probabilmente l'ho applicato male)
sia A il vertice piu' in basso e siano $V_1 ... V_7$ gli altri vertici;
praticamente devi individuare tutti i triangoli del tipo
$A V_(i-1) V_i$
e
se $V_(i-1)$ e' a sinistra della retta per $A V_i$ allora sommi la corrispondente area, altrimenti la sottrai
alla fine di tutte queste somme e sottrazioni dovresti avere l'area totale corretta
a me sembrerebe funzionare....
prova con un esempio piu' semplice (1 solo angolo concavo) cosi' si puo' discutere meglio e trovare il punto debole del 'mio' algoritmo
praticamente devi individuare tutti i triangoli del tipo
$A V_(i-1) V_i$
e
se $V_(i-1)$ e' a sinistra della retta per $A V_i$ allora sommi la corrispondente area, altrimenti la sottrai
alla fine di tutte queste somme e sottrazioni dovresti avere l'area totale corretta
a me sembrerebe funzionare....
prova con un esempio piu' semplice (1 solo angolo concavo) cosi' si puo' discutere meglio e trovare il punto debole del 'mio' algoritmo
Formula di Schoelace
che poi dovrebbe essere ottenuta a partire dal discorso degli integrali
che poi dovrebbe essere ottenuta a partire dal discorso degli integrali
Chiamo $P_i$ gli $n$ vertici del poligono con $i=1..n$ disposti in sequenza e definisco il punto $P_{n+1}$ coincidente con $P_{1}$.
Prendo un punto a caso nel piano (per esempio l'origine $O$), l'area del poligono (concavo o convesso che sia, non importa) si ottiene immediatamente dalla seguente somma di prodotti vettoriali:
$A=1/2 |\sum_{i=1}^{n}\vec(OP_i) \times \vec(OP_{i+1})|$
ciao
PS
La componente $z$ (l'unica non identicamente nulla) del prodotto vettoriale tra due vettori del piano $x,y$ $\vec(OA)$ e $\vec(OB)$ vale:
$(\vec(OA) \times \vec(OB))_z=OA_x *OB_y - OA_y *OB_x $
Questo risultato (che mi sembra un po' più generale e rigoroso) giustifica la formula proposta da Denny8x.
Con analoghe considerazioni si possono ottenere anche altre proprietà geometriche della figura....
Prendo un punto a caso nel piano (per esempio l'origine $O$), l'area del poligono (concavo o convesso che sia, non importa) si ottiene immediatamente dalla seguente somma di prodotti vettoriali:
$A=1/2 |\sum_{i=1}^{n}\vec(OP_i) \times \vec(OP_{i+1})|$
ciao
PS
La componente $z$ (l'unica non identicamente nulla) del prodotto vettoriale tra due vettori del piano $x,y$ $\vec(OA)$ e $\vec(OB)$ vale:
$(\vec(OA) \times \vec(OB))_z=OA_x *OB_y - OA_y *OB_x $
Questo risultato (che mi sembra un po' più generale e rigoroso) giustifica la formula proposta da Denny8x.
Con analoghe considerazioni si possono ottenere anche altre proprietà geometriche della figura....
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo