algorithm - ¿Cómo encontrar dos puntos más lejanos?
language-agnostic geometry (11)
EDITAR: 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 respondido aquí: Algoritmo para encontrar dos puntos más alejados el uno del otro
También:
Esta es una pregunta que me hicieron en una entrevista de trabajo hace algún tiempo. Y todavía no puedo entender la respuesta sensata.
La pregunta es:
Te dan conjunto de puntos (x, y). Encuentra los 2 puntos más distantes. Distantes unos de otros.
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 es mayor que 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 lo hace prohibitivamente caro para grandes conjuntos de datos.
Hay un enfoque con los primeros puntos de seguimiento que están en el límite, y luego el cálculo de las distancias para ellos, con la premisa de que habrá menos puntos en el límite que "dentro", pero sigue siendo caro 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.
Dado un conjunto de puntos {(x1, y1), (x2, y2) ... (xn, yn)} encuentra los 2 puntos más distantes.
Mi acercamiento:
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 la distancia máxima.
3). Calcule toda la distancia desde el punto (xb, yb) a (x1, y1), (x2, y2), ... (xn, yn)
El otro "punto más distante" (xc, yc) es el que tiene la distancia máxima.
Así que tienes tus puntos más distantes (xb, yb) (xc, yc) en O (n)
Por ejemplo, para puntos: (0,0), (1,1), (-8, 5)
1). Punto de referencia (xa, ya) = (-2.333, 2)
2). Calcular distancias:
de (-2.333, 2) a (0,0): 3.073
de (-2.333, 2) a (1,1): 3.480
de (-2.333, 2) a (-8, 5): 6.411
Entonces el primer punto más distante es (-8, 5)
3). Calcular distancias:
de (-8, 5) a (0,0): 9,434
de (-8, 5) a (1,1): 9.849
de (-8, 5) a (-8, 5): 0
Así que el otro punto más distante es (1, 1)
Encuentre la media de todos los puntos, mida la diferencia entre todos los puntos y la media, tome el punto a la mayor distancia de la media y encuentre 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
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 calcula el casco convexo del conjunto.
Ahora tienes que encontrar todos los puntos antípodas en el casco convexo y elegir el par con la distancia máxima. Hay O (n) puntos antípodas en un polígono convexo. Entonces, esto da un algoritmo O (n lg n) para encontrar los puntos más lejanos.
Esta técnica es conocida 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 más detalles, consulte esta URL .
Esta pregunta se introduce en Introducción al algoritmo. Mencionó 1) Calcular el casco convexo O (NlgN). 2) Si hay M vectex en el casco convexo. Entonces necesitamos O (M) para encontrar el par más lejano.
Encuentro estos enlaces útiles. Incluye análisis de detalles de algoritmos y programa. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html
Ojalá esto sea de ayuda.
Esto parece fácil si los puntos están dados en coordenadas cartesianas. Tan fácil que estoy bastante seguro de que estoy pasando por alto algo. Siéntete libre de señalar lo que me estoy perdiendo!
- Encuentre los puntos con los valores máximo y mínimo de sus coordenadas x, y y z (6 puntos en total). Estos deben ser los más "remotos" de todos los puntos de límite.
- Calcula todas las distancias (30 distancias únicas)
- Encuentra la distancia máxima
- Los dos puntos que corresponden a esta distancia máxima son los que está buscando.
Los algoritmos de punto límite abundan (busque los algoritmos de casco convexo). A partir de ahí, debería tomar O (N) 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 forma de semicerrado. Dependiendo de los ángulos entre los bordes, tendrá que avanzar uno o el otro, pero siempre se necesitará O (N) para circunnavegar el casco.
Sólo unos pocos pensamientos:
Puede mirar solo los puntos que definen el casco convexo de su conjunto de puntos para reducir el número, ... pero aún parece un poco "no óptimo".
De lo contrario, podría haber un enfoque recursivo de quad / árbol de árbol para delimitar rápidamente algunas distancias entre conjuntos de puntos y eliminar grandes partes de sus datos.
Un algoritmo estocástico para encontrar el par más distante sería
- Elige un punto al azar
- Consigue el punto más lejano a él.
- Repetir unas cuantas veces
- Eliminar todos los puntos visitados
- Elige otro punto al azar y repite unas cuantas veces.
Estás en O (n) siempre que predetermines "unas cuantas veces", pero no se garantiza que encuentres el par más lejano. Pero dependiendo de tu conjunto de puntos, el resultado debería ser bastante bueno. =)
Un punto de partida podría ser mirar los problemas de punto más cercano, que han sido examinados. Wikipedia enumera algunas opciones:
mire los triángulos rectos A- (x1, y1), B- (x2, y2) y la distancia b / w A y B es = sqrt [(| x1 | + | x2 |) ^ 2 + (| y1 | + | y2 |) ^ 2]