Поиск ближайшей точки

Question

[TheHorse]

Алгоритмическая абстрактная задача:

Дано: 1 000 000 черных точек и 1 000 000 красных точек (x,y,z: float);
— 10 000 < x,y,z < 10 000 (декартовая система координат).

Нужно найти сумму растояний от каждой красной точки до ближайшей от нее черной.
Пример:


Серьезно рассматривал 2 варианта:
KD — деревья — но для них есть печальный контрпример, когда все черный точки расположены на одинаковом расстоянии от всех красных (красные — отрезок; черные — кольцо вокруг любой из точек красного отрезка);

Диаграмма Вороного — но она очень печальна для любой ситуации, сложна в программировании (особенно для 3D варианта, проблемно строить дерево по диаграмме, чтобы иметь логарифмический спуск). Этот алгоритм, несмотря на сложность поиска ближайшей точки o(log(n)) (после построения o(???)), будет работать медлено. Определение принадлежности точки к многограннику — сложная операция.

Может есть альтернативные алгоритмы? Знаю, что разновидностей этой задачи очень много, но интересует конкретно этот случей и наиболее эфективный алгоритм.

Comments

[TheHorse]

P. S. дал эту задачу на собеседовании и забыл уточнить, что интересует решение для задачи, когда и красные и черные точки распределены в пространсте равномерно (в этом случае все очень просто), а теперь вот и сам не знаю, что с этой задачей делать?

Answer 1

[Dzuba]

Спасибо вам за задачку. Очень она меня заинтересовала.

Набросал на коленке один алгоритм, реализация на C# работает довольно сносно: ~4.5 сек на моей дряхлой машине. Если грамотно распараллелить (а это должно быть довольно просто для данного алгоритма), то должно быть еще быстрее.
Единственное отличие от вашей постановки задачи: координаты точек я задавал типом double, а не float.

Суть алгоритма: перейти к целым числам в том смысле, что накрыть ОДЗ (-10 000 < x,y,z < 10 000) трехмерной сеткой.
Для случая равномерного распределения точек — проще всего равномерной же сеткой.
Эксперименты показали, что оптимальный шаг сетки для указанных в условии задачи параметров лежит в диапазоне 100-400, но это не принципиально.
Необходимо разложить все точки одного цвета (пусть это будет красный) по ячейкам. Лично я решил раскладывать не сами точки, а их индексы в исходном массиве. Это легко сделать, особенно в равномерном случае. То есть, выражаясь языком C#, заполняется такой трехмерный массив:

List<int>[,,] grid

Элементами этого массива являются списки индексов красных точек, попадающих в соответствующую ячейку.

Далее нам придется сделать такую штуку, которую я называю «сферическим циклом» (не знаю, появилось ли какое-то стандартное наименование для таких конструкций). Суть такого цикла можно объяснить на пальцах так: обходим ячейки сетки, начиная с некоторой начальной тройки индексов i₀, j₀, k₀, и далее расходясь концентрическими сферами. Иными словами, сначала цикл попадает в начальную ячейку, затем пробегает все ячейки, отстоящие от начальной на 1 (округленно), потом на 2 (округленно) и т.д.

Далее, в самом обычном цикле пробегаем все черные точки, вызывая для каждой из них этот самый «сферический цикл», в котором и ищем ближайшего соседа. Правда там есть еще хитрость с условием выхода из этого цикла, но это мелочи.

Есть исходник на C#. Если есть интерес, могу его предоставить.

Comments

[TheHorse]

Для равномерного случая все просто, вы все правильно сделали. Для неравномерного — сложно построить адекватную сетку, эпично сложно будет делать <сферический цикл> (поиск в ширину; волновой поиск).

[Dzuba]

Долго думал над случаем «сильной» неравномерности, но так и не нашел возражений против следующих тезисов.

Если даже закон распределения неизвестен, произведем такое же равномерное разбиение, но зададимся некоторым критерием «сгущения точек» для ячеек сетки. Для каждой из «густых» ячеек введем еще одну сетку, более подробную и опять же равномерную (см. LGR — local grid refinement, т.е. локальное измельчение сетки). Если для некоторых ячеек сетки LGR снова выполняется условие «сгущения», поступаем рекурсивно, измельчая сетку локально до полного удовлетворения. При таком подходе, «сферический цикл» (это название, имхо, точнее, чем просто поиск в ширину, ибо явно указывает порядок обхода ячеек) должен уметь опускаться внутрь этих LGR, что тоже сделать вроде как теоретически несложно. Это все, разумеется, будет работать уже не так быстро, но, при должной оптимизации и подгонке параметров, должно быть вполне приемлемо.

Это только в качестве идеи. Реализацией займусь вряд ли, ибо уже другой порядок временных затрат.

[TheHorse]

Нужно еще мыслить, но идея здравая. Ща попробую найти контр. пример, если не получится — реализовать алгоритм.

[Вячеслав Саратовский]

@Dzuba , не могли бы поделится исходниками?

[Dzuba]

@super-developer, уже нет, почти 3 года прошло же.

Answer 2

[ertaquo]

Самый простой способ — перебором:

var sqr = function(x) { return x * x; };
var summ = 0;
for (var i in red_points)
{
  var minSLen = false;
  for (var j in black_points)
  {
    var sLen = sqr(black_points[j].x - red_points[i].x) + sqr(black_points[j].y - red_points[i].y) + sqr(black_points[j].z - red_points[i].z);
    if (minSLen === false || sLen < minSLen)
      minSLen = sLen;
  }
  if (minSLen >= 0)
    summ += Math.sqrt(minSLen);
}

Эффективность у него довольно низкая, но зато работает в любых условиях :-)

Comments

[TheHorse]

Этот алгоритм менее эффективен че те, что я предоставил, и они работают в любых условиях. У них проблемы со скоростью, у вами предоставленного — еще больше проблем со скоростью.