Что было бы самым эффективным способом обнаружения всех замкнутых путей в коллекции сегментов и коннекторов?

Question

У нас есть набор данных, который состоит из разъемов и сегментов. Каждый сегмент имеет ровно два разъема, но каждый разъем может принадлежать ноль или более сегментов (т.е. разъем «A» на левом изображении ниже не имеет сегментов, а разъем «M» имеет три, MR, ML и MN.)

Понятно, что везде, где встречаются или пересекаются какие-либо линии, будет разъем, поэтому нам не нужно беспокоиться о четных/нечетных правилах, перекрывающихся или частично закрытых полигонах и т. Д., Поскольку они не применяются.

Короче говоря, мы пытаемся идентифицировать все созданные многоугольники (цветные фигуры в правильном изображении.) Я считаю, что это может быть выполнено в два этапа.

Часть 1: Удаление лишних пунктов

Автономные разъемы (разъем «А» здесь) можно просто удалить, поскольку они не могут быть частью очертить фигуры.

Плавающие конечные точки, ссылающиеся на один сегмент (разъемы «B» и «E») также могут быть удалены, так как они также не могут быть частью контура фигуры. Это также удалит связанные сегменты (B-C и E-D).

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

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

Шаг 2: многоугольник Обнаружение

Каждый сегмент может быть прослежено в двух направлениях. Например, сегмент, соединяющий «O» и «P», может быть либо O-P, либо P-O. Выбрав направление трассы по часовой стрелке, O-P будет принадлежать полигону O-P-Q-N, тогда как P-O будет принадлежать многоугольнику P-O-I.

Следующая логика предполагает направление следа по часовой стрелке.

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

Рассмотрите случай квадрата, диагонально разделенного на два треугольника. Трассировка каждого сегмента дважды - один раз в каждом направлении - вы получите три потенциально допустимых полигона: квадрат и два треугольника. Треугольники будут иметь треугольник с положительным углом, который говорит вам, что они действительны, но треугольник угла квадрата будет отрицательным, говоря вам, что это содержащий полигон.

Примечание: содержащий многоугольник может быть равен допустимому полигону. Это будет просто «ранено» в противоположном направлении.

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

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

Например, если вы начали с «J» и прорисовывали вокруг против часовой стрелки, вы бы прошли через «I», «H», затем «G», затем «F», после чего вы вернетесь в «H». Вы только что нашли полигон H-G-F, который имеет отрицательный угол, поэтому вы знаете, что он содержит многоугольник. Удалите эти три сегмента из своего стека и продолжайте. Теперь вы снова нажмете «Я». В этом случае вы уже посетили этот же сегмент во время этого прохода, но в другом направлении, просто удалите этот сегмент полностью из своего стека и продолжайте дальше, рядом с «O», затем «N» и т. Д. В конце концов вы станете назад на 'J'.

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

Наконец, проверьте каждый из них, содержащий полигон, чтобы узнать, попадает ли он в любой допустимый полигон. Если это так, исключите его из этого допустимого многоугольника, создающего составной путь. В приведенном здесь примере, содержащий многоугольник H-G-F, содержится в действительном голубом полигоне, поэтому его следует исключить. Обратите внимание, что существует также допустимый многоугольник H-F-G, который отмечен красным цветом здесь.

В любом случае, это то, что я придумал, но мне интересно, есть ли лучший/более простой способ. Мысли?

Answer 1

Подсказка:

Ваша проблема имеет геометрический аспект (не чисто связности), потому что лица не могут перекрывать друг друга, и, как известно, быть простым. Я бы рекомендовал использовать sweepline.

Первая очистка для сброса всех плавающих конечных точек.

Затем рассмотрим горизонтальную линию, которая перемещается сверху вниз, вершина по вершине. На каждой позиции seewpline он включает или пересекает несколько сегментов. Сортируя все вершины/пересечения слева направо, вы получаете неперекрывающиеся сегменты линии.

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

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

R K  J 
RM KL G  JI 
M L GF GH JI 
MN F GH JI 
MN  H JI 
    N O  I 
    NQ P 
    Q 

(пары обозначают перекрестки).

Исходя из этого, вы должны быть в состоянии восстановить левый/правый контуры из соображений связности

R M | K L 
K L M N | G F H | G H | J I (and embedded G F H | G H) 
N Q | O P Q 
O P | I P 

Вот график, который вы получите, связав концы и пересечения существующих ребер из scanline to scanline.

И после очистки, удаления промежуточных вершин: