IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage PHP Discussion :

Point dans un polygone : erreurs de précision [PHP 5.4]


Sujet :

Langage PHP

  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2011
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2011
    Messages : 17
    Par défaut Point dans un polygone : erreurs de précision
    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

  2. #2
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2011
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2011
    Messages : 17
    Par défaut
    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

  3. #3
    Membre chevronné

    Homme Profil pro
    Développeur Web
    Inscrit en
    Juin 2011
    Messages
    205
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur Web
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Juin 2011
    Messages : 205
    Billets dans le blog
    1
    Par défaut
    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 !
    si ce post vous a été utile, si votre problème est résolu.
    Pensez-y !
    __________________________________
    Doc officielle PHP | FAQ PHP | Cours PHP

  4. #4
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2011
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2011
    Messages : 17
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [C] présence d'un point dans un polygone
    Par adiiii dans le forum Développement 2D, 3D et Jeux
    Réponses: 15
    Dernier message: 16/11/2019, 09h14
  2. Point dans un polygone 3D
    Par silfride dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 22/08/2008, 11h04
  3. Point dans un polygone
    Par kerinel dans le forum Mathématiques
    Réponses: 5
    Dernier message: 17/10/2007, 12h23
  4. Point dans un polygone
    Par titelisette dans le forum ASP
    Réponses: 7
    Dernier message: 03/05/2007, 17h08
  5. Point dans un polygone
    Par titelisette dans le forum Général JavaScript
    Réponses: 5
    Dernier message: 27/04/2007, 11h51

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo