Duplicaté possible:
Comment trouver le plus grand triangle dans Hull convexe de côté de la recherche de force bruteJ'ai un ensemble de points aléatoires à partir desquels je souhaite trouver le plus grand triangle de la région de la verticie de la région de Who's sur l'un de ces points.
Jusqu'à présent, j'ai compris que les verticales du triangle les plus importantes ne se situeront que sur les points externes du nuage de points (ou la coque convexe), donc j'ai programmé une fonction à faire juste que (en utilisant Graham Scan in Nlogn Time) .
Cependant, c'est là que je suis coincé. La seule façon de comprendre comment trouver le plus grand triangle de ces points consiste à utiliser la force brute à N ^ 3 fois, qui est toujours acceptable dans un boîtier moyen, car l'algorithme de coque convexe commence généralement à sortir la grande majorité des points. Cependant, dans le pire des cas, les points sont sur un cercle, cette méthode échouerait de manière misérablement.
Dose que quelqu'un connaisse un algorithme pour le faire plus efficacement?
Remarque: Je sais que CGAL a cet algorithme là-bas, mais ils n'entrent aucun détail sur la façon dont sa faite. Je ne veux pas utiliser des bibliothèques, je veux apprendre cela et le programmer moi-même (et me permettre également de le modifier exactement de la façon dont je veux que cela fonctionne, tout comme le scan de Graham dans lequel d'autres implémentations prennent en charge des points de colline Je ne veux pas).
5 Réponses :
En plus du sommet de ma tête, vous pourriez peut-être faire quelque chose d'impliquant la gridding / divisant la collection de points en groupes? Peut-être ... séparer les points en trois groupes (pas sûr de ce que le meilleur moyen de le faire dans ce cas serait, cependant), faisant quelque chose à supprimer ces points de chaque groupe qui sont plus proches des deux autres groupes que d'autres points de Le même groupe, puis en utilisant les points restants pour trouver le plus grand triangle pouvant être fait avoir un sommet dans chaque groupe? Cela ferait réellement le cas de tous les points sur un cercle beaucoup plus simple, car vous vous concentreriez simplement sur les points situés à proximité du centre des arcs contenus au sein de chaque groupe, comme ceux-ci seraient ceux de chaque groupe le plus éloigné de les deux autres groupes.
Je ne sais pas si cela vous donnerait le résultat approprié pour certains triangles / distributions de points, cependant. Il peut y avoir des situations où le triangle résultant n'a pas de superficie optimale, que ce soit parce que le regroupement et / ou le sommeil de sommet ne sont pas / n'est pas optimal. Quelque chose comme ça.
Quoi qu'il en soit, ce sont mes pensées sur le problème. J'espère que j'ai au moins été capable de vous donner des idées sur la façon de travailler dessus.
Voici une pensée sur la façon de le faire descendre à O (n 2 log n). Je ne sais pas vraiment rien de la géométrie informatique, je vais donc la marquer la communauté wiki; N'hésitez pas à améliorer cela.
Préprocéder la coque convexe en trouvant chaque point de la gamme de pentes de lignes à travers ce point de sorte que le jeu se situe complètement sur un côté de la ligne. Ensuite, inverser cette relation: construisez un arbre d'intervalle pour les pentes avec des points dans des nœuds de feuilles, de sorte que lorsqu'il soit interrogé avec une pente, vous trouvez les points de sorte qu'il y ait une tangente à travers ces points.
S'il n'y a pas d'ensembles de trois points colinéaires ou plus sur la coque convexe, il y a au plus quatre points pour chaque pente (deux de chaque côté), mais en cas de points colinéaires, nous pouvons simplement ignorer les points intermédiaires. < / p>
Maintenant, itérale à travers toutes les paires de points (P, Q) sur la coque convexe. Nous voulons trouver le point r tel que Triangle PQR a une superficie maximale. Prendre PQ comme base du triangle, nous voulons maximiser la hauteur en trouvant r aussi loin que possible de la ligne PQ possible. La ligne parallèle à PQ doit être telle que tous les points se trouvent sur un côté de la ligne, nous pouvons donc trouver un nombre délimité de candidats dans le temps O (journal n) à l'aide de l'arborescence d'intervalle de préconstruction.
Pour améliorer cela plus loin dans la pratique, faites une branche et liée à l'ensemble des paires de points: Trouvez une limite supérieure pour la hauteur de tout triangle (par exemple, la distance maximale entre deux points) et supprimer toute paire de points dont la distance multipliée par cette limite supérieure est inférieure au plus grand triangle trouvé jusqu'à présent.
"Je ne sais pas vraiment rien de la géométrie informatique, je vais donc la marquer la communauté wiki [.]" Étant dans le même bateau, je suppose que je marquerai le mien CW aussi.
Je ne sais pas pourquoi vous l'avez marqué comme un wiki communautaire, tout ce qui est utile pourrait être considéré comme une base pour une réponse réelle.
Je pense que le Les étriers rotatifs peuvent s'appliquer ici.
J'ai rencontré cela pendant mes recherches mais seulement en un coup d'œil. À première vue, je ne comprends pas bien comment cela pourrait fonctionner, quelle est votre ligne de pensée à ce sujet?
Utilisez le même algorithme qui calcule le diamètre: pour chaque bord de coque convexe, le point le plus éloigné de celui-ci définit le plus gros triangle avec ce bord comme base. Tournez une fois et trouvez le plus grand triangle dans l'ensemble. Mais ce n'est pas une preuve ...
Il serait donc calculer dans N ^ 2 fois. Amélioration significative. Malheureusement, rien ne garantit que le plus grand triangle aurait un avantage sur la coque. Prenez 6 points qui forment un hexagone parfait par exemple.
Que diriez-vous d'abandonner un point à la fois de la coque convexe? En commençant par la coque convexe, calculez la zone du triangle formé par chaque triple de points adjacents (P1P2P3, P2P3P4, etc.). Trouvez le triangle avec une zone minimale, puis laissez tomber le milieu des trois points qui formaient ce triangle. (En d'autres termes, si la plus petite zone triangle est P3P4P5, Drop P4.) Vous avez maintenant un polygone convexe avec N-1 points. Répétez la même procédure jusqu'à ce que vous restiez à trois points. Cela devrait prendre o (n ^ 2) temps.
Je ne serais pas du tout surpris s'il y a un cas pathologique où cela ne fonctionne pas, mais j'espère que cela fonctionnerait pour la majorité des cas. (En d'autres termes, je n'ai pas prouvé cela, et je n'ai aucune source de citer.)
Hmm, non, je ne pense pas que ce soit correct. Considérons un hexagone parfait. Nous savons que le plus grand triangle de là serait un triangle reliant tous les autres points. L'algorithme décrit commencerait d'abord en supprimant un point (peu importe quel point, ils sont tous identiques). Nous sommes laissés avec 5 points. Si l'algorithme supprime le point suivant, deux points à gauche ou à droite du point retiré, cela donnerait la bonne réponse. Toutefois, si cela enlevait le point opposé du point éliminé, cela donnerait une mauvaise réponse. Bon essayez cependant, me fait penser.
Je ne sais pas si cela aide, mais si vous choisissez deux points de la coque convexe et faites pivoter tous les points de la coque de sorte que la ligne de connexion des deux points soit parallèle à l'axe X, soit le point avec le Maximum ou celui avec la coordonnée Y minimale forme le triangle avec la plus grande surface avec les deux points choisis en premier.
Bien sûr, une fois que vous avez testé un point pour toutes les lignes de base possibles, vous pouvez le supprimer de la liste.
Quel est le nom de la routine dans cgal qui fait cela?
@andand: maximum_area_inscrid_k_gon_2, je pense.
@Faken: Le code source ne dit pas ce qu'est Algorithme CGAL :: MAXIMULT_AREA_INSCRIDED_K_GON_2 utilise. Pourtant, vous voudrez peut-être y jeter un coup d'oeil ( CGAL.ORG/ Manuel / Dernier / Inclure / cgal / extremal_polygon_2.h ) et voyez si vous pouvez reconstruire la logique.
@andand: Eh bien, je suis un ingénieur en mécanique en formant un code de programmeur professionnel, c'est comme traduire le français ... de toute façon, merci pour le point de départ, je vais voir ce que je peux faire de cela.
@Faken: Je n'ai pas vraiment regardé l'approche ci-jointe, mais cela semble être récursif. Je doute qu'ils inciteraient les frais généraux s'ils ne pouvaient pas avoir au moins O (n log n) la performance. Je vais le regarder d'autres et voir si je peux le comprendre.
@Faken: Il s'agit d'un dupliqué exact de Stackoverflow.com/questions/1621364/... . La réponse acceptée fournit une solution o (n) bien indiquée.
@andand: une méthode Simmilar à cela avait traversé mon esprit, mais je l'ai ignoré assez rapidement car je ne pouvais pas prouver que cela se retrouverait toujours avec le plus grand triangle (et pire, j'avais pensé que j'avais un exemple d'exemple Eh bien, que j'ai négligé de réellement tester sur papier). L'idée est extrêmement simple, merci de me le pointer, me donne une autre avenue à explorer, mais d'être honnête, j'ai toujours mes doutes, o (n) temps? Cela semble trop beau pour être vrai.
@Faken: C'est O (n) après Computing coque convexe, donc c'est O (nlogn) dans votre cas.
J'ai déjà une coque convexe, je voulais quelque chose qui était meilleur que N ^ 3 fois sur les points de la coque, donc il est vraiment dans O (n) temps. Cependant, je suis une perte sur la façon de fermer cette question, j'ai une réponse, mais ce n'est pas une réponse postée.
@Faken: Si vous le souhaitez fermé, vous pouvez le signaler pour une attention modérée que je suppose. Ou attendez juste que certains autres utilisateurs viennent le fermer. Il a déjà 2 votes (dont l'un est le mien). Votre question est essentiellement la même chose que l'autre question (qui a une réponse) et cette question doit être fermée comme une dupe de cela.
@faken ou répondez-y vous-même.