Обход граничных точек многоугольника из соединенных треугольников

Question

У меня есть двумерная полигональная сетка из соединенных треугольников, представленных так:

• массив вершин : V = A, B, C, D, E, ...
• массив индексов , индексы вершин треугольников в группах по 3 против часовой стрелки: I = 0, 4, 3, ...
  (так, например, V[0], V[4], V[3], который A-E-D образует треугольник)

http://img694.imageshack.us/img694/8968/meshg.png Пример сетки

Теперь я хочу пересечь граничные точки в против часовой стрелки , начальная вершина не имеет значения:
G, H, A, D, C, F

Причина этого в том, что я хочу вычислять динамические 2D тени, как в этой статье: http://www.gamedev.net/reference/programming/features/2dsoftshadow/page3.asp

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

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

Спасибо, abenthy

Answer 1

Вот один из способов:

1. Найдите граничные ребра, это делается путем обхода всех ребер треугольников и удаления всех ребер, встречающихся дважды (потому что все ребра, кроме ребер границ, являются общими для двух треугольников) (также помните, (A, B) это то же ребро как (B, A)).
2. Теперь у вас есть список краевых ребер. Начните с одного из них и последовательно проходите по остальным краям, пока не найдете тот, который подключен, добавьте этот край и удалите его из списка. Повторяйте, пока граница не закроется.

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