Слияние листьев в октри

Question

У меня очень большое облако точек (> 100000 точек), в котором я хотел бы обнаруживать планарные расположения. Я решил использовать октодерево, чтобы разбить точки на очень маленькие плоские кластеры, а затем объединить соседние кластеры, которые находятся в одной плоскости.Я написал код на C ++, который быстро разбивает облако точек на небольшие плоские кластеры, но как эффективно объединить их, ускользает от меня ...

Моя Octree реализация использует структуру указателей: есть OctreeNode s с массивами OctreeNode* children[8], содержащими указатели на их дочерние узлы, или все NULL указатели, если это листовой узел.

Сначала я думал, чтобы в каждом объекте OctreeNode сохранялся указатель наPlane объект.После первого разбиения точек каждый лист в октрее получит Plane, представляющий наименьшие квадраты, подходящие ко всем точкам, содержащимся в листе.Затем я перебираю каждый листовой узел дерева.Для каждого конечного узла я проверяю каждый из его соседних конечных узлов: если плоскость соседа должна быть объединена с плоскостью текущего конечного узла, я вызываю Plane* newPlane = Plane::mergePlanes(this->plane, neighbor->plane);, чтобы создать новую плоскость, которая представляет точки в обоих узлах.

Здесь я столкнулся с проблемой ... Сначала я подумал, что могу просто заменить обе плоскости новой плоскостью, то есть plane = newPlane; neighbor->plane = newPlane;, и все будет сделано (утечка памяти в стороне; я справился с ними в реальномкод).К сожалению, это не работает на практике.После объединения нескольких плоскостей может быть несколько различных OctreeNode, указывающих на один Plane, и простая замена указателей в this->plane и neighbor->plane не заменяет КАЖДЫЙ указатель, указывающий на их старые плоскости.

Решение выглядело хакерским, даже когда я впервые его придумал, а теперь его недостатки еще более очевидны.Кто-нибудь может придумать способ исправить метод объединения, который я придумал, или придумать лучший способ?

Спасибо

Answer 1

Стандартное исправление - ленивое исправление узлов. Имейте метод доступа, который смотрит на плоскость, на которую вы указываете, и затем видит, была ли она указана в другом месте. Если это так, выполните рекурсивный поиск до тех пор, пока не найдете его, и исправьте все объекты обратно к текущему, а затем верните правую плоскость обратно.

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

Answer 2

VTK имеет аналогичный класс дескриптора точки vtkIncrementalOctreePointLocator . Я думаю, что идеальная точка для объединения точки вставки.

например:.

double xyz[3];    // location
id_type point_id; // we get back the point id

// bool InsertUniquePoint( double xyz[3], id_type &point_id );
// return value is true, if new point inserted
bool value = inserter->InsertUniquePoint( xyz, point_id );

Так что мое мнение: если класс слишком большой, его легче перестроить.