Immagine
 Ultima discesa alla Tre Valli '12... di Marco Tenuti
 
"
Una volta che finisci in un database, ci sei per sempre

Marcante
"
 



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 : Storico per mese (inverti l'ordine)
Di seguito tutti gli interventi pubblicati sul sito, in ordine cronologico.
 
 
Di Marco Tenuti (del 29/01/2017 @ 22:21:00, in Windows, linkato 1764 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 (p)Link Commenti Commenti (0)  Storico Storico  Stampa Stampa
 
Di Marco Tenuti (del 17/01/2017 @ 19:35:00, in Windows, linkato 717 volte)

Anche Amazon è recentemente preso di mira dai truffatori, cioè gente che usa l'enorme visibilità del portale del negozio di Vancouver per cercare di portare a segno dei furti ai danni degli ignari.

Lo schema è molto semplice: il venditore/truffatore, una terza parte rispetto al negozio ufficiale di Amazon, mette in vendita un articolo proponendolo ad un prezzo sensibilmente più basso di un altro venditore serio e affidabile, ma non troppo basso.

Io mi sono imbattuto in uno sconto di circa il 15%, però il venditore aveva modificato opportunamente il proprio nome sostituendolo da Mio Negozio Online srl in ContattamiAllIndirizzoBoegmhAtliberoDot.

Io ho fiutato subito la trappola, ma non per questo mi sono tirato indietro al tentativo di acquistare qualcosa ad un prezzo interessante ed ho scritto puntualmente al venditore farlocco con un messaggio e-mail di richiesta di informazioni più dettagliate per portare avanti l'acquisto.

Oggi ho ricevuto la risposta, arrivata comunque dal medesimo indirizzo e-mail:

Ciao,
Il prodotto è originale, con la garanzia e la fattura. Abbiamo offerte speciali in questo periodo. L'offerta dura per 7 giorni. La consegna è gratuita in Europa da DHL Express. Questa attività va avanti Garanzia Programma A-to-Z Amazon.

L'operazione può essere avviata da Amazon, ho bisogno di quanto segue:

Nome completo:
indirizzo:
città:
CAP:
paese:
Telefono:
di prodotto:
Prezzo:

Mi trasmette immediatamente i dati necessari ad Amazon. Amazon invierà le informazioni relative alla cassa. In un massimo di 3 giorni, è possibile ottenere il prodotto. Con Amazon, avete 7 giorni per verificare l'articolo. Bisogna prendere una decisione. Se si desidera mantenere il prodotto o no! Se si desidera, Amazon invierà il denaro a me. In caso contrario, si ottiene il denaro e DHL prenderà l'oggetto da voi e dare di nuovo a me. Pagherò per la consegna ricorrente!

Sto aspettando la risposta.
Grazie.

Quando ho visto l'italiano sgrammaticato e il giro vorticoso, ho fatto uno più uno. Non contento, ho segnalato la cosa al servizio di assistenza tecnica di Amazon, il quale non ha fatto altro che confermare: negli ultimi giorni è tutto un comparire di offerte farlocche di truffatori e loro lavorano continuamente alla rimozione.

State all'occhio!

Articolo (p)Link Commenti Commenti (0)  Storico Storico  Stampa Stampa
 
Pagine: 1


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 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:
Ottobre 2024
Settembre 2024
Agosto 2024
Luglio 2024
Giugno 2024
Maggio 2024
Aprile 2024
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:
glaziers eastleigh
14/10/2024 @ 22:40:23
Di Joel
Anne
14/10/2024 @ 22:38:48
Di Wilbur
https://morphomics.s...
14/10/2024 @ 21:27:06
Di Aurelio
Cat flap
14/10/2024 @ 21:02:23
Di Cortez
spare
14/10/2024 @ 20:58:02
Di Gabriele
New Glazing leeds
14/10/2024 @ 20:35:31
Di Mora
Jacquetta
14/10/2024 @ 19:52:35
Di Cassandra
Repair Upvc window
14/10/2024 @ 19:16:18
Di Judith


14/10/2024 @ 23:00:39
script eseguito in 156 ms