Discussion :

[victor.racine]

Bonjour a tous,

J'ai un nuage de point qui peut aller jusqu'à 100000 points. Chaque point est défini par deux valeurs numériques X et Y. Je cherche à déterminer LE polygone convexe de surface minimale incluant une fraction fixe du nuage de point. Par exemple, on cherche le plus petit polygone incluant 90% des points. Je ne cherche pas de solution exacte car ce serait trop long à calculer, je cherche une bonne approximation.

J'ai pensé faire une méthode style level-set en flouant et mappant le nuage de point sur une grille carrée. Mais j'ai peur que la grille doivent être extrêmement grande pour obtenir un résultat correct.

Je pensais aussi utiliser un algo de densité comme le dBScan mais les paramètres du dBScan ne sont qu'indirectement liés à la fraction de point dans le cluster. De plus le dBScan n'inclue pas de notion de convexité.

Avez vous des idées ?
Merci
Victor

[pseudocode]

De prime abord, je dirais de tracer l'enveloppe convexe du nuage global, puis de retirer le point de l'enveloppe qui à le minium de densité locale. Et recommencer jusqu'a avoir retiré le nombre adéquat de points.

[souviron34]

Je cherche à déterminer LE polygone convexe de surface minimale incluant une fraction fixe du nuage de point.

Pour répondre simplement, il n'y en a pas...


Comment veux-tu déterminer les bons points à éliminer ???


Basée sur quoi, la sélection ? comme le dit pseudocode, la densité ? la distance ? par rapport aux voisins ? au barycentre ??

Apprend à poser les bonnes questions, et tu auras déjà 50% de la réponse.. On t'aidera pour le reste..


Donc il n'y a pas UN polygone répondant à la question.. Il y en a une foultitude, suivant tes critères d'élimination des points... ou d'angles du polygones, ....

[Nemerle]

De prime abord, je dirais de tracer l'enveloppe convexe du nuage global, puis de retirer le point de l'enveloppe qui à le minium de densité locale. Et recommencer jusqu'a avoir retiré le nombre adéquat de points.

Marche pas... cf. dessin ci-joint:



Le principe de minimum de densité local ne te permet pas de décider si tu enlèves dans le rectangle de gauche ou droite...

Je procèderai par algo génétique, ça marche très bien avec ce genre de problème (convergence très rapide).

[victor.racine]

Bonjour et merci pour vos réponses.

à Pesudo code: merci pour cette piste. C'est vrai qu'en rognant le polygone là où la densité locale est faible on devrait après quelques itérations arriver à n'inclure que pourcentage de points désiré. Par contre je ne vois pas exactement comment définir le rayon de la fenêtre de voisinage pour le calcul de la densité locale, ni comment choisir la la distance de rognage. Probablement que le rayon de la fenêtre de voisinage peut être égal à la distance de rognage.
Je vais essayer de tâtonner dans cette direction pour voir ce que ça donne.

à souviron34: merci de m'apprendre à me poser les bonnes questions ! Je suis d'accord qu'il n'existe pas UN polygone convexe incluant une fraction fixe du nuage de point. Par contre, bien que je ne sache pas en faire la démonstration, je pense bien qu'il existe UN polygone convexe de surface minimale incluant une fraction fixe du nuage de point. La minimisation de la surface étant le critère de sélection.
Maintenant je suis d'accord qu'il n'y a surement pas de methode de complexité acceptable permetant de trouver l'optimum. C'est pourquoi dans mon post j'ai dis :

Je ne cherche pas de solution exacte car ce serait trop long à calculer, je cherche une bonne approximation

Je n'ai peut être pas été clair dans la formulation du problème: je ne cherche pas LE meilleur polygone mais une bonne approximation de ce polygone.

Merci

[victor.racine]

Bonjour Nemerle,

Je ne comprends pas bien ton explication. Tu veux dire que si les densité à gauche et à droite sont les mêmes alors on ne sait pas décider par lequel commencer ? C'est ça que tu veux dire ?

Pour les algo génétiques je suis d'accord avec toi mais j'aurais préféré une implémentation un peu plus simple quitte à compromette un peu la qualité du résultat.

Merci
Victor

[Nemerle]

Tu veux dire que si les densité à gauche et à droite sont les mêmes alors on ne sait pas décider par lequel commencer ? C'est ça que tu veux dire ?

oui!

[pseudocode]

Le principe de minimum de densité local ne te permet pas de décider si tu enlèves dans le rectangle de gauche ou droite...

Oui, ce n'est pas décidable. Mais bon, quand on veut une approximation, il faut bien faire des choix.

[souviron34]

alors si je reprend l'idée de départ de pseudocode, un algo me semblerait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
prendre le polygone convexe entourant le total des points
    éliminer l'angle le plus obtus
    calculer le nb de points situés entre les 2, et en déduire le % de points restants

itérer

Mais on n'aura sans doute pas un % exact...


d'où ma remarque sur l'élimination des points...

PS: si on avait un polygone concave, ce serait enlever l'angle le plus aigu...

[pseudocode]

Mon idée de départ était de se servir du fait que tous les points sont forcément contenus dans l'enveloppe convexe:

Prenons N=100 points.

1. Si je prend l'enveloppe convexe, elle contient N=100 points , soit 100% du total.

2. Si je retire un des points de l'enveloppe convexe, il me reste N-1=99 points.

3. Si je prend l'enveloppe convexe de ces N-1 points, elle contient N-1=99, soit 99/100 = 99% du total.

et ainsi de suite.

Donc, dans cet exemple, si on veut garder 90% de points, il faut itérer 10 fois

[souviron34]

Donc, dans cet exemple, si on veut garder 90% de points, il faut itérer 10 fois

je suis bien d'accord...


Mais comme notre cher ami ne donne pas d'indications sur quels sont les points à enlever, sur quels critères, on n'en sait pas plus...


Si par exemple je calcule le barycentre et j'enlève les 10 points les plus proches, j'aurais toujours 90% de points, mais quid du polygone ? Je peux aussi enlever les 9 points les plus proches du premier point enlevé...






Je pense qu'il manque soit une indication, soit que ce n'est pas vraiment le problème...

[Zavonen]

Pourquoi ne pas procéder en deux temps:
Tout d'abord une dichotomie.
On suppose tous les points dans un rectangle initial R0.
On partage R0 en deux dans le sens de la hauteur et on compte combien il y a de points à gauche et combien à droite. On le partage ensuite dans le sens de la largeur et on compte combien il y a de points au dessus et en dessous.
On désigne par R1 la moitié de R0 qui contient le plus de points dans ce partage (max de 4 quantités donc). On construit ensuite R2 à partir de R1 comme R1 à partir de R0 et on itère jusqu'à obtenir le pourcentage voulu de points.
On mémorise à chaque fois le nombre n1 de points dans R1, le nombre n2 dans R2, etc...
On est certain ainsi de toujours sélectionner les zones de plus forte densité.
Ensuite, quand on a atteint le pourcentage voulu on fait une enveloppe convexe et basta.

[Graffito]

Une piste pour réduire le temps de calcul:

• diviser la zone en pavés carrés,
• pondérer les centres des carrés par le nombre de points contenus dans chaque carré.

En utilisant cette optimisation, on pourrait utiliser l'algo semblable à celui proposé par Pseudocode :

• calcul de l'enveloppe convexe sur les centres des carrés,
• suppression du point P de l'enveloppe convexe ayant la plus faible pondération,
• itération (calcul de l'enveloppe convexe et suppression de P) jusqu'à ce que les poids des centres des carrés enlevés correspondent au nombre de points à éliminer.

Un pavage hexagonal serait en théorie un peu meilleur, mais compte tenu de la complexité des calculs résultant, réduire la taillle des carrés sera plus avantageux.