Алгоритм рекурсивно разделить многоугольник на квадранты внедорожника: как он называется и где код?

Question

У меня много очков (сотни тысяч), и я хочу проверить, какие из них находятся внутри многоугольника. Для относительно небольшого многоугольника (т.е., вероятно, будет содержать только десятки или сотни точек), я могу просто использовать ограничивающую коробку полигона в качестве первоначальной проверки, а затем выполнить регулярную проверку в точке полиции для этих точек внутри коробки Анкет Но представьте себе большой (то есть, вероятно, содержит тысячи моих точек), нерегулярно формированные полигоны. Многие баллы пройдут проверку ограничивающего ящика, и, кроме того, проверка в точке в полих будет более дорогой, поскольку более крупный многоугольник состоит из гораздо большего количества точек. Поэтому я хотел бы иметь возможность фильтровать большинство очков в или наружу, не выполняя полную проверку с точки зрения.

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

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

Сделайте предварительный процесс «прямого дерева», где глубина прямого дерева варьируется по размеру многоугольника (т.е. позволяет больше глубины для большего многоугольника). Прямое дерево разделило бы ограничивающую коробку многоугольника на четыре квартала. Он проверил бы, полностью ли каждая четверть-образная очередь внутри многоугольника, полностью за пределами многоугольника, или ни один. В случае, если ни один из них не будет рекурсивно разделять подректы, продолжая таким образом, пока все прямы не будут полностью внутри или снаружи, либо максимальная глубина не была достигнута. Таким образом, идея состоит в том, что (а) время предварительного обработки для создания этого дерева, хотя оно само по себе сделает несколько проверок в полигоне, стоит того, потому что это время затмевается количеством пунктов, которые необходимо проверить, и (b) подавляющее большинство баллов может быть рассмотрено с использованием простых проверок рамки (как правило, несколько таких проверок, как вы спускаетесь по дереву), и тогда относительно небольшое число должно было бы провести полную проверку в политигоне ( ибо, когда вы достигнете листового узла, который еще не «ни»).

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

Answer 1

Я на самом деле закончил тем, что использовал связанный, но другой подход. Я понял, что по сути эта структура дерева, которую я строил, была не более чем полигоном, нарисованным с низким разрешением. Например, если мое дерево опустилось на глубину 8, это было похоже на то, чтобы рисовать мой многоугольник на растровом карте с разрешением 256x256, а затем с прохождением тестов на пиксель против этого многоугольника. Поэтому я расширил эту идею и использовал библиотеку быстрой графики (библиотека CIMG). Я рисую многоугольник на черно-белой растровой карте размера 4000x4000. Затем я просто проверяю точки как пиксели против этой растровой карты. Магия заключается в том, что рисунок, который огромный растровый карта действительно быстр по сравнению со временем, которое мне потребовалось, чтобы построить дерево. Так что я получаю гораздо более высокое разрешение, чем я когда -либо мог иметь с моим деревом.

Одна проблема заключается в том, чтобы обнаружить точки возле самого края многоугольника, который может быть включен или исключен неправильно из -за проблем с округлением/разрешением, даже при размере 4000x4000. Если вам нужно точно знать, находятся ли эти точки в или наружу, вы можете нарисовать ход по многоугольникам в другом цвете, и если ваш тест Pixel попадет в этот цвет, вы бы сделали полную точку в Poly Check. Для моих целей разрешение 4000x4000 было достаточно хорошим (я мог переносить неправильное включение/исключение для некоторых из моих краевых точек).

Таким образом, фундаментальным трюком этого решения является идея, что алгоритмы рисования многоугольника просто очень быстрые по сравнению с другими способами, которыми вы можете «оцифровать» свой многоугольник.