Обнаружение региона на основе полилиний ВТК

Question

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

область интересов http://oi43.tinypic.com/vwsug5.jpg

Для любой случайной точки rp в области мне нужночтобы выяснить, в каком регионе он находится.

До сих пор я пытался:

• Расчет ближайшей точки vtk к rp, нахождение кривой, к которой он принадлежит, и затемвычисление, если rp находится слева или справа от кривой.Это не работает для замкнутых кривых, таких как окружающая область 1 на рисунке выше, особенно если они не являются непрерывными (т. Е. Прямоугольник)
• Разбивка домена на сегменты: первоначально те сегменты, которыесодержат точку vtk, заполненную флагами региона, связанными с этой точкой;остальные ведра затем заполняются на основе их соседей.Контейнер, в который попадает rp, возвращает свой набор флагов.Однако у меня возникают проблемы с тем, чтобы это работало, когда в корзине содержится более одного флага региона (т. Е. Когда rp находится близко к линии).

Я предполагаю, что это, вероятно, решенная проблема, но я не совсем уверен, где искать.Я думал о проблеме точка-многоугольник , но я имею дело с кривыми, а не с многоугольниками.Другие идеи включают трассировку лучей, но кажется, что она больше подходит для 3D.

Кто-нибудь может предложить альтернативу или модификацию того, что я пробовал?

Answer 1

Каждая линия по периметру интересующего поддомена (SDOI) должна иметь SDOI в качестве одного из граничащих доменов.

• Таким образом, вы можете заполнить (или расширить круг) область, в которой находится rp.
• Найдите общую область, соседствующую со всеми этими линиями.
• Это ты, SDOI.

UNLESS:

Особый случай: rp находится в кольце (т. Е. Домен 1). Таким образом, мы не знаем, находимся ли мы на ринге или за его пределами. Мы знаем, что находимся в этом «особом случае», потому что только два домена возвращаются из вышеуказанного метода (1 или 2), но мы не знаем, какой из них.

Решение:

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