Реализация kd-дерева PCL очень медленная

Вкратце:

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

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

Как упомянул Андерас в комментарии, радиус поиска также играет значительную роль. Если в радиус поиска попадает много точек, поиск может стать очень медленным.

Полный ответ:

3 измерения это не много. Проблема возникает из-за количества очков, которые у вас есть.

ANN означает приблизительный поиск ближайшего соседа. Очень часто приходится идти на компромисс между точностью и скоростью, когда речь идет о NNS (поиске ближайших соседей).

Это означает, что вы выполняете поиск быстрее, но можете найти не точную NN, а близкую (например, не ближайшую точку, а вторую ближайшую и так далее). Большая скорость означает меньшую точность и наоборот.

CGAL также имеет параметр epsilon, обозначающий точность (ε = 0 означает полную точность). CGAL предназначен для перехода в 3 измерения, так что вы можете попробовать.

Я мог бы просто проверить себя и опубликовать ответы. Однако это не было бы на 100% безопасным, поскольку имеющиеся у вас очки могут иметь какое-то отношение. Это очень важно для производительности библиотеки, если она собирается использовать отношения, которые точки (могут) иметь друг к другу.

Еще один фактор, который следует учитывать, — простота установки.

CGAL трудно установить. Когда я это сделал, я выполнил эти шаги. ИНС легко установить. Я бы также посоветовал вам взглянуть на BOOST Geometry, который может вам пригодиться.

FLANN также является сильным игроком в этой области, но я бы не рекомендовал его, поскольку он предназначен для обработки наборов данных гораздо больших размеров (например, 128).

....

Хорошо, я признаю это, теперь мне самому любопытно, и я собираюсь провести несколько тестов!

....

ЭНН

(Я не публикую код, чтобы ответ не стал слишком большим. В документации есть примеры, и вы, конечно, можете спросить, если хотите!). Вывод:

// для бутылки Клейна

samaras@samaras-A15:~/Inria/nn_libs/ANN/ann_1.1.2/code$ g++ main.cpp -O3 -I ../include/ -L../lib -lANN -std=c++0x -o myExe
samaras@samaras-A15:~/Inria/nn_libs/ANN/ann_1.1.2/code$ ./myExe
N = 1000000
D = 3
ε = 0 // full accuracy
Misses: 0
creation of the tree took 1.06638 seconds.
Brute force for min: 0.009985598 seconds.
NN for 0.0           0.000078551 seconds.
Speedup of ANN for NN = 8.721533780

Для ε = 0.1 я получил:

Misses: 1000
creation of the tree took 0.727613 seconds.
Brute force for min: 0.006351318 seconds.
NN for 0.0           0.000004260 seconds.
Speedup of ANN for NN = 8.678169573

// для сферы

ε = 0
Misses: 0
creation of the tree took 1.28098 seconds.
Brute force for min: 0.006382912 seconds.
NN for 0.0           0.000022341 seconds.
Speedup of ANN for NN = 4.897436311

ε = 0.1
Misses: 1000
creation of the tree took 1.25572 seconds.
Brute force for min: 0.006482465 seconds.
NN for 0.0           0.000004379 seconds.
Speedup of ANN for NN = 5.144413371

Обратите внимание на разницу в ускорении! Это связано с характером наборов данных, как объяснялось выше (связь между точками).

ЦГАЛ:

// бутылка Клейна

samaras@samaras-A15:~/code/NN$ ./myExe
ε = 0
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.02478 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 471492
 Tree depth: 34
0x80591e4
Brute force for min: 0.007979495 seconds.
NN for 0.0           0.008085704 seconds.
Speedup of cgal for NN = 0.983849423

ε = 0.1
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.02628 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 471492
 Tree depth: 34
0x80591e4
Brute force for min: 0.007852951 seconds.
NN for 0.0           0.007856228 seconds.
Speedup of cgal for NN = 0.996250305

// Сфера

samaras@samaras-A15:~/code/NN$ ./myExe
ε = 0
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.025502 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 465002
 Tree depth: 32
0x80591e4
Brute force for min: 0.007946504 seconds.
NN for 0.0           0.007981456 seconds.
Speedup of cgal for NN = 0.992449817


samaras@samaras-A15:~/code/NN$ ./myExe
ε = 0.1
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.025106 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 465002
 Tree depth: 32
0x80591e4
Brute force for min: 0.008115519 seconds.
NN for 0.0           0.008117261 seconds.
Speedup of cgal for NN = 0.996702679

Для моих тестов ANN понятнее, чем CGAL, возможно, и для ваших тоже!

Примечание:

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