Sélection des points les moins alignés/proches

Bonjour,

j'ai un petit problème de sélection de points... que voilà :
- parmi un ensemble de N points (N petits, donc recherche exhaustive possible)
- je veux sélectionner quatre points qui sont les moins alignés (en priorité) et si possible qui sont aussi les moins proches.

*** Pour cela j'ai déjà imaginé de parcourir tous les quadruplés possible et pour chacun, calculer la sommes des angles formés par tous les triplets de points du quadruplés étudié.

*** Une variante serait de parcourir tous les quadruplés et le score de chacun serait l'angle minimum des triplets.

Cette dernière me m'assurerait de ne pas avoir les points alignés. Ensuite il faudrait que je discrimine pour rapport à la distance (ce qui est plus facile), comme par exemple calculer la somme des distances au barycentre de chaque quadruplé.


Est ce que quelqu'un verrait d'autres solutions ?
Merci par avance.

Bonsoir,

en quelle dimension travailles-tu?

Citation:

---

Envoyé par Aleph69

en quelle dimension travailles-tu?

---

juste 2, faudrait pas que ce soit trop dur ;-)

Bonsoir,

A votre place, je trierai les quadruplets suivant le résultat de cette valeur V :

V(A,B,C,D) = ABxCD + ACxBD + ADxBC.

Où AB est le vecteur AB, et x le produit scalaire.

Plus V est grand, plus les points sont non-alignés.

je propose :

• un quck sort sur les distances
  
  
• suivi d'une exploration à partir de la fin du tableau pour éliminer les points alignés

Maintenant, en prenant les critères d'alignement en tête :

• une régression linéaire
  
  
• suivie d'un tri par rapport à la distance à cette régression (et le delta)
  
  
• suivi d'un tri sur les distances point à point

Solutions à 2 balles, vite fait..

:oops:

Ca ressemble à la détection d'outlier dans un modèle linéaire. Je pense que le sujet à déjà été traité dans la littérature. :D

Perso, je vote pour RANSAC, ou une de ses variantes.

Citation:

---

Envoyé par mabu

A votre place, je trierai les quadruplets suivant le résultat de cette valeur V :
V(A,B,C,D) = ABxCD + ACxBD + ADxBC.
Où AB est le vecteur AB, et x le produit scalaire.
Plus V est grand, plus les points sont non-alignés.

---

Intéressant... je vais tester.

Citation:

---

Envoyé par souviron34

je propose :

• un quck sort sur les distances
• suivi d'une exploration à partir de la fin du tableau pour éliminer les points alignés

Maintenant, en prenant les critères d'alignement en tête :

• une régression linéaire
• suivie d'un tri par rapport à la distance à cette régression (et le delta)
• suivi d'un tri sur les distances point à point

Solutions à 2 balles, vite fait..
:oops:

---

Les solutions les plus simples sont souvent les meilleures, mais ici je risque de n'avoir que très peu de quadruplés. D'un point de vue statistique, je crains que le la régression soit instable car le nombre de points pour la construire est très/trop faible. De plus, la régression est intéressante mais je crains particulièrement l'alignement de triplets.

Citation:

---

Envoyé par pseudocode

Ca ressemble à la détection d'outlier dans un modèle linéaire. Je pense que le sujet à déjà été traité dans la littérature. :D
Perso, je vote pour RANSAC, ou une de ses variantes.

---

Mmm... détection d'outliers sur un aussi petit nombre de points... ça risque d'être difficile. Non ?

Citation:

---

Envoyé par ToTo13

Mmm... détection d'outliers sur un aussi petit nombre de points... ça risque d'être difficile. Non ?

---

Bah ca dépend de ta définition de petit. :P

A bien relire le PO, je me rend compte que les 4 points que tu cherches ne sont pas forcément des outliers comme je le pensais. Ca m'apprendra a lire une question aussi tard. En effet, il ne s'agit pas forcément de trouver les ponts qui correspondent le moins a un modèle linéaire.

Donc je retire ma suggestion initiale.

Est-ce que ca ne serait pas plutot des points situés aux extrémités des deux axes principaux ?

Citation:

---

Envoyé par pseudocode

Est-ce que ca ne serait pas plutot des points situés aux extrémités des deux axes principaux ?

---

Non plus :-(
Ceux sont des points répartis de manière quelconque, voire quasi aléatoire dans un espace 2D.
Et pour la suite de mon traitement, je dois prendre le quadruplé qui doit contenir les points les moins alignés possibles, car plus ils sont alignés, moins les résultats sont pertinents (erreurs d'approximation numérique).

Citation:

---

Envoyé par ToTo13

Non plus :-(
Ceux sont des points répartis de manière quelconque, voire quasi aléatoire dans un espace 2D.
Et pour la suite de mon traitement, je dois prendre le quadruplé qui doit contenir les points les moins alignés possibles, car plus ils sont alignés, moins les résultats sont pertinents (erreurs d'approximation numérique).

---

Je pense qu'il faudrait définir plus rigoureusement la notion de "4 points les moins alignés possibles".

En gros, La proposition de mabu semble etre la maximisation de l'aire du quadrilatère, celle se Souviron le maximum de variance et la mienne (PCA) le maximum de décorrélation.

Citation:

---

Envoyé par pseudocode

Je pense qu'il faudrait définir plus rigoureusement la notion de "4 points les moins alignés possibles".

---

En étant exact, il ne faut surtout pas que j'ai trois points alignés dans le quadruplé. Donc c'est pour ça que je parlais de quatre points les moins alignés possibles.

Pour chacun des quadruplets de point (P1...P4):

- tu prends i,j tel que d1=d(Pi,Pj) soit maximal
- tu calcules pour les 2 autres point Pk,Pl leurs distances à la droite (PiPj),
et tu notes d2 la somme de ces deux distances

Tu cherches alors le quadruplets tel que d1*d2 soit maximal par exemple.

Finalement, il semble que prendre le quadruplé qui possède le plus grand des plus petits angles formés par les triplets qui le compose, soit une bonne solution.


PS :

Citation:

---

Envoyé par mabu

A votre place, je trierai les quadruplets suivant le résultat de cette valeur V :
V(A,B,C,D) = ABxCD + ACxBD + ADxBC.
Où AB est le vecteur AB, et x le produit scalaire.
Plus V est grand, plus les points sont non-alignés.

---

Je suis très étonné, mais cette méthode n'a pas donné de bons résultats :-(

Citation:

---

Envoyé par ToTo13

Finalement, il semble que prendre le quadruplé qui possède le plus grand des plus petits angles formés par les triplets qui le compose, soit une bonne solution.

---

A mon tour d'être étonné... une condition uniquement angulaire donnera effectivement de bon résultats concernant l'éloignement mutuel des 4 points, mais ne tiendra pas compte réellement de la notion d'éloignement de DISTANCE.

Si tu prends une configuration de 4 points, que tu effectues une homothétie de rapport >1 et de centre la moyenne des 4 points, tu auras le même plus grands des petits angles, mais tes points seront "plus" éloignés...

Citation:

---

Envoyé par ToTo13

Je suis très étonné, mais cette méthode n'a pas donné de bons résultats :-(

---

Si le but était de trouver le quadrilatère d'aire maximale, j'aurais pris le Max des 3 produits plutot que la somme. J'aurais également essayé de normaliser un peu le résultat, par exemple en divisant par le périmètre.

Faudra que je teste pour voir ce que ca donne. ;)

Citation:

---

Envoyé par Nemerle

A mon tour d'être étonné... une condition uniquement angulaire donnera effectivement de bon résultats concernant l'éloignement mutuel des 4 points, mais ne tiendra pas compte réellement de la notion d'éloignement de DISTANCE.

---

C'est l'alignement qui me causait principalement des problèmes !

Bonjour,

je me demande s'il ne serait pas possible d'accélérer un peu le calcul en considérant d'abord les triplets de points et en regardant la qualité du triangle qu'ils forment. J'entends par qualité les mesures qu'on utilise habituellement dans les triangulations de Delaunay, par exemple le rapport entre l'aire du cercle inscrit dans un triangle et le diamètre de ce triangle. Si le triangle est trop aplati, alors ça n'est pas utile de considérer les quadruplets qu'il définit car, si j'ai bien compris, quatre points le moins alignés possible forment un carré parfait.

Citation:

---

Envoyé par Aleph69

je me demande s'il ne serait pas possible d'accélérer un peu le calcul en considérant d'abord les triplets de points et en regardant la qualité du triangle qu'ils forment. J'entends par qualité les mesures qu'on utilise habituellement dans les triangulations de Delaunay, par exemple le rapport entre l'aire du cercle inscrit dans un triangle et le diamètre de ce triangle. Si le triangle est trop aplati, alors ça n'est pas utile de considérer les quadruplets qu'il définit car, si j'ai bien compris, quatre points le moins alignés possible forment un carré parfait.

---

Effectivement, c'est un critère très intéressant. Il faut que je teste.