L’algorithme du point dans un polygone permet de vérifier par programme si un point particulier est à l’intérieur d’un polygone ou en dehors de celui-ci. Une façon commune d’aborder le problème est de compter combien de fois une ligne tracée à partir du point (dans n’importe quelle direction) croise le bord du polygone. Si la ligne et le polygone se croisent un nombre de fois pair (ou pas du tout), le point est à l’extérieur. S’ils se croisent un nombre de fois impair, le point est à l’intérieur. Ceci est vrai même pour des formes complexes qui ont beaucoup de coordonnées et ont donc un bord très précis.

Voyons un exemple d’image avant de passer au code.

Ici, les lignes tracées à partir du point 1 croisent le bord deux fois ou pas du tout, parce qu’il est à l’extérieur.

Le point 2 est à l’intérieur et donc les lignes croisent le bord une ou trois fois, en fonction de la direction.

Même dans des cas particuliers, tels que le point 3, nous voyons que cette méthode fonctionne : la ligne croise deux fois le bord et le point est donc à l’extérieur.

J’utilise cette approche dans le code PHP ci-dessous, qui retourne l’une de ces 4 valeurs possibles :

• inside (= dedans) si le point est à l’intérieur du polygone.
• outside (= dehors) si, vous l’aurez deviné, le point est à l’extérieur du polygone.
• vertex (= sommet) si le point se trouve exactement sur un sommet ET $pointOnVertex = true (ligne 2
• boundary (= bord) si le point est situé sur le bord. Si $pointOnVertex = false, la valeur boundary est également retournée quand le point est sur un sommet.

<?php
/*
Description: The point-in-polygon algorithm allows you to check if a point is
inside a polygon or outside of it.
Author: Michaël Niessen (2009)
Website: http://AssemblySys.com

If you find this script useful, you can show your
appreciation by getting Michaël a cup of coffee ;)
https://ko-fi.com/assemblysys

As long as this notice (including author name and details) is included and
UNALTERED, this code can be used and distributed freely.
*/

class pointLocation {
var $pointOnVertex = true; // Check if the point sits exactly on one of the vertices?

function pointLocation() {
}

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

// Transform string coordinates into arrays with x and y values
$point = $this->pointStringToCoordinates($point);
$vertices = array();
foreach ($polygon as $vertex) {
$vertices[] = $this->pointStringToCoordinates($vertex);
}

// Check if the point sits exactly on a vertex
if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) {
return "vertex";
}

// Check if the point is inside the polygon or on the boundary
$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'])) { // Check if point is on an horizontal polygon boundary
return "boundary";
}
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']) { // Check if point is on the polygon boundary (other than horizontal)
return "boundary";
}
if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) {
$intersections++;
}
}
}
// If the number of edges we passed through is odd, then it's in the polygon.
if ($intersections % 2 != 0) {
return "inside";
} else {
return "outside";
}
}

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]);
}

}
?>

Utiliser le code PHP du point dans un polygone

Définissez les valeurs du ou des point(s) et un tableau contenant les sommets du polygone (sous la forme “coordonnéeX coordonnéeY”), puis appelez la fonction pointInPolygon. Les premières et dernières coordonnées du polygone doivent être identiques, pour “boucler la boucle”.

Comme vous pouvez le voir dans l’exemple suivant, il est facile vérifier plusieurs points à la fois. Ce code fonctionne également avec des coordonnées négatives, pour le polygone ainsi que pour les points à vérifier.

 $point) {
    echo "point " . ($key+1) . " ($point): " . $pointLocation->pointInPolygon($point, $polygon) . "
";
}
?>

Ceci donnera : point 1 (50 70): vertex (= sommet) point 2 (70 40): inside (= dedans) point 3 (-20 30): inside (= dedans) point 4 (100 10): outside (= dehors) point 5 (-10 -10): outside (= dehors) point 6 (40 -20): inside (= dedans) point 7 (110 -20): boundary (= bord):