Spin0us.net github

Localisation

Coordonnées dans un polygone

par spin0us le 19 avril 2013

Pour celles et ceux qui, comme moi, doivent travailler sur des systèmes de géolocalisation, voici une petite explication pour déterminer si un point de coordonnées GPS se situe, ou non, dans une zone polygonale.

Pour ce genre d'opération il existe plusieurs méthodes plus ou moins connues et plus ou moins efficace. Ici, nous allons nous attarder principalement sur deux d'entre elles : le calcul d'angles et l'algorithme ray casting.

Je ne vais pas m'attarder à vous décrire les deux méthodes car il y a suffisament d'informations sur les autres sites du web. Je vais me contenter de comparer les temps de calcul des deux méthodes appliquées au PHP.

Méthode 1 : Calcul d'angles

function Angle2D($x1, $y1, $x2, $y2) {
	$theta1 = atan2($y1,$x1);
	$theta2 = atan2($y2,$x2);
	$dtheta = $theta2 - $theta1;
	while ($dtheta > M_PI) $dtheta -= 2 * M_PI;
	while ($dtheta < -M_PI) $dtheta += 2 * M_PI;
	return $dtheta;
}

function pointIsInPolygon($polygon, $point) {
	$angle = 0;
	$n = count($polygon);
	for ($i=0;$i<$n;$i++) {
		$p1_h = $polygon[$i][0] - $point[0];
		$p1_v = $polygon[$i][1] - $point[1];
		$p2_h = $polygon[($i+1)%$n][0] - $point[0];
		$p2_v = $polygon[($i+1)%$n][1] - $point[1];
		$angle += Angle2D($p1_h,$p1_v,$p2_h,$p2_v);
	}
	if (abs($angle) < M_PI)
        return false;
	else
		return true;
}

Méthode 2 : Ray casting

function rayCrossesSegment($point, $a, $b) {
    $px = $point[1];
    $py = $point[0];
    $ax = $a[1];
    $ay = $a[0];
    $bx = $b[1];
    $by = $b[0];
    if($ay > $by) {
        $ax = $b[1];
        $ay = $b[0];
        $bx = $a[1];
        $by = $a[0];
    }
    if($px < 0) $px += 360;
    if($ax < 0) $ax += 360;
    if($bx < 0) $bx += 360;
    if($py == $ay || $py == $by) $py += 0.00000001;
    if(($py > $by || $py < $ay) || ($px > max($ax, $bx))) return false;
    if($px < min($ax, $bx)) return true;
    $red = ($ax != $bx) ? (($by - $ay) / ($bx - $ax)) : INF;
    $blue = ($ax != $px) ? (($py - $ay) / ($px - $ax)) : INF;
    return ($blue >= $red);
}

function pointIsInPolygon($polygon, $point) {
    $crossings = 0;
    for($i=0; $i < count($polygon); $i++) {
        $a = $polygon[$i];
        $j = $i + 1;
        if($j >= count($polygon)) $j = 0;
        $b = $polygon[$j];
        if(rayCrossesSegment($point, $a, $b)) {
            $crossings++;
        }
    }
    return ($crossings % 2 == 1);
}

Conditions de test

Pour comparer les deux méthodes, j'ai utiliser une polygone englobant l'europe et un point aléatoire qui se déplace dans et hors de cette zone. Il a alors suffit de boucler (10 000 et 100 000 itérations) sur l'appel de la fonction et de faire les relevés de compteur (opération répétée plus de 15 fois sur la même configuration afin de sortir les résultats extrèmes).

Résultats

Dans un premier, je m'attendais à voir une grosse différence dans les temps de calcul, la méthode Ray casting m'ayant été vendue comme plus performante. Mais non. L'écart n'est pas super énorme (de l'ordre de 10% en moyenne), mais c'est bien le calcul d'angle qui est toujours le plus rapide.

Conclusion: je vais rester sur les angles. Ca tombe bien, c'est déjà en place, donc moins de modifications que prévu