Алгоритм поиска треугольников в пределах области

Question

Я работаю над небольшим проектом, который требует от меня быстро найти, какие треугольники внутри набора треугольников либо частично, либо полностью содержатся в данной прямоугольной области. Меня интересует оптимизация для быстрого поиска - я не ограничена памятью.

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

Может кто-нибудь указать мне на любой ресурс, где «правильный» способ справиться с этой проблемой?

Спасибо!

Редактировать: Я забыл упомянуть, что прямоугольные области, которые я использую в настоящее время, параллельны осям координат x и y. На данный момент я доволен любым решением, которое использует это ограничение. В общем, хотя решение с совершенно произвольными прямоугольниками было бы полезно узнать.

Answer 1

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

Вы можете найти эффективные реализации AABBTrees в:

• CGAL: http://doc.cgal.org/latest/AABB_tree/

• библиотеку GEOGRAM, что я пишу: http://alice.loria.fr/software/geogram/doc/html/classGEO_1_1MeshFacetsAABB.html

• OpCode: http://www.codercorner.com/Opcode.htm

Answer 2

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

1. Сравнить ограничительную рамку треугольника в регион. Если он внутри, треугольник внутри. Если вообще нет перекрытия, это не так. Используйте дерево интервалов для каждого измерения для этого шага, если вам нужно проверить один и тот же набор треугольников с разными регионами.

2. Мы проверили два простых случая на первом шаге, поэтому мы знаем, что область и перекрывающая область перекрываются. Проверьте, находится ли какая-либо из точек треугольника внутри прямоугольника. Если это так, треугольник внутри.

3. Проверьте четыре стороны прямоугольника с трех сторон треугольника для сегмента линии пересечения

Answer 3

Если предварительная обработка набора треугольников не допускается, вам нечего лучше делать, чем сравнивать каждый треугольник с окном.

Чтобы решить проблему перекрытия треугольника/прямоугольника легко (или просто рассуждать об этом), вы можете сформировать сумму Минковского двух полигонов, чтобы превратить проблему в экземпляр «point-in-convex-polygon».

Конечно, начальный тест ограничивающего прямоугольника по оси выровнено приветствовать.

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