Спасибо вам за задачку. Очень она меня заинтересовала.
Набросал на коленке один алгоритм, реализация на C# работает довольно сносно: ~4.5 сек на моей дряхлой машине. Если грамотно распараллелить (а это должно быть довольно просто для данного алгоритма), то должно быть еще быстрее.
Единственное отличие от вашей постановки задачи: координаты точек я задавал типом double, а не float.
Суть алгоритма: перейти к целым числам в том смысле, что накрыть ОДЗ (-10 000 < x,y,z < 10 000) трехмерной сеткой.
Для случая равномерного распределения точек — проще всего равномерной же сеткой.
Эксперименты показали, что оптимальный шаг сетки для указанных в условии задачи параметров лежит в диапазоне 100-400, но это не принципиально.
Необходимо разложить все точки одного цвета (пусть это будет красный) по ячейкам. Лично я решил раскладывать не сами точки, а их индексы в исходном массиве. Это легко сделать, особенно в равномерном случае. То есть, выражаясь языком C#, заполняется такой трехмерный массив:
List<int>[,,] grid
Элементами этого массива являются списки индексов красных точек, попадающих в соответствующую ячейку.
Далее нам придется сделать такую штуку, которую я называю
«сферическим циклом» (не знаю, появилось ли какое-то стандартное наименование для таких конструкций). Суть такого цикла можно объяснить на пальцах так: обходим ячейки сетки, начиная с некоторой начальной тройки индексов i
0, j
0, k
0, и далее расходясь концентрическими сферами. Иными словами, сначала цикл попадает в начальную ячейку, затем пробегает все ячейки, отстоящие от начальной на 1 (округленно), потом на 2 (округленно) и т.д.
Далее, в самом обычном цикле пробегаем все черные точки, вызывая для каждой из них этот самый «сферический цикл», в котором и ищем ближайшего соседа. Правда там есть еще хитрость с условием выхода из этого цикла, но это мелочи.
Есть исходник на C#. Если есть интерес, могу его предоставить.
