[OSM-talk-fr] Problème insoluble de géométrie.

[Philippe Verdy]

Le 5 mai 2012 14:52, Christian Quest <cquest at openstreetmap.fr> 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.