Encontrar el punto de intersección más cercano en el plan

Question

me pidieron siguiente pregunta en una entrevista reciente:

Que suponga que tiene, después de cuadrícula en el sistema de coordenadas cartesianas (cuadrante I).

o - x - x - x - o 
| | | | | 
x - x - x - o - x 
| | | | | 
x - o - o - x - x 

where, o => person at intersection and x => no person at intersection 

class Point { 
int x; 
int y; 
boolean hasPerson; 
} 


Point findNearestPointWhereAllPeopleCanMeet(Point[] people) { 

} 

Implementar una rutina donde da una lista de personas de localización (puntos), encontrar un lugar (punto) de tal manera que es punto más cercano a todo punto dado.

¿Cómo resolvería este problema?

1) El enfoque es k-d árbol, pero ¿conoce alguna otra solución?

Answer 1

Si el problema requiere la minimización de Manhattan distance (es decir, las personas solo caminan paralelas a los ejes), entonces el problema es bastante trivial. En primer lugar, seleccionar la coordenada x y la coordenada y son problemas independientes.

Luego, para cada coordenada, simplemente encuentre el valor mediano de la posición de las personas a lo largo de ese eje. Para muchas configuraciones de personas, puede haber más de un punto que minimice la suma de las distancias para caminar de todas las personas. (Solo considere 2 personas separadas por más de 2 bloques en x y en la misma coordenada y; cualquier intersección intermedia requerirá el mismo total de andar por las dos personas).

Si el problema requiere minimizar la distancia euclidiana, entonces el objetivo es encontrar la mediana L1 de 2 variables. Este es un problema estándar, pero está lejos de ser trivial. (Ver here, por ejemplo.) Hay una respuesta única. Dado que esta fue una pregunta de entrevista, sospecho que esto no se aplica.

Answer 2

Antes de ir a estudiar árboles kd estos son algunos de los pensamientos que vienen a la mente:

1. Iterar todos los puntos de su matriz, gráfico, o lo que es
2. Asignar a cada punto (x, y) un valor que representa la MAX_distance del Punto a cualquiera de las personas. (Véase un ejemplo de una aclaración más adelante)
3. tomar cualquiera de los puntos que tienen el más bajo MAX_DISTANCE

POR EJEMPLO Punto dado (0,0):

• Para (1,0) la distancia es: 1
• Para (2,0) la distancia es: 2
• Para (0,2) la distancia es decir: 2
• para (3,1) la distancia es: 4
• para (4,2) la distancia es: 6

el MAX_DISTANCE para (0,0) es de 6. dado tu ingrese la menor MAX_distance debe ser 3 y hay muchos puntos con ese valor como (2,1) f o instancia.

Debería haber formas de hacer este algoritmo más eficiente ... Tal vez con kd trees: p o con otros ajustes como verificar el número total de personas, su ubicación/distancia relativa, el valor de MAX_distance en cualquier iteración, etc.

Answer 3

Esto probablemente le dará más de una respuesta aproximada que la correcta. Pero tal vez usted puede intentar algún tipo de agrupación (véase el procesamiento de imágenes médicas)

¿Qué pasa si usted proyecta todos los puntos sobre el eje Y:

3* 
4* 
3* 

Entonces proyectar sobre el eje X:

2* 2* 2* 2* 2* 

Leyenda: 3 * significa 3 personas en esta coordenada en el eje

Ahora encuentre la mediana también usando los pesos (peso @ ubicación = cuántas personas en en el eje)

Si encuentra la mediana para ambos ejes, puede tomar los puntos de reunión como (medianX, medianaY).

Puede obtener el punto más cercano correcto si al calcular la mediana en un eje, también se asegura de minimizar la distancia calculando la mediana del otro eje. Este último caso es más difícil.