Ovvero come stabilire se un punto si trova o meno all'interno di un poligono

Durante l'elaborazione dei dati pubblicati su questo sito mi sono imbattuto nel problema di automatizzare la procedura di determinazione se un punto si trovi o meno all'interno di un poligono.

Quanto segue è la traduzione e sintesi dell'articolo pubblicato su Wikipedia inerente l'argomento.

Un semplice modo per determinare se un punto si trovi o meno all'interno di un poligono è verificare quante volte una semiretta partente dal punto in analisi interseca i bordi del poligono.

Esclusi i casi in cui il punto si trovi esattamente sul bordo o su di un vertice, o che il lato del poligono intersecato abbia lo stesso angolo della semiretta, il numero delle intersezioni sarà pari se il punto si trova all'esterno e dispari in caso contrario.

I casi particolari suddetti, per applicazioni i tipo geografico possono essere esclusi con relativa sicurezza.

Questo algoritmo è basato sulla semplice osservazione che se un punto si muove lungo una retta  che interseca il poligono partedo da infinito, questo si troverà dapprima all'esterno, quindi all'interno ed in seguito all'esterno, questo ciclo si ripeterà per una o più  volte a seconda della geometria del poligono in esame,
in ogni modo ogni due intersezioni esso sarà sicuramente all'esterno.








Lo script seguente, tratto da questo sito è una applicazione di quanto detto sopra in linguaggio PHP.


<?php
class pointLocation
{
// Controlla se il punto si trova esattamente su un vertice
var $pointOnVertex = true;

function pointLocation()
{
}

function pointInPolygon($point, $polygon, $pointOnVertex = true)
{
$this->pointOnVertex = $pointOnVertex;

// Trasformo le stringhe in arrays con valori per x e y (lat e lon)
$point = $this->pointStringToCoordinates($point);
$vertices = array();
foreach ($polygon as $vertex) {
$vertices[] = $this->pointStringToCoordinates($vertex);
}

// Controlla se il punto si trova esattamente su un vertice
if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) {
return "vertice";
}

// Controlla se il punto si trova all'interno del poligono o sul perimetro

$intersections = 0;
$vertices_count = count($vertices);

for ($i = 1; $i < $vertices_count; $i++) {
$vertex1 = $vertices[$i - 1];
$vertex2 = $vertices[$i];
if ($vertex1['y'] == $vertex2['y'] and $vertex1['y'] == $point['y'] and $point['x'] > min($vertex1['x'], $vertex2['x']) and $point['x'] < max($vertex1['x'], $vertex2['x'])) {
// Controlla se il punto si trova su un tratto orizzontale del perimetro
return "perimetro";
}
if ($point['y'] > min($vertex1['y'], $vertex2['y']) and $point['y'] <= max($vertex1['y'], $vertex2['y']) and $point['x'] <= max($vertex1['x'], $vertex2['x']) and $vertex1['y'] != $vertex2['y']) {
$xinters = ($point['y'] - $vertex1['y']) * ($vertex2['x'] - $vertex1['x']) / ($vertex2['y'] - $vertex1['y']) + $vertex1['x'];
if ($xinters == $point['x']) {
// Controlla se il punto si trova su un tratto del perimetro (non orizzontale)
return "perimetro";
}
if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) {
$intersections++;
}
}
}
// Se il numero delle intersezioni è pari allora il punto si trova all'esterno
if ($intersections % 2 != 0) {
return "interno";
} else {
return "esterno";
}
}


function pointOnVertex($point, $vertices)
{
foreach ($vertices as $vertex) {
if ($point == $vertex) {
return true;
}
}
}


function pointStringToCoordinates($pointString)
{
$coordinates = explode(" ", $pointString);
return array("x" => $coordinates[0], "y" => $coordinates[1]);
}
}

/*** Esempio ***/

$pointLocation = new pointLocation();
$points = array("7 8");
//$polygon = array("10 5", "10 10", "5 10", "5 5");


foreach ($points as $key => $point) {
echo "$key ($point) Si trova all'" . $pointLocation->pointInPolygon($point, $polygon) . "<br>";

echo "<br>";
}
?>