Immagine
 Davide si cimenta provetto fotografo in Kenia... di Marco Tenuti
 
"
El caco 'ndrio el liga in boca

Marco Tenuti
"
 



Miei sponsor
Gli sponsor che pago io

Social Network



Se vuoi contattarmi via e-mail:

t e n u t i @ l i b e r o . i t
Wikio - Top dei blog
\\ Home Page : Articolo
Ce lo avete un modo per trovare un punto dentro un poligono?
Di Marco Tenuti (del 12/01/2012 @ 13:15:27, in informatica, linkato 9332 volte)

Un punto dentro un poligonoL'altroieri per questioni professionali mi sono imbattuto nel problema di stabilire computazionalmente un qualsiasi punto interno di un poligono. Supponiamo che vi si dia un poligono P costituito da N vertici: voi dovete rispondere con P_int, cioè dovete dotarmi di una procedura computazionale (cioè un algoritmo) che consenta di stabilire le coordinate di un punto (P_int) che si è certi essere contenuto nel poligono e non sul bordo. Tengo a precisare che la procedura deve funzionare con un qualsiasi poligono, cioè anche con uno concavo, altrimenti è troppo facile.

Nel caso di un poligono convesso, la soluzione sarebbe semplicemente di rispondere con la formuletta del calcolo del centroide (punto medio tra tutti i vertici) o del baricentro.

Tra le varie ipotesi fantasiose, verosimili ed inverosimili, la più stupida che ho trovato nella rete è stata questa: "basta guardarlo il poligono e indicare un punto interno". A dir poco geniale!

Le soluzioni algoritmiche più comuni a questa problematica si basano di solito sul ragionamento dell'attraversamento: provo ad attraversare il poligono. Alla prima intersezione entro nel poligono, alla successiva esco. Se il poligono è convesso, sono sicuro che entro una sola volta ed esco una sola volta. Se il poligono è concavo, a seconda della retta di attraversamento, potrei entrare ed uscire più volte, pertanto basta contare il numero di volte che ho incontrato un segmento del perimetro per dire se sono dentro o fuori. Se ne ho già incontrato un numero dispari di segmenti, mi trovo dentro il poligono; se invece ho incontrato i segmenti del poligono per un numero pari di volte, sono certamente fuori.

In una versione algoritmica la cosa difficile è proprio stabilire bene una buona retta di attraversamento:

  • costruisco il bounding box (rettangolo contenitore) che contiene completamente il poligono (AABB)
  • stabilisco un punto di prova che si trova dentro uno degli quattro quadranti al di fuori del bounding box: tale punto è sicuramente fuori dal poligono
  • stabilisco la retta di attraversamento congiungendo tale punto ed il centro del bounding box
  • determino tutte le intersezioni tra i segmenti del poligono e la retta di attraversamento
  • se ho scelto opportunamente la retta di attraversamento, avrò sicuramente almeno un paio di intersezioni
  • il risultato della computazione, cioè la risposta al problema, è il punto medio tra la prima e la seconda intersezione

Questo approccio algoritmico è però da evitare, perché potrebbe essere necessario dover cambiare la retta di attraversamento alcune volte. In più la retta di attraversamento potrebbe incrociare "malamente" qualche segmento, perché le è esattamente parallela, con tutti i problemi del caso. In tal caso non riusciamo a stabilire se l'intersezione che non è puntuale, ma è a tutti gli effetti un segmento vero e proprio, ci faccia entrare o uscire dal poligono. La gestione di questa casistica porterebbe a scrivere del codice specifico e comunque saremmo in presenza di approssimazioni nella valutazione dell'intersezione tra due segmenti pressoché paralleli.

Ce l'avete voi un'idea migliore per trovare una semplice soluzione al problema? Vi dico subito che c'è - è elegante e molto affascinante - e che l'ho già implementata, però ve la espongo più avanti.

Articolo Articolo  Storico Storico Stampa Stampa
 
# 1
Io proverei con il metodo della circonferenza inscritta al bounding box ...
Di  Nic  (inviato il 12/01/2012 @ 13:58:49)
# 2
Esplicita un po' meglio, Nic. Stai parlando del punto di scelta con cui individuare la retta di attraversamento?
Di  MT  (inviato il 12/01/2012 @ 14:35:56)
# 3
Questo è un classico problema risolto dalla Geometria Computazionale. L'algoritmo e le strutture dati sono abbastanza complicate ma il risultato è robusto!
Di  natan  (inviato il 23/01/2015 @ 20:39:58)
# 4
search engine optimization pricing
Di  Wendell  (inviato il 12/11/2022 @ 06:20:35)
# 5
seo packages for small Business
Di  Kerrie  (inviato il 17/11/2022 @ 23:40:45)
# 6
Sergio
Di  Finlay  (inviato il 04/12/2022 @ 23:46:31)
# 7
Car Diagnostic
Di  Maximo  (inviato il 07/12/2022 @ 19:14:58)
# 8
car key remote Control repair
Di  Tanesha  (inviato il 07/12/2022 @ 23:07:26)
# 9
Asbestos Lawyer
Di  Sherry  (inviato il 08/12/2022 @ 14:14:42)
# 10
Mesothelioma Settlement
Di  Francesca  (inviato il 10/12/2022 @ 02:00:44)
# 11
Mesothelioma Case
Di  Phillis  (inviato il 11/12/2022 @ 09:52:25)
# 12
Asbestos claim
Di  Shawna  (inviato il 11/12/2022 @ 14:32:02)
# 13
Demo Slot
Di  Aileen  (inviato il 15/12/2022 @ 16:34:44)
# 14
https://www.sunseteyewear.co.id/profile/erssanigita/profile
Di  Willy  (inviato il 15/12/2022 @ 17:04:11)
# 15
akun demo Slot
Di  Otto  (inviato il 15/12/2022 @ 17:59:33)
# 16
slot Demo gratis
Di  Davida  (inviato il 15/12/2022 @ 18:03:07)
# 17
Akun Demo slot
Di  Harold  (inviato il 15/12/2022 @ 20:11:22)
# 18
akun Demo slot
Di  Carina  (inviato il 15/12/2022 @ 22:11:58)
# 19
Akun Demo slot
Di  Flossie  (inviato il 15/12/2022 @ 22:17:20)
# 20
Slot demo
Di  Isiah  (inviato il 16/12/2022 @ 00:31:10)
# 21
Susana
Di  Guy  (inviato il 16/12/2022 @ 19:01:00)
# 22
https://ironworksfitness.org/
Di  Leo  (inviato il 17/12/2022 @ 00:53:14)
# 23
grimwolf.net
Di  Rory  (inviato il 17/12/2022 @ 01:48:38)
# 24
Ftsfnigeria.Org
Di  Antoine  (inviato il 17/12/2022 @ 04:14:29)
# 25
purplemiddleway.org
Di  Margene  (inviato il 17/12/2022 @ 11:50:04)
# 26
harvesttruck.org
Di  Maisie  (inviato il 17/12/2022 @ 12:20:16)
# 27
rcyf.net
Di  Nancy  (inviato il 17/12/2022 @ 14:48:55)
# 28
Mycrashcourse.Net
Di  Carmela  (inviato il 17/12/2022 @ 16:42:11)
# 29
Smc2012.org
Di  Earnest  (inviato il 17/12/2022 @ 19:14:31)
# 30
Https://Rraft.Org
Di  Marta  (inviato il 17/12/2022 @ 21:02:23)
# 31
https://emilyobrien.net/
Di  Benny  (inviato il 17/12/2022 @ 22:45:02)
# 32
codoli.org
Di  Amanda  (inviato il 18/12/2022 @ 17:16:06)
# 33
https://imtma.org
Di  Earnestine  (inviato il 19/12/2022 @ 10:19:39)
# 34
Poker Online
Di  Elizbeth  (inviato il 27/12/2022 @ 14:05:55)
# 35
Lottery hongkong
Di  Milo  (inviato il 27/12/2022 @ 22:09:56)
# 36
Juliet
Di  Trina  (inviato il 27/12/2022 @ 22:34:01)
# 37
ha-ber.Net
Di  Reva  (inviato il 27/12/2022 @ 23:10:48)
# 38
Valerie
Di  Elvera  (inviato il 29/12/2022 @ 02:42:59)
# 39
poker
Di  Vanessa  (inviato il 29/12/2022 @ 07:42:23)
# 40
slot
Di  Colleen  (inviato il 29/12/2022 @ 08:21:31)
# 41
togel singapore lottery
Di  Jann  (inviato il 29/12/2022 @ 08:38:02)
# 42
https://thinkgeek.org
Di  Felix  (inviato il 29/12/2022 @ 11:56:10)
# 43
pragmatic Play
Di  Juliet  (inviato il 29/12/2022 @ 18:29:45)
# 44
Efrain
Di  Michel  (inviato il 30/12/2022 @ 02:43:41)
# 45
Novaeco.Ru
Di  Ashly  (inviato il 07/01/2023 @ 20:54:02)
# 46
hemp Online
Di  Kazuko  (inviato il 11/01/2023 @ 05:03:39)
# 47
asbestos Lawsuit
Di  Kala  (inviato il 11/01/2023 @ 08:19:00)
# 48
Abbey
Di  Mohammed  (inviato il 11/01/2023 @ 18:39:40)
# 49
Commercial door repair
Di  Latanya  (inviato il 11/01/2023 @ 19:26:16)
# 50
mymobilityscooters.co.uk
Di  Mellissa  (inviato il 12/01/2023 @ 03:40:58)
# 51
Sasha
Di  Calvin  (inviato il 12/01/2023 @ 09:03:10)
# 52
Tesco sim only deals uk
Di  Odette  (inviato il 13/01/2023 @ 00:34:27)
# 53
deals
Di  Christin  (inviato il 13/01/2023 @ 03:03:26)
# 54
Mesothelioma settlement
Di  Marie  (inviato il 14/01/2023 @ 00:21:19)
# 55
Ghost alarm Fitting
Di  Wilford  (inviato il 14/01/2023 @ 02:00:42)
# 56
Masturbators For men
Di  Shavonne  (inviato il 14/01/2023 @ 05:31:16)
# 57
gurupin.co.kr
Di  Irish  (inviato il 14/01/2023 @ 06:29:44)
# 58
Windows
Di  Mahalia  (inviato il 14/01/2023 @ 08:58:45)
# 59
Heike
Di  Marcus  (inviato il 14/01/2023 @ 09:03:00)
# 60
https://realgirls.fun/bettyebrifma
Di  Ian  (inviato il 14/01/2023 @ 09:47:59)
# 61
https://Realgirls.fun/kennithdelit
Di  Lawanna  (inviato il 14/01/2023 @ 10:36:14)
# 62
delta 8 hemp flowers
Di  Alvaro  (inviato il 14/01/2023 @ 12:08:43)
# 63
asbestos Attorney
Di  Allison  (inviato il 14/01/2023 @ 13:15:36)
Anti-Spam: digita i numeri CAPTCHA
Testo (max 1000 caratteri)
Nome
e-Mail / Link


Disclaimer
L'indirizzo IP del mittente viene registrato, in ogni caso si raccomanda la buona educazione.


Ci sono  persone collegate

Tagcloud

Gare 2017
GARE 2017?
26/03: GF Tre Valli
30/04: GF del Durello
21/05: Passo Buole Extreme
28/05: Soave Bike
25/06: Lessinia Legend
Gare 2016
GARE 2016
26/06: 6H Valpolicella Fatta
27/08: GF d'Autunno Fatta
08/11: XCRunning Grezzana Fatta
Tickerkm
KM STORICI

Km fatti

Palmares
BREVETTI E CIRCUITI

2014: Salzkammergut Survivor
2012: Prestigio MTB
2011: Prestigio MTB
2010: Prestigio MTB, Fizik Veneto
2008: Garda Challenge

< marzo 2024 >
L
M
M
G
V
S
D
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
             

Cerca per parola chiave
 

Titolo
famiglia (4)
fotografia (1)
gastronomia (1)
MTB (14)
rally (2)
viaggi (12)

Le fotografie pił cliccate

Titolo
Quale circuito suggerisci al Marcante per il 2013?

 Lessinia Tour
 Prestigio MTB
 Nobili MTB
 Challenge Giordana
 Gare all'estero
 Stare a casa

Titolo

View Marco Tenuti's profile on LinkedIn

Listening
Kid Rock - Rock n Roll Jesus

Ghosts - The world is outside

Hellogoodbye - Zombies! Aliens! Vampires! Dinosaurs!

Reading
Fabio Volo - E' una vita che ti aspetto
Michael Guillen - Le 5 equazioni che hanno cambiato il mondo
Sophie Kinsella - I love shopping a New York

Watching
Mia moglie consiglia Le sorelle McLeod



Titolo
.NET Framework (4)
Abarth (13)
Alcenago (4)
auto (15)
computational (2)
consumatore (56)
cucina (18)
cultura (16)
dizionario (2)
famiglia (40)
finanza (4)
Grezzana (6)
hitech (17)
humour (8)
idee (1)
informatica (62)
iPhone (46)
mobile computing (10)
MTB (1199)
musica (4)
natura (23)
OS X (3)
PS3 (7)
rally (63)
salute (4)
social (4)
telefonia (3)
Verona (12)
viaggi (26)
video (7)
Visual Basic 6 (5)
web (49)
Windows (33)

Catalogati per mese:
Marzo 2024
Febbraio 2024
Gennaio 2024
Dicembre 2023
Novembre 2023
Ottobre 2023
Settembre 2023
Agosto 2023
Luglio 2023
Giugno 2023
Maggio 2023
Aprile 2023
Marzo 2023
Febbraio 2023
Gennaio 2023
Dicembre 2022
Novembre 2022
Ottobre 2022
Settembre 2022
Agosto 2022
Luglio 2022
Giugno 2022
Maggio 2022
Aprile 2022
Marzo 2022
Febbraio 2022
Gennaio 2022
Dicembre 2021
Novembre 2021
Ottobre 2021
Settembre 2021
Agosto 2021
Luglio 2021
Giugno 2021
Maggio 2021
Aprile 2021
Marzo 2021
Febbraio 2021
Gennaio 2021
Dicembre 2020
Novembre 2020
Ottobre 2020
Settembre 2020
Agosto 2020
Luglio 2020
Giugno 2020
Maggio 2020
Aprile 2020
Marzo 2020
Febbraio 2020
Gennaio 2020
Dicembre 2019
Novembre 2019
Ottobre 2019
Settembre 2019
Agosto 2019
Luglio 2019
Giugno 2019
Maggio 2019
Aprile 2019
Marzo 2019
Febbraio 2019
Gennaio 2019
Dicembre 2018
Novembre 2018
Ottobre 2018
Settembre 2018
Agosto 2018
Luglio 2018
Giugno 2018
Maggio 2018
Aprile 2018
Marzo 2018
Febbraio 2018
Gennaio 2018
Dicembre 2017
Novembre 2017
Ottobre 2017
Settembre 2017
Agosto 2017
Luglio 2017
Giugno 2017
Maggio 2017
Aprile 2017
Marzo 2017
Febbraio 2017
Gennaio 2017
Dicembre 2016
Novembre 2016
Ottobre 2016
Settembre 2016
Agosto 2016
Luglio 2016
Giugno 2016
Maggio 2016
Aprile 2016
Marzo 2016
Febbraio 2016
Gennaio 2016
Dicembre 2015
Novembre 2015
Ottobre 2015
Settembre 2015
Agosto 2015
Luglio 2015
Giugno 2015
Maggio 2015
Aprile 2015
Marzo 2015
Febbraio 2015
Gennaio 2015
Dicembre 2014
Novembre 2014
Ottobre 2014
Settembre 2014
Agosto 2014
Luglio 2014
Giugno 2014
Maggio 2014
Aprile 2014
Marzo 2014
Febbraio 2014
Gennaio 2014
Dicembre 2013
Novembre 2013
Ottobre 2013
Settembre 2013
Agosto 2013
Luglio 2013
Giugno 2013
Maggio 2013
Aprile 2013
Marzo 2013
Febbraio 2013
Gennaio 2013
Dicembre 2012
Novembre 2012
Ottobre 2012
Settembre 2012
Agosto 2012
Luglio 2012
Giugno 2012
Maggio 2012
Aprile 2012
Marzo 2012
Febbraio 2012
Gennaio 2012
Dicembre 2011
Novembre 2011
Ottobre 2011
Settembre 2011
Agosto 2011
Luglio 2011
Giugno 2011
Maggio 2011
Aprile 2011
Marzo 2011
Febbraio 2011
Gennaio 2011
Dicembre 2010
Novembre 2010
Ottobre 2010
Settembre 2010
Agosto 2010
Luglio 2010
Giugno 2010
Maggio 2010
Aprile 2010
Marzo 2010
Febbraio 2010
Gennaio 2010
Dicembre 2009
Novembre 2009
Ottobre 2009
Settembre 2009
Agosto 2009
Luglio 2009
Giugno 2009
Maggio 2009
Aprile 2009
Marzo 2009
Febbraio 2009
Gennaio 2009
Dicembre 2008
Novembre 2008
Ottobre 2008
Settembre 2008
Agosto 2008
Luglio 2008
Giugno 2008
Maggio 2008
Aprile 2008
Marzo 2008
Febbraio 2008
Gennaio 2008
Dicembre 2007
Novembre 2007
Ottobre 2007
Settembre 2007
Agosto 2007
Luglio 2007
Giugno 2007
Maggio 2007
Aprile 2007
Marzo 2007
Febbraio 2007
Gennaio 2007
Dicembre 2006
Novembre 2006
Ottobre 2006
Settembre 2006
Agosto 2006
Luglio 2006
Giugno 2006
Maggio 2006
Aprile 2006
Marzo 2006
Febbraio 2006
Gennaio 2006
Dicembre 2005
Novembre 2005
Ottobre 2005
Settembre 2005
Agosto 2005
Luglio 2005
Giugno 2005
Maggio 2005
Aprile 2005
Marzo 2005
Febbraio 2005
Gennaio 2005
Dicembre 2004

Gli interventi pił cliccati

Ultimi commenti:
https://zetcasino.on...
09/03/2024 @ 06:53:31
Di Cory
telegra.ph
22/02/2024 @ 17:27:35
Di Lida
Casinoonlinevavada.O...
19/02/2024 @ 18:29:38
Di Jackie
개자1...
12/02/2024 @ 17:32:22
Di Roseann
адв...
12/02/2024 @ 16:26:23
Di Dalene
Reduslim-Familienpak...
27/01/2024 @ 15:20:34
Di Alannah
pipeline pro
22/01/2024 @ 20:20:15
Di Mervin
hotels 18+
19/01/2024 @ 05:05:00
Di Ruby


19/03/2024 @ 06:26:36
script eseguito in 188 ms