performance - varias - Encuentra K puntos más cercanos al punto P en plano bidimensional

punto mas cercano al origen de una superficie

Question

Fuente: PREGUNTA DE LA ENTREVISTA AMAZÓNICA

Dado un punto P y otros N puntos en el espacio bidimensional, encuentre K puntos de los N puntos más cercanos a P.

¿Cuál es la forma más óptima de hacer esto?

Esta página Wiki no proporciona mucha ayuda para construir un algoritmo. Cualquier idea / acercamiento a las personas.

Answer 1

Solución 1

private List<Point> nearestKPoint_1(List<Point> list, final Point center, int k) {
List<Point> ans = new ArrayList<>();
PriorityQueue<Point> maxHeap = new PriorityQueue<>(k + 1, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return distance(center, o2) - distance(center, o1);
}
});
for (Point p : list) {
maxHeap.offer(p);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
Iterator<Point> i = maxHeap.iterator();
while (i.hasNext()) {
ans.add(i.next());
}
return ans;
}
public int distance(Point p1, Point p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
if (x != point.x) return false;
return y == point.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}

Solución 2

private List<Point> nearestKPoint_2(List<Point> list, final Point center, int k) {
List<Point> ans = new ArrayList<>();
Distance[] nums = new Distance[list.size()];
for (int i = 0; i < nums.length; i++) {
nums[i] = new Distance(distance(center, list.get(i)), i);
}
quickSelect(nums, k);
for (int i = 0; i < k; i++) {
ans.add(list.get(nums[i].i));
}
return ans;
}
private void quickSelect(Distance[] nums, int k) {
int start = 0, end = nums.length - 1;
while (start < end) {
int p = partition(nums, start, end);
if (p == k) {
return;
} else if (p < k) {
start = p + 1;
} else {
end = p - 1;
}
}
}
private int partition(Distance[] nums, int start, int end) {
Distance pivot = nums[start];
int i = start, j = end + 1;
while (true) {
while (i < end && nums[++i].compareTo(pivot) < 0);
while (j > start && nums[--j].compareTo(pivot) > 0);
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, start, j);
return j;
}
private void swap(Distance[] nums, int i, int j) {
Distance tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
class Distance implements Comparable<Distance> {
int d;
int i;
public Distance(int d, int i) {
this.d = d;
this.i = i;
}
@Override
public int compareTo(Distance o) {
return this.d - o.d;
}
}

Answer 2

Para una sola consulta ...

Mantener un montón de tamaño k .

Para cada punto, calcule la distancia al punto P Inserta esa distancia en el montón y elimina el máximo del montón si el tamaño del montón es mayor que k .

Tiempo de ejecución: O(n log k)

Answer 3

La solución 1 hace un montón de tamaño K y recoge puntos por una complejidad O (NLogK) de distancia mínima.

Solución 2 : toma y ordena el tamaño N y ordena por distancia. Debe usarse QuickSort (modificación de Hoare). Como respuesta, toma primero K puntos. Esta también es una complejidad NlogN pero es posible optimizar para aproximar O (N). Si omite la clasificación de subordenaciones innecesarias. Cuando se divide el conjunto por 2 matrices secundarias, se debe tomar solo el array donde se encuentra el índice Kth. la complejidad será: N + N / 2 + N / 4 + ... = O (N) .

Solución 3 : busca el elemento Kth en la matriz de resultados y toma todo el punto menor que se fundó. Existe O (N) alghoritm, similar a la búsqueda de la mediana.

Notas : mejor utilizar sqr de distancia para evitar las operaciones sqrt, será mucho más rápido si el punto tiene coordenadas enteras.

Como respuesta a una entrevista, use mejor la Solución 2 o 3.

Answer 4

Puede usar el árbol KD http://en.wikipedia.org/wiki/K-d_tree para particionar el espacio y, dado el punto, podrá buscar vecinos de forma gradual mediante la búsqueda binaria. El beneficio de usar este enfoque es que escala fácilmente a la versión en línea cuando recibe puntos / consultas en tiempo de ejecución uno por uno o en lotes.

Answer 5

¿Qué está mal con el enfoque a continuación?

1) Calcula la distancia desde el punto dado a otros puntos.

2) Guarde la distancia y el índice de ese punto en el TreeMap<Double,Integer> map

3) Seleccione los elementos K superiores del mapa. Sus valores darán índice del elemento Punto de la matriz de puntos.

El mapa se ordena de acuerdo con el orden natural de sus claves, o mediante un comparador proporcionado en el momento de creación del mapa,