Un poligono semplice, o poligono di Jordan, definisce un interno e un esterno (vedi l’articolo Che cos’è un poligono?). Quale algoritmo permette di stabilire se un punto del piano è interno o esterno al poligono? La domanda sembra banale per un poligono non troppo complicato, come quello della figura seguente:
Al cervello umano basta un quarto di secondo per dirci che il punto M si trova all’interno del poligono, mentre il punto N è all’esterno. Ma come fare algoritmicamente? Questa domanda ricorre nei sistemi informativi geografici, nelle interfacce grafiche, nell’infografica, nei sistemi di progettazione assistita dal computer e nella robotica. Vi sono inoltre casi più complessi, in cui l’occhio può essere tratto in inganno.
Il poligono è effettivamente semplice, ma il punto M è interno o esterno al poligono?
Il metodo del «raggio intersecante» ---------------------------------
L’algoritmo più semplice per stabilire se un punto è all’interno di una zona è il «ray crossing method», derivato dai lavori di Stig Nordbeck e Bengt Rystedt del 1967 in cartografia. Consiste nel tracciare una retta passante per il punto di cui si vuole conoscere la posizione. Partendo dall’esterno, si conta poi il numero di intersezioni con il poligono. Ogni volta che tale numero è dispari, siamo all’interno del poligono. L’uso di una retta orizzontale o verticale semplifica i calcoli.
Questo algoritmo è semplice da implementare. Occorre fare attenzione al caso in cui la retta passa per un vertice. Anche il caso in cui il punto da identificare sia molto vicino a un lato può risultare problematico. Esistono numerosi perfezionamenti di questo algoritmo, molto usato, per ridurne la complessità di calcolo.

Il punto M è interno al poligono perché la semiretta

interseca il poligono un numero dispari di volte.