[OSM-dev-fr] Complexité algorithmique Problème insoluble de géométrie

[sly (sylvain letuffe)]

le sujet initial est sur la liste talk-fr, et concerne l'algorithme de 
construction de géométries compatibles OGC à partir d'une relation 
type=multipolygon dans OSM dont 2 polygones membres ont un point commun.

> le problème à résoudre pour énumérer les
> géométries possibles, dont chacune reste à valider selon les
> contraintes des polygones GIS, est topologiquement équivalent à celui
> du voyageur de commerce

On re-re-re-sort du cadre de la liste talk-fr, je bascule donc sur dev-fr, 
mais je ne pense pas qu'un tel algo soit d'une complexité égale à celle du TSP 
mais bien inférieure, tout en étant plus complexe que l'aglo actuellement 
rencontré dans osm2pgsql ou, peut-être, osm2gis.

-- 
sly (sylvain letuffe)