Le 5 mai 2012 14:52, Christian Quest <[email protected]> a écrit : > Sur l'exemple que tu indiquais où 18 géométries étaient possibles dont > 9 valides... ces 9 valides sont-elles équivalentes ? Si oui, ne > suffit-il pas d'en choisir une parmi les 9 ?
Non impossible d'en déterminer une : elles sont toutes valides au sens des polygones GIS générés où aucun noeud généré dans les polygones séparés n'est parcouru plus d'une fois. Et pourtant elles sont différentes au sens des surfaces délimitées (on ne sait plus quel polygone est interne ou externe, toutes les solutions sont possibles) ce qui fait qu'on ne sait plus tester si un point quelconque au milieu de tout ça fait partie ou non de la surface délimitée. On ne peut pas résoudre le problème par un algorithme de parcours de nœud en nœud en suivant les chemins pas à pas : cette méthode explose de façon combinatoire, même pour ne serait-ce que déterminer la première géométrie valide possible. La résolution vers les polygones les plus petits (méthode de la "scanline", utilisée par les algos de remplissages de surfaces polygonales pour un rendu en bitmap) est celle qui produira des dispositions de surfaces en damiers, et ce n'est pas toujours la bonne, et ne permet plus de détecter les intersections inattendues produites par les modifications dans JOSM et la création de noeuds d'intersections d'un clic souris. Elle a une complexité en O(n.log n) où n est le nombre de segments, mais elle ne marche bien qu'avec des segments de droite (après les avoir tous réorientés vers le bas et en éliminant les segments horizontaux), mais elle ne marche pas avec des ways multisegments qu'il faut d'abord éclater en liste de segments individuels (ce qui éclate les ways OSM). Il reste donc à utiliser une méthode de résolution simple basée sur les rôles des ways: la méthode des parcours de pas en pas fonctionne alors en temps quasi linéaire (en fonction du nombre de ways dans la relation) et sans même avoir à les éclater au préalable en liste de segments réorientés dans une direction verticale fixe. Elle sépare simplement les sous-ensembles de ways en groupes, puis traite chaque groupe séparément. _______________________________________________ Talk-fr mailing list [email protected] http://lists.openstreetmap.org/listinfo/talk-fr
