  Ultima discesa alla Tre Valli '12... di Marco Tenuti " Piutosto de un carton nei ovi, l'è meio un carton de ovi Anomino veronese "    Se vuoi contattarmi via e-mail:

t e n u t i @ l i b e r o . i t
A point inside a polygon
Di Marco Tenuti (del 29/01/2017 @ 22:21:00, in Windows, linkato 266 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. 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. 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. 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.

Nessun commento trovato.

Anti-Spam: digita i numeri Testo (max 1000 caratteri)
Nome

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

Ci sono  persone collegate  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
26/06: 6H Valpolicella 27/08: GF d'Autunno 08/11: XCRunning Grezzana  KM STORICI  BREVETTI E CIRCUITI

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

 < settembre 2020 > 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

Cerca per parola chiave famiglia (4)
fotografia (1)
gastronomia (1)
MTB (14)
rally (2)
viaggi (12)

Le fotografie più cliccate Quale circuito suggerisci al Marcante per il 2013?

Lessinia Tour
Prestigio MTB
Nobili MTB
Challenge Giordana
Gare all'estero
Stare a casa Listening
Kid Rock - Rock n Roll Jesus

Ghosts - The world is outside

Hellogoodbye - Zombies! Aliens! Vampires! Dinosaurs!

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   28/09/2020 @ 17:04:15
script eseguito in 219 ms