Étant donné un ensemble de points, comment puis-je trouver les deux points les plus éloignés l'un de l'autre? [dupliquer]

Question

  

Double possible:
   Plus grand ensemble de points de la deuxième dimension linéaire

Je pourrais calculer la distance entre chaque point et prendre le plus grand, mais cela ne semble pas être un moyen très efficace de le faire quand il y a un grand nombre (& 1000) de points.

Remarque: ceci est destiné à l'iPhone, je n'ai donc pas beaucoup de puissance de traitement.

Answer 1

Vous demandez de calculer le diamètre de l'ensemble. La technique standard consiste tout d'abord à calculer la coque convexe, ce qui réduit le problème de la recherche du diamètre d'un polygone convexe. Même dans le cas où vous n'éliminez aucun point, ces informations ajoutées sont exactement ce qui est nécessaire pour résoudre le problème efficacement. Cependant, trouver le diamètre d'un polygone convexe n'est pas entièrement trivial; plusieurs articles publiés avec des algorithmes pour cette tâche se révèlent incorrects.

Voici une discussion passablement lisible d'un algorithme O (n) correct pour la tâche (où n est le nombre de points de la coque convexe).

Notez également que l’iphone n’est pas limité; Une implémentation soigneusement écrite de l'algorithme, même naïf, peut gérer 1 000 points en moins d'un dixième de seconde. Bien sûr, utiliser le bon algorithme vous permettra d'aller beaucoup plus vite =)

Answer 2

Pourquoi ne pas simplement calculer la la coque convexe des points? En fonction de votre algorithme , il faut soit O (n) ou O (n log n) temps et élimine tous les points intérieurs de la considération. Ensuite, vérifiez seulement ces points les plus éloignés pour trouver les deux qui sont les plus éloignés.

Answer 3

Commencez par le point dont la coordonnée x est la plus basse. (Appelez-le Point X) Construire un ensemble de " points de démarcation "    en commençant par le point x et la ligne verticale passant par le point, il ne devrait pas y avoir d'autres points à gauche de PointX) recherchez le point suivant dans la limite en faisant tourner la ligne lentement dans le sens des aiguilles d'une montre (ou dans le sens inverse des aiguilles d'une montre) jusqu'à ce que la ligne touche un autre point (voir ci-dessous). ). Ajoutez ce point à l'ensemble et répétez l'opération avec le point suivant pour obtenir le suivant, jusqu'à ce que vous reveniez au point x d'origine. Vous avez maintenant un ensemble de points formant la limite de l’ensemble complet. Comparez la distance entre chaque paire dans cet ensemble réduit pour trouver la paire la plus éloignée.

Pour "faire pivoter la ligne" (pour trouver chaque point limite séquentiel), prenez le point qui est "le plus éloigné" dans la direction perpendiculaire à la ligne utilisée pour le dernier point de limite et créez une nouvelle ligne entre le dernier point de limite et celui "next". point. Ensuite, vérifiez qu’il n’ya pas d’autres points dans la nouvelle direction perpétuelle formée par cette nouvelle ligne. S'il n'y a pas d'autres points "Furthur out" dans la section de salissure qui est perpendiculaire à cette ligne ou à la dernière ligne, c’est le bon choix pour le prochain point de limite. Si ce point existe, passez à celui-ci et relancez le test.

Answer 4

Voir ces pages (celle-ci). liens vers et les pages accessibles en cliquant sur les liens "suivants" sur le calcul du diamètre de la coque convexe d'un ensemble de points.

Mon résumé rapide:

1. calculez un ensemble de points dans une coque convexe (= O (n log n), le seul moment où vous obtenez O (n) est si vous triez d'abord la liste qui prend de toute façon O (n log n))
2. commander le long des limites (vous l'obtenez gratuitement si vous utilisez un analyse Graham pour # 1)
3. utilisez l'un des algorithmes de diamètre O (n) pour rechercher les points antipodes ayant le plus grand diamètre. L'algorithme de Shamos me convient bien, car il s'agit d'un des algorithmes de rotation des compas .