Étant donné un ensemble de points 2D X, je voudrais trouver une coque convexe constituée de n points maximum. Bien sûr, ce n'est pas toujours possible. Par conséquent, je recherche une coque convexe approximative composée de max. n points qui couvrent au maximum l'ensemble des points X.
Dit plus formellement, si F (H, X) renvoie le nombre de points de X que la coque convexe H recouvre, où | H | est la quantité de points à partir de laquelle la coque est construite, alors je cherche la quantité suivante:
H_hat = argmax_H F (H, X), st | H |
Une autre façon de considérer le problème est la tâche de trouver le polygone constitué de max. n coins d'un ensemble X de sorte qu'il couvre au maximum ledit ensemble X.
La façon dont je suis venu avec est la suivante:
X = getSet() \\ Get the set of 2D points
H = convexHull(X) \\ Compute the convex hull
while |H| > n do
n_max = 0
for h in H:
H_ = remove(h,H) \\ Remove one point of the convex hull
n_c = computeCoverage(X,H_) \\ Compute the coverage of the modified convex hull.
\\ Save which point can be removed such that the coverage is reduced minimally.
if n_c > n_max:
n_max = n_c
h_toremove = h
\\ Remove the point and recompute the convex hull.
X = remove(h,X)
H = convexHull(X)
Cependant , c'est une manière très lente de faire ceci. J'ai un grand ensemble de points et n (la contrainte) est petit. Cela signifie que la coque convexe d'origine contient beaucoup de points, d'où la boucle while itère pendant très longtemps. Existe-t-il un moyen plus efficace de procéder? Ou y a-t-il d'autres suggestions de solutions approximatives?
3 Réponses :
L'approche suivante pourrait peut-être fonctionner pour vous: Au départ, calculez la coque convexe H . Ensuite, sélectionnez un sous-ensemble de n points au hasard à partir de H , qui construit un nouveau polygone qui pourrait ne pas couvrir tous les points, appelons-le donc coque quasi-convexe Q . Comptez le nombre de points contenus dans Q (inliers). Répétez ceci un certain nombre de fois et conservez la proposition Q avec le plus d'inliers.
Cela semble un peu lié à RANSAC, mais pour cette tâche, nous n'avons pas vraiment de notion de ce qu'est une valeur aberrante, nous ne pouvons donc pas vraiment estimer le rapport de valeur aberrante. Par conséquent, je ne sais pas à quel point l'approximation sera bonne ni combien d'itérations vous aurez besoin pour obtenir un résultat raisonnable. Vous pouvez peut-être ajouter des heuristiques au lieu de choisir les n points purement au hasard ou vous pouvez avoir un seuil de combien de points doivent au moins être contenus dans Q puis arrêter lorsque vous atteignez ce seuil.
Modifier
En fait, après y avoir réfléchi, vous pouvez utiliser une approche RANSAC:
max_inliers = 0
best_Q = None
while(true):
points = sample_n_points(X)
Q = construct_convex_hull(points)
n_inliers = count_inliers(Q, X)
if n_inliers > max_inliers:
max_inliers = n_inliers
best_Q = Q
if some_condition:
break
Quelques idées.
Les points que nous excluons lors de la suppression d'un sommet se trouvent dans le triangle formé par ce sommet et les deux sommets adjacents à celui-ci sur la coque convexe. La suppression de tout autre sommet n'affecte pas l'ensemble des points potentiellement exclus. Par conséquent, nous n'avons qu'à recalculer la couverture deux fois pour chaque sommet supprimé.
En parlant de recalcul de la couverture, nous n'avons pas nécessairement à regarder à chaque point. Cette idée n'améliore pas le pire des cas, mais je pense que cela devrait être une grande amélioration dans la pratique. Maintenez un index des points comme suit. Choisissez un sommet aléatoire pour être la «racine» et regroupez les points par lesquels le triangle formé par la racine et deux autres sommets les contient (O (m log m) temps avec un bon algorithme). Chaque fois que nous supprimons un sommet non racine, nous unissons et filtrons les deux ensembles de points pour les triangles impliquant le sommet supprimé. Chaque fois que nous recalculons la couverture, nous ne pouvons scanner que des points dans deux triangles pertinents. Si jamais nous supprimons cette racine, choisissez-en une nouvelle et refaites l'index. Le coût total de cet entretien sera de O (m log ^ 2 m) dans l'attente où m est le nombre de points. Il est cependant plus difficile d'estimer le coût de la couverture informatique.
Si les points sont distribués de manière raisonnablement uniforme dans la coque, utilisez peut-être area comme proxy pour la couverture. Stockez les sommets dans une file d'attente prioritaire ordonnée par l'aire de leur triangle formée par leurs voisins (oreille). Chaque fois que nous supprimons un point, mettez à jour la zone d'oreille de ses deux voisins. C'est un algorithme O (m log m).
Ce qui suit ne résout pas la question de la manière dont je l'ai formulée, mais il a résolu le problème qui a engendré la question. Par conséquent, je voulais l'ajouter au cas où quelqu'un d'autre rencontrerait quelque chose de similaire.
J'ai étudié deux approches:
1) Considère la coque convexe comme un polygone et applique un algorithme de simplification de polygone dessus. L'algorithme spécifique que j'ai étudié était le Ramer-Douglas-Peucker Algorithme .
2) Appliquez l'algorithme décrit dans la question, sans recalculer la coque convexe.
Aucune des deux approches ne vous donnera (pour autant que je sache), la solution souhaitée au problème d'optimisation indiqué, mais pour mes tâches, elles ont suffisamment bien fonctionné.
H_hatdoit-il être composé de points originaux ou pouvez-vous en ajouter de nouveaux?Hé, j'ai ajouté la géométrie computationnelle comme balise car je connais au moins un expert qui la suit spécifiquement. Vous avez fait un excellent travail de marquage, j'ai donc dû abandonner «convexe». J'espère que ça va; vous pouvez effectuer les ajustements souhaités.
Une difficulté majeure est que la taille de la coque ne diminue pas de manière monotone lorsque vous supprimez des points.
Je doute que la solution optimale puisse être trouvée progressivement. Pensez au cas H = 3 et supposez que vous avez trouvé un triangle couvrant 5 points. Peut-être y en a-t-il un autre dans un endroit complètement différent, contenant 100 d'entre eux.
@YvesDaoust Vous avez probablement raison, mais les seules solutions exactes auxquelles je puisse penser sont beaucoup plus lentes que la proposition de la question.
@DavidEisenstat: ce que je veux dire, c'est que le problème ne semble pas avoir de belles propriétés locales. La modification d'un sommet peut modifier 90% de la couverture.
@YvesDaoust il est fort probable que l'algorithme que j'ai écrit ne calcule pas la solution optimale. C'est le meilleur que j'aie imaginé pour y penser. Je vais maintenant examiner les idées ci-dessous.
@DavidEisenstat Merci d'avoir ajusté les balises.
Je pensais à une approche où vous faites évoluer un polygone convexe de côtés H et essayez de l'étendre de manière gourmande pour augmenter la couverture. Mon autre remarque montre que cela est probablement sans espoir car le véritable optimum pourrait n'avoir absolument aucun point commun.