¿Cómo encontrar dos puntos más distantes?

Esta es una pregunta que me pidieron en una entrevista de trabajo hace algún tiempo. Y todavía no puedo encontrar una respuesta sensata.¿Cómo encontrar dos puntos más distantes?

La pregunta es:

se le da conjunto de puntos (x, y). Encuentra 2 puntos más distantes. Distante el uno del otro.

Por ejemplo, para los puntos: (0,0), (1,1), (-8, 5) - los más distantes son: (1,1) y (-8,5) porque la distancia entre ellos son más grandes de ambos (0,0) - (1,1) y (0,0) - (- 8,5).

El enfoque obvio es calcular todas las distancias entre todos los puntos y encontrar el máximo. El problema es que es O (n^2), lo que hace que sea prohibitivamente costoso para grandes conjuntos de datos.

Hay un acercamiento con los primeros puntos de seguimiento que están en el límite, y luego calcular distancias para ellos, bajo la premisa de que habrá menos puntos en el límite que "adentro", pero sigue siendo costoso y fallará en el peor de los casos.

Intenté buscar en la Web, pero no encontré ninguna respuesta sensata, aunque esto podría ser simplemente mi falta de habilidades de búsqueda.

Fuente

2010-04-29 Anonymous

¿Fue "hace algún tiempo" del orden de una hora? ;-) –

Si puede hacer la clasificación en O (nlogn), intente usarla. –

¿Qué quieres decir, Gabriel? Ordenar por qué? –

EDIT: Una forma es encontrar el casco convexo http://en.wikipedia.org/wiki/Convex_hull del conjunto de puntos y luego los dos puntos distantes son vértices de esto.

Posiblemente contestadas aquí: Algorithm to find two points furthest away from each other

también:

http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

Fuente

2010-04-29 10:06:01 zaf

Esa pregunta se trata de algoritmos de gráficos, no geometría computacional, ¿no? –

puede modelar el problema como un gráfico completo ponderado –

buena respuesta, me gusta. – ldog

Algoritmos de punto de frontera abundan (busque algoritmos de casco convexo). A partir de ahí, debería tomar O (N) el tiempo para encontrar los puntos opuestos más distantes.

Del comentario del autor: primero encuentre cualquier par de puntos opuestos en el casco, y luego camine alrededor de él en modo semicerrado. Dependiendo de los ángulos entre los bordes, tendrá que avanzar ya sea un andador o el otro, pero siempre tomará O (N) para circunnavegar el casco.

Fuente

2010-04-29 10:04:01

Ahora suponga que todos los N puntos dados están en el casco convexo. Todavía en)? –

Sí, porque primero encuentra cualquier par de puntos opuestos en el casco, y luego camina alrededor de él en modo semicerrado. Dependiendo de los ángulos entre vértices, tendrá que avanzar ya sea uno o el otro andador, pero siempre tomará O (N) para circunnavegar el casco. –

Por favor, publique un algoritmo completo para verificar qué puntos son los más lejanos, dado el casco convexo (un conjunto de nodos y su orden). –

A pocos pensamientos:

lo podría hacer en sólo los puntos que definen la envolvente convexa de su conjunto de puntos para reducir el número, ... pero todavía se ve un poco "no es óptima".

De lo contrario, puede haber un enfoque recursivo quad/oct-tree para unir rápidamente algunas distancias entre conjuntos de puntos y eliminar grandes partes de sus datos.

Fuente

2010-04-29 10:05:00 Adrien

Un punto de partida podría estar buscando problemas en el más cercano de punto, que han sido examinadas.Wikipedia enumera algunas opciones:

http://en.wikipedia.org/wiki/Closest_point_query

Fuente

2010-04-29 10:07:56

O http://en.wikipedia.org/wiki/Closest_pair_problem – zaf

Bueno, las soluciones para la base más cercana en dividir y conquistar, y no tengo idea de cómo aplicarlo para encontrar los puntos más apartados. –

Un algoritmo estocástico para encontrar el par más distante sería

elegir un punto al azar
Obtener el punto más lejano a él
Repetir una pocas veces
Eliminar todos los puntos visitados
Elegir otra r punto aleatorio y repetir algunas veces.

Usted está en O (n) siempre y cuando predetermine "algunas veces", pero no se garantiza que realmente encuentre el par más distante. Pero dependiendo de tu conjunto de puntos, el resultado debería ser bastante bueno. =)

Fuente

2010-04-29 10:20:23 Jens

Considere esto, y luego corrija o elimine su respuesta para que no obtenga votos a la baja: imagine que tiene un conjunto de puntos casi cuadrado, '{A = (0, 0), B = (10, 10), C = (10, 0), D = (0, 11)} '; los puntos más distantes son BD (distancia = 14.86); pero si intenta comenzar en A o B, sentirá la tentación de eliminar C (AC = BC = 10) o D (AD = 11, BD = 10.05) ya que están más cerca del vértice elegido que del vértice opuesto (AC = 14.14), ** mientras que en realidad la distancia más larga es realmente 14.86 **. – ANeves

@sr pt: En su ejemplo, CD son los puntos más distantes, no BD. Comenzando en A o B, uno siempre elegiría el otro en el paso 2, por lo que solo estos dos se eliminarán en el paso 4. – Jens

Esta pregunta se presenta en Introducción al algoritmo. Mencionó 1) Calcular casco convexo O (NlgN). 2) Si hay M vectex en Convex Hull. Entonces necesitamos O (M) para encontrar el par más lejano.

Encuentro estos enlaces útiles. Incluye análisis de detalles de algoritmo y programa. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html

Deseo que sea útil.

Fuente

2014-09-25 02:39:39 yuan

Está buscando un algoritmo para calcular el diámetro de un conjunto de puntos, Diam (S). Se puede demostrar que este es el mismo que el diámetro del casco convexo de S, Diam (S) = Diam (CH (S)). Así que primero calcule el casco convexo del conjunto.

Ahora tiene que encontrar todos los puntos antipodales en el casco convexo y recoger el par con la distancia máxima. Hay O (n) puntos antipodales en un polígono convexo. Por lo tanto, esto proporciona un algoritmo O (n lg n) para encontrar los puntos más lejanos.

Esta técnica se conoce como Pinzas giratorias. Esto es lo que Marcelo Cantos describe en su respuesta.

Si escribe el algoritmo con cuidado, puede hacerlo sin calcular los ángulos. Para obtener más información, consulte este URL.

Fuente

2014-11-28 16:55:15 saadtaame

Esto parece fácil si los puntos se dan en coordenadas cartesianas. Tan fácil que estoy bastante seguro de que estoy pasando por alto algo. ¡Siéntase libre de señalar lo que me estoy perdiendo!

Encuentra los puntos con los valores máximo y mínimo de sus coordenadas x, y, z (6 puntos en total). Estos deberían ser los puntos más "remotos" de todos los límites.
calcular todas las distancias (30 distancias únicas)
encontrar la distancia máxima
Los dos puntos que corresponden a esta distancia máxima son los que usted está buscando.

Fuente

2016-08-01 17:02:40

Obviamente O (N) por cierto ... –

Bien, entonces, después de pensarlo más, no está garantizado que los dos puntos más lejanos Doh! Sin embargo, le proporciona el tamaño mínimo de la región delineada por la matriz de puntos, que no será excedida por una escala de más de sqrt (2). Puede ser útil! –

-1

Dado un conjunto de puntos {(x1, y1), (x2, y2) ... (xn, yn)} encuentre 2 puntos más distantes.

Mi enfoque:

1). Necesita un punto de referencia (xa, ya), y será:
xa = (x1 + x2 + ... + xn)/n
ya = (y1 + y2 + ... + yn)/n

2). Calcule toda la distancia desde el punto (xa, ya) hasta (x1, y1), (x2, y2), ... (xn, yn)
El primer "punto más distante" (xb, yb) es el que tiene el distancia máxima

3). Calcule toda la distancia desde el punto (xb, yb) hasta (x1, y1), (x2, y2), ... (xn, yn)
El otro "punto más distante" (xc, yc) es el que tiene el distancia máxima

por lo que tiene sus puntos más distantes (xb, yb) (xc, yc) en O (n)

Por ejemplo, para los puntos: (0,0), (1,1), (- 8, 5)

1). Punto de referencia (xa, ya) = (-2.333, 2)

2). Calcular distancia:
desde (-2.333, 2) hasta (0.0): 3.073
desde (-2.333, 2) hasta (1,1): 3.480
desde (-2.333, 2) hasta (-8 , 5): 6.411
Así que el primer punto más distante es (-8, 5)

3). Calcular distancias:
desde (-8, 5) hasta (0,0): 9.434
desde (-8, 5) hasta (1,1): 9.849
desde (-8, 5) hasta (-8 , 5): 0
Así que el otro punto más distante es (1, 1)

Fuente

2016-09-07 04:43:31

primero ni siquiera has probado por qué es correcto, pero aquí hay un ejemplo de por qué está mal {{0, 0}, {10,0}, {- 10,0}, {0,17}} la respuesta correcta es 20, tu respuesta es ~ 19.72 – Vladp

-2

vistazo a triángulos de ángulo recto A- (x1, y1), B- (x2, y2) y la distancia b/w A y B es = sqrt [(| x1 | + | x2 |)^2 + (| y1 | + | y2 |)^2]

Fuente

2016-11-15 13:59:09

Él ya dijo que calcular las distancias entre todos ellos es demasiado expansivo ... –

Calcula la media de todos los puntos, mide la diferencia entre todos los puntos y la media, toma el punto la distancia más grande de la media y encuentra el punto más alejado de ella. Esos puntos serán las esquinas absolutas del casco convexo y los dos puntos más distantes. Hace poco hice esto para un proyecto que necesitaba cascos convexos confinados a planos infinitos dirigidos al azar. Funcionó muy bien.

Fuente

2017-03-10 18:27:05

¿Cómo encontrar dos puntos más distantes?

Respuesta

Cuestiones relacionadas