Comment trouver deux points les plus éloignés?
C'est une question qu'on m'a posée lors d'un entretien d'embauche il y a quelque temps. Et je n'ai toujours pas trouver réponse sensée.
Question Est:
on vous donne un ensemble de points (x,y). Trouver 2 points les plus éloignés. Éloignés les uns des autres.
par exemple, pour les points: (0,0), (1,1), (-8, 5) - les plus éloignés sont: (1,1) et (-8,5) parce que la distance entre eux est plus grande de(0,0)-(1,1) et(0,0)-(-8,5).
l'approche évidente est de calculer toutes les distances entre tous les points, et de trouver maximum. Le problème est qu'il est O (N^2), ce qui le rend prohibitif pour les grands ensembles de données.
il y a une approche avec d'abord des points de cheminement qui sont sur la frontière, puis le calcul des distances pour eux, sur la prémisse qu'il y aura moins de points sur la frontière que "à l'intérieur", mais il est encore coûteux, et échouera dans le pire des cas.
a essayé de chercher sur le web, mais n'a pas trouvé de réponse sensée - bien que ce pourrait être simplement mon manque de compétences de recherche.
11 réponses
EDIT: une façon est de trouver le convex coque http://en.wikipedia.org/wiki/Convex_hull de l'ensemble des points et ensuite les deux les points distants en sont les sommets.
peut-être répondu ici: algorithme pour trouver deux points les plus éloignés l'un de l'autre
Aussi:
point Limite algorithmes abondent (cherchez l'enveloppe convexe des algorithmes). De là, il faut du temps pour trouver les points opposés les plus éloignés.
D'après le commentaire de l'auteur: trouvez d'abord n'importe quelle paire de points opposés sur la coque, puis marchez autour d'elle en demi-serrure-étape de la mode. Selon les angles entre les bords, vous devrez avancer soit un marcheur ou l'autre, mais il faudra toujours O(N) pour contourner la coque.
trouver la moyenne de tous les points, mesurer la différence entre tous les points et la moyenne, prendre le point la plus grande distance de la moyenne et trouver le point le plus loin de lui. Ces points seront les coins absolus de la coque convexe et les deux points les plus éloignés. J'ai récemment fait ceci pour un projet qui avait besoin de coques convexes confinées à des plans infinis dirigés au hasard. Il a travaillé beaucoup.
cette question est présentée à L'introduction de L'algorithme. 1) calculer la coque convexe O (NlgN). 2) S'il y a M vectex sur la coque convexe. Il faut O (M) pour trouver la paire la plus éloignée.
je trouve ces liens utiles. Il comprend une analyse de l'algorithme et le programme. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html
J'espère que ce sera utile.
vous recherchez un algorithme pour calculer le diamètre d'un ensemble de points, Diam(s) . On peut montrer que c'est le même que le diamètre de la coque convexe de S, Diam(s) = Diam(CH(S)) . Donc d'abord calculer l'enveloppe convexe de l'ensemble.
maintenant vous devez trouver tous les points antipodaux sur la coque convexe et choisir la paire avec la distance maximale. Il y a O (n) points antipodaux sur un polygone convexe. Cela donne donc un algorithme O(N lg n) pour trouver les points les plus éloignés.
cette technique est connue sous le nom de Calepers rotatifs . C'est ce que Marcelo Cantos décrit dans sa réponse.
si vous écrivez l'algorithme avec soin, vous pouvez le faire sans calculer les angles. Pour plus de détails, voir URL .
un algorithme stochastique pour trouver la paire la plus éloignée serait
- choisir un point au hasard
- Obtenez le point le plus lointain
- répéter plusieurs fois
- supprimer tous les points visités
- choisissez un autre point aléatoire et répétez plusieurs fois.
Vous êtes en O(n) tant que vous prédéterminer "quelques fois", mais il n'est pas garanti trouver la paire la plus éloignée. Mais selon votre ensemble de points le résultat devrait être assez bon. = )
Juste quelques pensées:
vous pourriez regarder seulement les points qui définissent la coque convexe de votre ensemble de points pour réduire le nombre,... mais il semble encore un peu "sous-optimale".
sinon il pourrait y avoir une approche récursive quad/oct-tree pour rapidement lié quelques distances entre les ensembles de points et d'éliminer de grandes parties de vos données.
un point de départ pourrait être d'examiner les problèmes les plus rapprochés, qui ont été examinés. Wikipedia liste quelques options:
Cela semble facile, si les points sont donnés en coordonnées Cartésiennes. Si facile que je suis presque sûr que j'oublie quelque chose. N'hésitez pas à me faire remarquer ce que je rate!
- trouver les points avec les valeurs Max et min de leurs coordonnées x, y et z (6 points au total). Ces points devraient être les plus" éloignés " de tous les points limites.
- calculer toutes les distances (30 distances uniques)
- trouver le max distance
- les deux points qui correspondent à cette distance maximale sont ceux que vous recherchez.
compte tenu d'un ensemble de points {(x1,y1), (x2,y2) ... (xn,yn)} trouver 2 points les plus éloignés.
mon approche:
1). Vous avez besoin d'un point de référence (XA,ya), et il sera:
xa = (x1 + x2 +...+ xn) / n
ya = (y1 + y2 +...+ yn) / N
2). Calculer toute la distance entre le point (XA, ya) et (x1,y1), (x2,y2),...(xn,yn)
Le premier "point le plus éloigné" (xb, yb) est celui avec la distance maximale.
3). Calculer toute la distance entre le point (xb,yb) et (x1, y1), (x2, y2),...(xn,yn)
L'autre "plus lointaine" (xc,yc) est la distance maximale.
donc vous avez obtenu vos points les plus éloignés (xb,yb) (xc,yc) en O (n)
par exemple, pour les points: (0,0), (1,1), (-8, 5)
1). Point de référence (XA, ya) = (-2,333, 2)
2). Calculer les distances:
de (-2,333, 2) à (0,0) : 3.073
de (-2,333, 2) à (1,1) : 3.480
de (-2,333, 2) à (-8, 5) : 6.411
Donc le premier point le plus éloigné est (-8, 5)
3). Calculer les distances:
de (-8, 5) à (0,0) : 9.434
de (-8, 5) à (1,1) : 9.849
de (-8, 5) à (-8, 5) : 0
Donc l'autre point le plus éloigné est (1, 1)
regardez les triangles d'angle droit A - (x1, y1), B - (x2, y2) et la distance b / w A et B est = sqrt [(|x1|+|x2|)^2 + (|y1|+|y2/)^2]