Dados n puntos en un plano 2-D, ¿cuál es el punto tal que la distancia desde todos los puntos se reduce al mínimo? Este punto no necesita ser del conjunto de puntos dados. ¿Es centroide o algo más?Encontrar el punto más cercano a un conjunto de puntos en el plano
¿Cómo encontrar todos esos puntos (si hay más de uno) con un algoritmo?
Esto se conoce como el "Centro de distancia" y es diferente del centroide.
En primer lugar, debe definir qué medida de distancia está utilizando. Si suponemos que está utilizando la métrica estándar de d = sqrt ((x1-x2)^2 + (y1-y2)^2), entonces no es única, y el problema es minimizar esta suma.
El ejemplo más fácil para mostrar esta respuesta no es único es el ejemplo de línea recta. Cualquier punto entre los dos puntos tiene una distancia total igual a todos los puntos.
En 1D, la respuesta correcta será cualquier respuesta que tenga el mismo número de puntos a la derecha y a la izquierda. Mientras esto sea cierto, cualquier movimiento hacia la izquierda y la derecha aumentará y disminuirá los lados izquierdo y derecho en la misma cantidad, por lo que la distancia será la misma. Esto también prueba que el centroide no es necesariamente la respuesta correcta.
Si ampliamos a 2D, este ya no es el caso, ya que el sqrt hace que el problema se pondere. ¡Sorprendentemente para mí no parece haber un algoritmo estándar! La página here parece usar un método de fuerza bruta. ¡Nunca lo supe!
Si quisiera usar un algoritmo, entonces encontraría el punto medio en X e Y como punto de inicio, luego usaría un gradient descent algorithm - esto daría la respuesta bastante rápido. Toda la ecuación termina como cuadrática, por lo que parece que debería haber una solución exacta.
¿No lo hace el algoritmo de fuerza bruta en su primer enlace para los puntos en una esfera? –
No, dije descenso en gradiente para n puntos. Escribe tu función de puntuación para que calcule la distancia total a los n puntos, luego deja que tu función de descenso minimice este valor. No voy a agregar el código en caso de que sea tarea, debería ser fácil de escribir. –
@Matthijs, con bastante probabilidad, que no se veía muy duro. Gracias por señalar. Es una pregunta interesante, ¿no? –
Puede haber más de un punto. Considera un avión con solo dos puntos en él. Esos puntos describen un segmento de línea. Cualquier punto en ese segmento de línea tendrá la misma distancia total desde los dos puntos finales.
Entonces, ¿cómo encontrar todos esos puntos con un algoritmo? – nowonder
De hecho, la respuesta va a ser un simple polígono. La razón es que una suma de funciones convexas (como la función de distancia) también es convexa. Probablemente pueda encontrar sus coordenadas exactas comenzando desde un triángulo y agregando puntos. Sin embargo, hacerlo ingenuamente sería 'n^2'. –
A brute force algo. podría darte los mejores resultados. En primer lugar, ubique un rectángulo/cualquier cuadrilátero que delimite los puntos de entrada. Finalmente, para cada punto dentro del rectángulo, calcule la distancia desde otros puntos. Sume las distancias del punto desde el conjunto de entrada. Diga que este es el 'costo' del punto. Repita para cada punto y seleccione el punto con mín. costo.
La inteligencia también se puede agregar al algo. puede eliminar áreas con base en el precio promedio, etc ...
Eso es cómo iba a abordar el problema, al menos ... creo que sirve.
Pero tiene una complejidad muy alta. Comprobando cada punto dentro del rectángulo, cómo hacerlo, las coordenadas del punto pueden ser cualquier número de punto flotante. – nowonder
Bueno, obviamente, necesita un poco de paso, una distancia mínima entre dos puntos consecutivos, un ejemplo simple usando C podría ser: para (int row = minR; row
Esto se discute en detalle aquí http://www.ddj.com/architect/184405252?pgno=1
Esto fue interesante pero resuelve un problema diferente. El que pregunta hizo el punto que minimiza la distancia a todos los puntos. El artículo DDJ encuentra los dos puntos más cercanos el uno al otro. –
No cierre esto, los algoritmos de geometría son enteramente dentro del alcance de desbordamiento de pila –
Es tarea? Además, ¿en qué idioma estás tratando de implementar esto? – Piskvor
No, no es tarea. Estoy estudiando algoritmos en geometría computacional. Así que tengo una duda. Lo estoy haciendo en C. – nowonder