Найти ближайшую точку пересечения в плане - PullRequest
Новая
       35

Найти ближайшую точку пересечения в плане

7 голосов
/ 20 декабря 2011

Мне недавно задали следующий вопрос в интервью:

Предположим, у вас есть следующая сетка по декартовой системе координат (квадрант 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) {

}

Реализуйте процедуру, в которой указан список людей (точки), найдите местоположение (точку), которое является ближайшей точкой ко всей данной точке.

Как бы вы решили этопроблема?

1) Подход - это дерево кд, но знаете ли вы какое-нибудь другое решение?

Ответы [ 3 ]

5 голосов
/ 20 декабря 2011

Если проблема требует минимизации Манхэттенского расстояния (то есть люди идут только параллельно осям), то тогда проблема довольно тривиальна. Во-первых, выбор координаты x и координаты y являются независимыми проблемами.

Затем для каждой координаты просто найдите медианное значение положения людей вдоль этой оси. Для многих конфигураций людей может быть более одной точки, которая минимизирует сумму пройденных расстояний всех людей. (Просто рассмотрите 2 человека, разделенных более чем 2 блоками по x и с одной и той же координатой y; любое пересечение между ними потребует одинакового общего количества пеших ходов двумя людьми.)

Если задача требует минимизации евклидова расстояния, то цель состоит в том, чтобы найти медиану L1 с двумя переменными. Это стандартная проблема, но она далеко не тривиальна. (См., Например, здесь .) Существует уникальный ответ. Учитывая, что это был вопрос интервью, я подозреваю, что это не относится.

1 голос
/ 20 декабря 2011

Прежде чем отправиться изучать k-d деревья, вот некоторые мысли, которые пришли мне в голову:

  1. Переберите каждую точку вашей матрицы, графика или чего-либо еще
  2. Назначьте каждой точке (x, y) значение, представляющее MAX_distance от точки любому из людей. (См. Поясняющий пример ниже)
  3. Возьмите любую из точек с наименьшим MAX_distance

например. Заданная точка (0,0):

  • Для (1,0) расстояние составляет: 1
  • Для (2,0) расстояние составляет: 2
  • Для (0,2) расстояние составляет: 2
  • Для (3,1) расстояние составляет: 4
  • Для (4,2) расстояние составляет: 6

MAX_distance для (0,0) равно 6. Учитывая ваши входные данные, наименьшее MAX_distance должно быть 3, и есть много точек с таким значением, например (2,1).

Должны быть способы сделать этот алгоритм более эффективным. Может быть, с деревьями kd: p или другими настройками, такими как проверка общего числа людей, их относительного местоположения / расстояния, значения MAX_distance на любой итерации и т. Д.

0 голосов
/ 20 декабря 2011

Это, вероятно, даст вам более приблизительный, чем правильный ответ. Но, может быть, вы можете попробовать какую-то кластеризацию (см. Обработку медицинских изображений)

Что если вы спроецируете все точки на ось Y: 

 3*
 4*
 3*

Затем спроецируйте на ось X: 

2* 2* 2* 2* 2*

Легенда: 3 * означает 3 человека по этой координате на оси

Теперь найдите медиану, также используя веса (weight @location = сколько людей в этом месте на оси)

Если вы найдете медиану для обеих осей, вы можете взять точки встречи как (medianX, medianY).

Вы можете получить правильную ближайшую точку, если при расчете медианы по одной оси вы также убедитесь, что расстояние минимизировано, вычислив медиану по другой оси. Последний случай сложнее.

...