Я рассматриваю реализацию структур данных quad tree и r-tree, чтобы проверить некоторые идеи по работе с распределением двух точек измерения. Мой вопрос в том, как эти алгоритмы обрабатывают повторяющиеся точки? Или каковы некоторые методы обработки повторяющихся точек?
Как обрабатывать повторяющиеся точки для R-деревьев и четырехъядерных деревьев?
Ответы (2)
Скорее всего, вы можете игнорировать/удалять повторяющиеся точки.
person
Gigamegs
schedule
15.09.2015
Я не могу игнорировать или удалять точки. Я хочу узнать информацию о распределении всех точек, поэтому важно знать, что есть дубликаты. Однако я не уверен, как справиться с разделением в этом случае. Я думаю, мне просто нужно будет создать точку класса, которая также имеет счетчик, который я увеличиваю, если создается дублирующаяся точка, и игнорирую часть разделения.
- person Stefan Orr; 16.09.2015
QuadTrees требуют ухода. Наивная реализация будет пытаться продолжить разбиение до тех пор, пока у вас не будет меньше максимального количества элементов m (по умолчанию m = 1). Если у вас есть дубликаты m + 1, это приведет к бесконечному циклу. Таким образом, вам нужно выявлять и обрабатывать повторяющиеся точки.
R-деревья лучше. Совершенно допустимо иметь перекрывающиеся страницы. Таким образом, даже когда страница, состоящая только из дубликатов, переполняется, вы можете разделить ее. Разделение R-дерева всегда должно разделять данные на две страницы одинакового размера.
person
Has QUIT--Anony-Mousse
schedule
16.09.2015
Да, R-дерево должно работать из коробки для дублированных точек (например, R-дерево Boost.Geometry допускает дублирование). Классическое сбалансированное KD-дерево (хранение узловых точек в массиве, похожем на кучу, и использование координат точек в качестве координат разделительных плоскостей) также должно работать из коробки для дублирующихся точек.
- person Adam Wulkiewicz; 21.10.2015
