Как найти все многоугольники заданных вершин? - PullRequest
Новая
       36

Как найти все многоугольники заданных вершин?

3 голосов
/ 07 июня 2019

У меня есть список вершин, и я знаю связи между ними. Я пытаюсь найти все многоугольники вершин. Эти многоугольники не должны перекрываться.

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

В основном я хочу найти следующие многоугольники: 

* A, E, G, C, D, A
* E, F, G,  E 
* E, B, F, E

Как я могу решить выбрать G-путь, когда я начинаю с A, затем дохожу до вершины E?

P.S .: Я открыт для подхода, отличного от моего, если мой подход не подходит для этой проблемы или есть лучшие / более простые решения для этого

SampleImg

1 Ответ

1 голос
/ 10 июня 2019

В соответствии с вашим примером вы пытаетесь найти грани плоского графа, определяемые его вершинами и ребрами.

Шаг 1. Замените все свои-направленные ребра парой направленных ребер (дуг), соединяющих вершины в обоих направлениях.Для каждой дуги (v1 -> v2) найдите следующую дугу (v2 -> v3), чтобы обе эти дуги имели одинаковую грань слева из них - это может бытьделается путем вычисления углов между дугами и осью (скажем) OX и упорядочением их по часовой стрелке (или против часовой стрелки).Отметьте все дуги как «неиспользованные».

Шаг 2. Подберите любую «неиспользуемую» дугу и следуйте по следующим дугам один за другим, пока не достигнете начала начальной дуги - вы 'Я получу цикл, ограничивающий лицо.Вы нашли новое лицо со всеми его дугами / вершинами.Отметьте все дуги в этом цикле как «используемые».Повторяйте до тех пор, пока не останется «неиспользуемых» дуг.

Возвращаясь к своему примеру - вы получите следующие дуги: 

A -> E, E -> A
A -> D, D -> A
B -> E, E -> B
B -> F, F -> B
C -> D, D -> C
C -> G, G -> C
E -> F, F -> E
E -> G, G -> E
F -> G, G -> F

Примеры следующие дуги:

  • (D -> C) - следующая дуга для (A -> D)
  • (C -> G) - следующая дуга для (D -> C)
  • (G -> E) - следующая дуга для (C -> G)
  • и т. Д. *

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

...