Discussion :

[nakwakwak]

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 :

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

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
var_dump($polygon->pointInPolygon(new Point(42.698684, 2.8958719)));
var_dump($polygon->pointInPolygon(new Point(42.695306,2.696428)));

Ces deux points sont censés être dans le polygone. Le premier ne fonctionne pas, le second est ok.

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

[nakwakwak]

Bonjour,
Bon, je me réponds à moi-même. J'ai refait mes calculs à la main en ne faisant confiance qu'à moi-même, et je suis arrivé à quelque chose qui fonctionne en réécrivant mes équations et en les retransposant.

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())) &&
             (((($this->getVertices()[$j]->getX() - $this->getVertices()[$i]->getX()) / ($this->getVertices()[$j]->getY() - $this->getVertices()[$i]->getY())) * ($testPoint->getY() - $this->getVertices()[$i]->getY()) + $this->getVertices()[$j]->getX()) < $testPoint->getX()) )
               $c = !$c;
            }
 
        return $c;
    }

Edit : Non, ça ne fonctionne toujours pas en fait. C'est toujours aussi imprécis (mais pas au même endroit). C'est à me rendre fou . Je vous en supplie, aidez-moi, je vous donnerai 1Milliard d'euros.

nakwakwak

[k'amm]

Je te conseille d'essayer de simplifier ton modèle petit à petit pour mieux voir où se situe le problème. Vu le nombre de cas possibles et de tests que tu fais, pour trouver celui qui foire...

Essaies de repartir de ton modèle théorique en l'éprouvant avec les valeurs qui ne passent pas le test PHP ?
Le plus important est de bâtir l'algo, l'implémentation viendra ensuite plus simplement (et n'hésites pas à mettre tout plein de traces en décomposant tes tests pour bien voir l'endroit où ça coince) !


...Sinon tu as un tutoriel qui propose une implémentation en PHP (à remettre au goût du jour et à adapter selon ton besoin bien entendu) du modèle de Ray tracing : http://code.dawnofthegeeks.com/2009/...o-ray-tracing/

Bon courage !

[nakwakwak]

Salut, merci de ta réponse.

J'ai suivi tes conseils et j'ai tout refait depuis le départ et j'ai fini par trouver LES problèmeS. Il faut dire que hier soir, il était tard et j'étais au bord de la crise de nerfs. Pas moyen de faire quoi que ce soit de cohérent dans cet état. Ça m'apprendra à être maniaque. Au bout d'un moment, il faut savoir s'arrêter, aller se coucher et reprendre le lendemain.
Après avoir tout refait, je me suis retrouvé avec exactement le même type de problèmes. Je me suis lancé dans un débogage profond avec l'affichage de tous les segments, et une comparaison efficace avec Google Earth pour voir les points, les détections, les segments, les résultats qui allaient et ceux qui allaient pas.

Premier problème : les coordonnées étaient issues d'un fichier KML et j'aurais dû lire la doc de ce langage : les coordonnées sont de la forme LONGITUDE,LATITUDE (si vous regardez bien, moi je fais des trucs bizarres avec la chaîne ).
Second problème : La longitude, c'est l'axe des X et la latitude, c'est l'axe des Y. En l'occurrence, ça m'arrange bien pour la clarté du code et je faisais l'inverse.

Du coup, avec ces deux problèmes j'avais quelque chose de vraiment bizarre ; une sorte de rayon qui partait du bas mais qui était analysé à l'horizontal et un polygone qui se rapprochait du bon, mais qui n'était pas bon ^^ . Tout fonctionne bien maintenant .

nakwakwak