sélection d'un sous ensemble de points en 2D

**victor.racine** · 12/08/2010, 12h08

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** · 12/08/2010, 14h21

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.

**Nemerle** · 13/08/2010, 11h22

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

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

**pseudocode** · 13/08/2010, 11h58

Envoyé par Nemerle

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** · 14/08/2010, 11h38

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** · 14/08/2010, 13h49

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** · 12/08/2010, 23h04

Envoyé par victor.racine

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, ....

**victor.racine** · 13/08/2010, 11h26

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** · 13/08/2010, 11h36

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