Immagine
 Dopo Prato Piazza è la volta di buttarsi verso Carbonin (Dolomiti Superbike 2012)... di Marco Tenuti
 
"
Me par che la gamba la tira ben anca de drio. Sa disito?

A. Pezzo
"
 



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
How to find a point inside a polygon
Di Marco Tenuti (del 29/01/2017 @ 22:20:09, in informatica, linkato 406 volte)

Some months ago I challenged my readers to find a method to determine an inner point inside a polygon. I described the original issue in this article in Italian language, altough more than one lector confused this issue with another one, i.e. determine if a point is inside or not in a polygon.

Canonical diagonal crossover

I would spend a little bit more on the issue: the algorytmic problem is to find a point completely inside the polygon, whatever the polygon is convex or concave. The satisfying point must lay completely in the inner region bounded by the polygon, not over the bound, otherwise you could solve the problem taking any of the vertexes or the mid point over any edge.

The most elegant solution I found - which is also very effective to outfit in programming code - is based on the fact tha any polygon may be always discretized in triangles and you may prove for induction that a valid solution is a mid point taken over and inner diagonal of the polygon. What's difficult is finding an inner diagonal, i.e. a segment that connects any pair of vertexes. In each polygon you can find several diagonals completely inside the polygon, but you can stop as soon as you find the first one.

Proof for induction that an inner diagonal always exists

Let's make a proposal for an easy algorytm to get some solution:

  • loop from 1 to n over the set of the polygon vertexes
  • take the i-th vertex from 1 to n, if n is the amount of the polygon vertexes
    • take another j-th vertex where j loops from i+1 to n and let's trace the test diagonal, which doesn't have to belong to the edges set
      • take each k-th edge in the edges set
        • check if the test diagonal from i to j intersects k-th edge
      • if the test diagonal doesn't intersect any edge, it could be completely embraced in the polygon or it could be completely outside the polygon
      • check if the mid point of the test diagonal is inside or outside the polygon if the mid point is inside, return it as the solution

As you may see, this pseudocode is quite easy to understand, although it is far from being efficient: its polynomial complexity is O(n3).

Let's go a step further and let's quickly see the method based on the proof that an inner diagonal always exists inside a polygon [O'Rourke 13-14]. The idea behind is that the mid point of the inner diagonal is always inside the polygon.

You may prove that for induction using the amount of vertexes and sides of the polygon. If you find a solution for an N-vertexes polygon, you can find a solution even for an N+1-vertexes polygon.

A point inside the segment ab

The base of induction is the easiest polygon, the triangle. In the triangle the solution to the problem is trivial: just use the centroid of the vertexes.

For a quadrangle, if it is convex, you get two inner diagonals and both satisfy the algorytm choice. If the quadrangle is concave, only one diagonal is completely inside, but the solution is whatsoever found. You can notice that the inner diagonal is the side shared between two adjacent triangles got by the triangular meshing of the polygon, so you just need to consider any shared side of two triangles in the mesh.

Let's move to the inductive step:

  • find a convex vertex v in the polygon and consider a and b as adjacent vertexes surrounding v
  • for each other vertex q in the polygon
    • if the vertex q is inside the triangle avb, calculate the distance of v to the segment ab
    • keep vertex q as solution if its distance is minimal with respect other found vertexes
  • if no vertexes q have been found inside avb, use the mid point of segment ab as solution or the centroid of triangle avb
  • if some vertex q is inside the triangle avb then the diagonal qv is surely inside and the solution is its mid point

In the image shown above, you may noticed that the nearest point to segment ab, doesn't lay in triangle avb, so the solution in the centroid in triangle avb or the mid point of segment ab, which is an inner diagonal.

You may notice that algorytm complexity is O(n), which is the best you would ask for: its optimal even in the performance space.

Articolo Articolo  Storico Storico Stampa Stampa
 
Nessun commento trovato.

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

< ottobre 2017 >
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)
consumatore (57)
cucina (18)
cultura (15)
dizionario (2)
famiglia (40)
finanza (4)
Grezzana (6)
hitech (17)
humour (8)
idee (1)
informatica (66)
iPhone (46)
mobile computing (10)
MTB (1198)
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 (31)

Catalogati per mese:
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:
86Lelia
04/09/2017 @ 21:58:04
Di Timothy
Grazie mille Marco,l...
31/08/2017 @ 10:04:45
Di Matteo
e la slitta della le...
25/08/2017 @ 21:26:21
Di nino
First Way (My Advice...
02/07/2017 @ 20:00:27
Di francesco
č successo anche a m...
02/07/2017 @ 19:46:14
Di francesco
maldestro tentativo ...
26/06/2017 @ 16:30:05
Di alep
ZPETS
22/04/2017 @ 00:54:54
Di Floy
A me hanno telefonat...
18/04/2017 @ 11:23:01
Di Armando


23/10/2017 @ 13:50:06
script eseguito in 94 ms