Discussion :

[Graffito]

Bonjour,

A partir d'un polygone non convexe comportant N points, je voudrais obtenir le contour "le meilleur" qui ne retiendrait qu'un (petit) nombre N de points.

Par exemple, réduction des contours d'un pays définis par 2345 points à 50 points maximum, avec un minimum d'écart entre le polygone résultant (50 points) et le polygone initial(2345 points).

L'objectif est de réduire les calculs ultérieurs d'appartenance aux polygones et de distances pour des simulations qui demandent beaucoup de calculs, mais ne sont pas trés sensibles à une perte de précision limitée.
Mais on ne peut toutefois pas aller jusqu'à accepter l'envelloppe convexe.

Sachant qu'aujourd'hui, j'utilise un "bricolage" minable pour le faire, auriez-vous des solutions ou des pistes pour faire mieux ?

[souviron34]

si tu appliquais la solution que j'ai donne dans ton autre post, tu aurais le comtrole de la "convexite", et donc du nombre de points.....

[Graffito]

C'est la première discussion que j'ouvre sur le sujet.
Te referes-tu à cette discussion :http://www.developpez.net/forums/sho...lygone+convexe

[ToTo13]

Bonsoir,

et si tu essayais de minimiser l'énergie entre ton nouveau contour et l'ancien :
- tu as un contour avec N points.
- tu n'en gardes que n.
- tu modifies par une méthode tabou tes n points.
- ta fonction d'énergie est la somme des distances entre ton ancien contour et le nouveau.

[pseudocode]

et si tu essayais de minimiser l'énergie entre ton nouveau contour et l'ancien

En théorie ça devrait marcher... Mais a mon avis, en pratique, ça va être dur de trouver une fonction d'énergie qui respecte la "sémantique" de l'image. Ça serait dommage de supprimer la Manche sous prétexte que c'est une petite excroissance sur la cote nord-ouest.

[Graffito]

Ça serait dommage de supprimer la Manche sous prétexte que c'est une petite excroissance sur la cote nord-ouest.

Effectivement, il faut laisser les excroissances pour le respect global des distances entre le polygone et l'ensemble des points du plan, ce qui est l'objectif premier.

Sachant cela, auriez-vous une idée pour une mesure de la qualité d'un contour réduit ?

L'idéal pour l'application prévue serait de prendre un ensemble de points (échantillon par quadrillage) situés à une distance inférieure à d (exemple 500 km) du polygone initial et de calculer la moyenne des divergences de la distance du point au polygone initial et au polygone réduit (en considérant que la distance est nulle si le point se trouve à l'intérieur).