Polygone non convexe (le retour) : réduire le nombre de sommets

**Graffito** · 24/01/2008, 18h39

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** · 24/01/2008, 18h53

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** · 24/01/2008, 19h02

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** · 24/01/2008, 19h16

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** · 24/01/2008, 19h37

Envoyé par ToTo13

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** · 24/01/2008, 21h04

Ç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).

**souviron34** · 24/01/2008, 21h25

Envoyé par 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

oui

Envoyé par Graffito

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 la une mesure de la qualité de la réduction du nombre de points?

pour cela, tout depend. Avec l'algo que j'ai presente, tu passes forcement par les points "exterieurs". Pour le reste, c'est le pourcentage de "realisme".

Sinon tu peux faire un histo des distances par rapport au plus proche cote du polygone trouve, en faisant un histo par cote : tu "projettes" chaque point (delimite par les 2 perpendiculaires a ce segment) sur cet histo, et tu gardes la distance la plus courte (pour eviter justement les points interieurs). Puis tu calcules moyenne/ecart type pour le polygone au total....

**Graffito** · 24/01/2008, 21h35

tu passes forcement par les points "exterieurs".

Les points "exterieurs" sont-ils ceux de l'envellope convexe?
Même parmi ceux-là il faut en éliminer.

**souviron34** · 24/01/2008, 23h08

Envoyé par Graffito

Les points "exterieurs" sont-ils ceux de l'envellope convexe?
Même parmi ceux-là il faut en éliminer.

euh.....

La France sans la pointe bretonne, ou la limite Pas-de calais/Belgique, ou Alsace/Allemagne, etc etc, ca va etre dur....

Le minimum de tes points est le polygone convexe...

**pseudocode** · 24/01/2008, 23h10

Envoyé par Graffito

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

L'algorithme de Douglas-Peucker utilise la distance entre le point original et le segment du polygone simplifié. On peut deja commencer avec cela.

**Graffito** · 25/01/2008, 08h48

Le minimum de tes points est le polygone convexe...

Non, je peux aussi admettre de petites réductions de l'envellope qui impactent peu la "mesure" de qualité (moins que la suppression d'un point de non convexité).
Le minimum de mes points est un "petit" nombre N que je ne veux pas dépasser car l'impact sur les calculs ultérieurs sera en NxN.

Merci à tous pour vos pistes, je vais regarder Tabou et Douglas-Peucker.

**souviron34** · 25/01/2008, 14h09

je m'excuse d'insister

mais le minimum représentatif de points est le polygone convexe (d'ailleurs, c'est simple : pourquoi appelle-t-on la France "l'hexagone" ??

)

**Graffito** · 26/01/2008, 08h49

Le minimum représentatif de points est le polygone convexe

Un p'tit dessin valin mieux qu'un long discours...

Dans cet exemple, la solution de réduction la meilleure est la 2), soit la réduction "non convexe".

**Graffito** · 26/01/2008, 09h04

L'algorithme de Douglas-Peucker utilise la distance entre le point original et le segment du polygone simplifié

Bon, vous allez rire

, j'ai déjà implémenté quelque chose d'assez semblable à cet algorithme pour réduire le nombre de points d'une courbe avec comme paramètre la distance maximum du nouveau contour au contour initial.
La méthode donne d'ailleurs d'excellents résultats avec de bonnes performances.

Mais, j'ai pas du tout pensé à l'utiliser pour mes polygones.

Il suffit d'itérer la methode en augmentant/diminuant la distance admise jusqu'à trouver le nombre de points qui convient!

**souviron34** · 27/01/2008, 00h08

Envoyé par Graffito

Un p'tit dessin valin mieux qu'un long discours...

Dans cet exemple, la solution de réduction la meilleure est la 2), soit la réduction "non convexe".

si tu le dis

mais ça n'est pas celle que j'aurais choisie

je ne vois franchement pas l'intérêt d'nelver des points SGNIFICATIFS...

C'est contraire à toute méthode mathématique ou physique..

Et vu que l'humain applique des principes physiques, je doute...

**Graffito** · 27/01/2008, 10h52

mais ça n'est pas celle que j'aurais choisie
...
C'est contraire à toute méthode mathématique ou physique

Effectivement, tu aurais raison si pour le calcul de distance, on considérait qu'il faut le faire avec tous les points du plan.
Mais, dans mon cas, au delà d'une certaine distance limite, ce calcul n'est plus pertinent. Mes polygones représentant des limites de volumes (espace aérien) situés au-dessus d'une sphère (la terre), cette distance limite est l'horizon radio-électrique (100 à 400 km approximativement proportionnel à la racine carrée de la hauteur) au-delà duquel la propagation des ondes chutes abruptement.

**souviron34** · 27/01/2008, 17h46

et ??

je ne vois toujours aucune raison... : prendre au minimum les espaces convexes permettrait la complétude de l'espace, avec éventuellement des recouvrements. Prendre ta solution 2 évite les recouvrements, mais introduit des "non-zones". Ce problème me semble NETTEMENT plus grave que les recouvrements, qui peut être traité facilement ultérieurement (avec la direction de l'avion).

m'enfin c'est moi...

**Graffito** · 27/01/2008, 18h08

et ??

Je pensais que mon message répondait à ton souci de la réalité physique.

L'important est de minimiser les divergences avec le polygone initial lors de mesures de distances avec le polygon réduit lors de simulations. Il vaut parfois mieux enlever un point extérieur (appartenant au contour convexe) qu'un point intérieur.

De plus, même en ne gardant que le contour convexe, pour atteindre le nombre de points recherché, il faudra peut-être enlever des points.

La bonne solution théorique est la solution qui minimise les écarts de distances par rapport à un point de test quelquonque situé dans un certain rayon autour du polygone convexe, et en supposant une distribution de points de tests homogène.

Ps: je n'ai aucune notion de mobile dans le problème à traiter, juste des distances.

**souviron34** · 27/01/2008, 18h17

tu as tes raisons et je te les laisse, ainsi que la reponsabilité qui va avec.

Mais je maintiens que la solution "mathématique" que tu prends (réduire le nombre de points en minimisant la divergence) oublie un aspect essentiel de la fonctionalité demandée : garder la sécurité, et donc ne pas engendrer de trous.

Donc pour moi , vu de l'extérieur, sur le problème de l'espace aérien, c'est la combinaison des 2 conditions qui m'apparaitrait importante.

Mais toi et ta société êtes responsables de vos produits, je pense. Donc c'est "vous qui voyez"...

PS: d'ailleurs, je ne vois pas très bien la raison d'avoir à réduire le nombre de sommets d'un polygone défini physiquement.....