Как хранить большое количество двумерных треугольников и эффективно их извлекать, используя запрос диапазона

Question

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

Я слышал о KD Trees, Quad Trees, просто хотел убедиться, есть ли лучший для хранения 2d треугольников, я знаю, что вышеупомянутое является общим, есть ли что лучше для 2d треугольника.

Я работаю с C #.

Answer 1

Взгляните на R-деревья (https://en.wikipedia.org/wiki/R-tree). Они весьма полезны для поиска по диапазону. Не уверен, что есть доступные реализации C #, но есть такие для C ++, например https://www.boost.org/doc/libs/1_68_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html, гдеВы можете найти интересные тесты (построение дерева, запросы)

Я бы также порекомендовал взглянуть на алгоритм: «STR: простой и эффективный алгоритм для упаковки R-дерева». В случаеВы хотите минимизировать перекрытие.

Answer 2

Мой выбор - квадри.

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

Запрос типа «треугольники в данном ограничивающем прямоугольнике» сводится к поиску нужного узла в дереве (ячейка, содержащая прямоугольник).

Запрос типа «треугольники, покрывающие данную точку» - это вопрос, чтобы найти ячейку (и ее подэлементы) для этой точки, а затем проверить каждый треугольник в контейнерах для этих ячеек.