Bonjour,
J'ai implémenté une méthode pointInPolygon(Point $point) dans ma classe Polygon. Elle utilise le principe du Raytracing : dans un repère (O,x,y), un polygone P et un point M(Mx, My), on trace la demi-droite (xM]. Si celle-ci coupe le polygone un nombre impair de fois, alors le point est dans le polygone. Sinon, le point est à l'extérieur.
Ma méthode fonctionne dans la plupart des cas, mais dans des cas un peu plus tordus, elle se trompe et m'annonce des points en dehors alors qu'ils sont bien dans le polygone.
Voici la méthode en question :
Et dans son contexte : http://pastebin.com/cE9Af8ev : vous pouvez tester ce fichier directement. J'y ai mis un exemple de polygone complexe et deux points qui sont censés être dans la polygone.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 public function pointInPolygon(Point $testPoint) { $c = FALSE; for ($i = 0, $j = $this->_verticesCount; $i < $this->_verticesCount; $j = $i++) { if ( (($this->getVertices()[$i]->getY() > $testPoint->getY()) != ($this->getVertices()[$j]->getY() > $testPoint->getY())) && ($testPoint->getX() < ($this->getVertices()[$j]->getY() - $this->getVertices()[$i]->getY()) * ($testPoint->getY() - $this->getVertices()[$i]->getY()) / ($this->getVertices()[$j]->getY() - $this->getVertices()[$i]->getY()) + $this->getVertices()[$i]->getX()) ) $c = !$c; } return $c; }
Ces deux points sont censés être dans le polygone. Le premier ne fonctionne pas, le second est ok.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 var_dump($polygon->pointInPolygon(new Point(42.698684, 2.8958719))); var_dump($polygon->pointInPolygon(new Point(42.695306,2.696428)));
Vous pouvez visualiser le Polygone sur Google Earth et vous rendre compte que les deux points sont bien dans le polygone grâce à ce fichier KML : http://pastebin.com/ZT5SGNNB . Il vous suffit d'installer Google Earth et d'ouvrir ce fichier après l'avoir enregistré sous le nom "fichier.kml".
Merci d'avance de votre aide, si vous avez besoin d'une quelconque information supplémentaire, n'hésitez surtout pas, ce problème m'ennuie bien.
nakwakwak
Partager