Duplicar posible:
Greatest linear dimension 2d set of pointsDado un conjunto de puntos, ¿cómo encuentro los dos puntos que están más alejados entre sí?
pude calcular la distancia entre cada punto y tomar la más grande, pero que no suene como una forma muy eficiente de hacerlo cuando hay una gran (> 1000) número de puntos.
Nota: Esto es para iPhone, así que no tengo una tonelada de potencia de procesamiento.
Usted está pidiendo que calcule 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 elimine ningún punto, esta información adicional 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 fairly readable discussion 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 le permitirá ir mucho más rápido =)
Comience con el punto con la x-coord más baja. (Llámalo Punto X) Construir conjunto de "puntos límite" empezando por el punto x, y línea vertical por el punto, no debería haber otros puntos a la izquierda de PointX) encontrar el siguiente punto en el límite girando lentamente la línea en sentido horario (O en sentido antihorario) hasta que la línea toque algún otro punto (ver abajo). Agregue ese punto al conjunto y repita con el siguiente punto para obtener el siguiente, hasta que finalmente regrese al punto x original. Usted npw tiene un conjunto de puntos que forman el límite del conjunto completo. Compara 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 límite secuencial), tome el punto que está "más alejado" 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 límite punto y ese "próximo" 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 dirtección perpindicular a esta línea o a la última línea, entonces esta es la opción correcta para el siguiente punto límite, si hay tal punto, cambie a ese punto y vuelva a realizar la prueba.
Mismo comentario que a Chris. No haces nada más fácil si en el límite exterior no hay mucho menos puntos. –
Esto suena como una forma costosa de calcular el casco complejo, seguido por el resto de la respuesta de Chris Bunch. – PanCrit
No sabía que había un término técnico para esto ... (casco convexo) pero es un límite de banda de goma. Verificará otros algoritmos para calcularlo ... En cuanto al número de puntos, para cualquier colección aleatoria de puntos, el número de puntos en el límite debe ser O (n) menor que el número total de puntos. (El límite es una línea unidimensional que delimita un área de 2 dimensiones). –
¿Por qué no simplemente calcular el convex hull de los puntos? Dependiendo del algorithm que use, toma O(n) o y elimina todos los puntos internos de consideración. Luego, solo revisa estos puntos más externos para encontrar los dos que están más lejos.
Esto no facilita las cosas. Si la cantidad de puntos en un casco convexo es O (n), entonces la complejidad sigue siendo la misma. –
Muy cierto. Pero la esperanza es que si hay> 1000 puntos, muchos de ellos estarán dentro del casco convexo. –
Gran respuesta. Iba a decir esto. Comience con la heurística Akl-Toussaint para tirar tantos puntos como sea posible antes de encontrar el casco convexo. – Nosredna
Vea el these pages (el vinculado a y las páginas accesibles haciendo clic en los "próximos" enlaces) al calcular el diámetro del casco convexo de un conjunto de puntos.
Mi breve resumen:
Es O (n) solo después de encontrar el casco convexo - si solo le dan un conjunto de puntos, puede ser O (n log n) para encontrar primero el casco convexo. – ShreevatsaR
@ShreevatsaR: por supuesto. Mi respuesta dice explícitamente "donde n es el número de puntos en el casco convexo", lo que deja bastante claro que primero debe encontrar el casco convexo. –
Sí, quizás sí. La claridad está en el ojo del lector. :-) (El algoritmo para la tarea en la pregunta obviamente no es O (n) donde n es el número de puntos en el casco convexo, es la segunda parte que es, como dices.) De todos modos, pensé que vale la pena mencionar , solo para completar: las personas pueden llegar a estas respuestas años después a través de motores de búsqueda que no pueden leer cuidadosamente, y pueden confundirse, etc. – ShreevatsaR