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

Question

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

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

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

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

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

Answer 1

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

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

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