Dado un conjunto de puntos, ¿cómo encuentro los dos puntos que están más alejados entre sí? [duplicar]

Question

  

Posible duplicado:
   El mayor conjunto de puntos de la dimensión lineal 2d

Podría calcular la distancia entre cada punto y tomar la más grande, pero eso no suena como una forma muy eficiente de hacerlo cuando hay un gran número de puntos (> 1000).

Nota: Esto es para iPhone, por lo que no tengo un montón de poder de procesamiento.

Answer 1

Estás pidiendo calcular el diámetro del conjunto. La técnica estándar es calcular primero el casco convexo, lo que reduce el problema para encontrar el diámetro de un polígono convexo. Incluso en el caso de que no elimines ningún punto, esta información agregada es exactamente lo que se necesita para resolver el problema de manera eficiente. Sin embargo, encontrar el diámetro de un polígono convexo no es del todo trivial; Varios artículos publicados con algoritmos para esta tarea resultan ser incorrectos.

Aquí hay un discusión bastante legible de un algoritmo O (n) correcto para la tarea (donde n es el número de puntos en el casco convexo).

Además, tenga en cuenta que el iPhone no es que limitado; una implementación cuidadosamente escrita de incluso el algoritmo completamente ingenuo puede manejar 1000 puntos en menos de una décima de segundo. Por supuesto, usar el algoritmo correcto te permitirá ir mucho más rápido =)

Answer 2

¿Por qué no calcular simplemente el casco convexo de los puntos? Dependiendo del algoritmo que usa, toma O (n) o O (n log n) y elimina todos los puntos internos de la consideración. Luego, solo marque estos puntos más externos para encontrar los dos que están más lejos.

Answer 3

Comience con el punto con la coordenada x más baja. (Llámalo punto X) Construir conjunto de " puntos de límite "    comenzando con el punto x, y la línea vertical a través del punto, no debe haber otros puntos a la izquierda del Punto X) encuentre el siguiente punto en el límite girando lentamente la línea en el sentido de las agujas del reloj (O en sentido contrario a las agujas del reloj) hasta que la línea toque algún otro punto, (vea a continuación ). Agregue ese punto al conjunto y repita con el siguiente punto para obtener el siguiente, hasta que finalmente vuelva al punto original x. Usted npw tiene un conjunto de puntos que forman el límite del conjunto completo. Compare la distancia entre cada par en este conjunto reducido para encontrar el par que está más alejado.

Para " girar la línea " (para encontrar cada punto de límite secuencial), tome el punto que está más lejos " en la dirección perpindicular a la línea utilizada para el último punto límite, y construya una nueva línea entre el último punto límite y la " siguiente " punto. Luego verifique que no haya otros puntos furthur en la nueva dirección perpindicular formada por esa nueva línea. Si no hay otros puntos " furthur out " en la succión perpindicular a esta línea o a la última línea, entonces esta es la opción correcta para el siguiente punto de límite, si existe tal punto, cambie a ese y vuelva a probar.

Answer 4

Consulte estas páginas (la enlazadas y las páginas accesibles haciendo clic en los enlaces " a continuación " ;, en el cálculo del diámetro del casco convexo de un conjunto de puntos.

Mi resumen rápido:

1. calcular el conjunto de puntos en el casco convexo (= O (n log n), la única vez que obtiene O (n) es si primero ordena la lista, lo que toma O (n log n) de todos modos)
2. ordene a lo largo del límite (obtendrá esto gratis si usa un exploración de Graham para # 1)
3. use uno de los algoritmos de diámetro O (n) para buscar puntos antipodales con el mayor diámetro. algoritmo de Shamos me parece bien porque es uno de los calibradores rotativos .