Преобразование ненаправленной Graph в Заявлении Mesh

Question

:

Я создаю программу, которая позволяет пользователям выкладывать свои собственные ненаправленный граф (узлы и ребра). Когда они нажимают определенную кнопку, я хочу создать триангулированную сетку из каждого «пробела» на графике. Вот два изображения, которые должны дать вам представление о том, что я после:

Есть несколько предостережений:

• Поскольку пользователи имеют полный контроль, я могу получить 3 , 4, 5 ... N односторонние пространства
• пользователь может создавать либо выпуклые или вогнутые формы
• применение делается в единстве с C#

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

Буду признателен за любую помощь, которую вы можете дать мне с этим наездником. Чтобы помочь вам, я уже знаком с выпуклыми алгоритмами и триангуляцией корпуса.

Update:

Я не могу размещать код, потому что я под NDA для этого проекта, но структуры данных довольно просты.

Узлы имеют положение (вектор 3, но y всегда 0) и список связанных ребер.

Кромки имеют первый узел, второй узел и позицию (средняя точка).

Я хочу создать объект Mesh для каждого пробела. Этот сетчатый объект имеет статический массив вершин (вектор 3s) и статический массив треугольников (которые являются int и относятся к индексам вершин).

Answer 1

Ваш подход хороший. Есть несколько моментов для уточнения.

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

Обратите внимание, что каждое ребро будет иметь две грани. Итак, если вы будете следовать за лицом по наиболее острому углу, чем вы следите за этими краями только с одной стороны. Решение состоит в том, чтобы создать ориентированный граф с одинаковыми узлами и для каждого ребра создать два ребра в обоих направлениях. В общем, тот же график, что и начальный граф, но ребра удваиваются. Алгоритм:

take one (directed) edge 
follow it in same way by smallest angle 
make faces of that cycle 
remove face (directed) edges from graph 
repeat procedure until there are edges. 

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

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

Update

Поскольку каждый полигон и полигон края передается только один раз, я думаю, что это вполне оптимальным решением. Всего несколько возможностей.

Главным шагом в алгоритме является выбор следующего края из последнего посещенного узла. Простая реализация состоит в том, чтобы рассчитать углы внешних краев и сделать следующий. Расчет углов может выполняться один раз, а не каждый раз, когда край посещает узел, и даже отображение in-edge -> out-edge может быть выполнено для узла.

Не нужно создавать новый ориентированный граф, достаточно хранить данные направления для каждого ребра. Достаточно двух булевых переменных, по одному для каждого направления. С этим первым шагом, выбирая не посещенный край для запуска нового многоугольника, становится более сложным. Это может быть покрыто, если вычисление верхнего угла используется путем удаления посещенных углов с карты и узла маркировки как видимых, если на карте больше нет углов.