Открыть мобильное меню

Триангуляция. Деление многоугольной поверхности на треугольники.

Это всего один вариант из нескольких. Я его использовал для построения пола во Flash 3D, при создании комнаты с более чем 4 стенами, по сути поверхность любой конфигурации.

Суть алгоритма триангуляции

  • берём точки 1, 2, 3. Узнаём произведение их векторов. Если произведение положительно, то треугольник находится внутри поверхности, иначе снаружи
  • если треугольник внутри, то нужно проверить чтоб его грани не пересекались с другими гранями контура поверхности (в примере красная линия 1-5 пересекает синие линии 2-3 и 3-4).
    • если пересечений нет, то рисуем его, а внутреннюю "мертвую точку" удаляем из списка проверяемых.
    • если было пересечение какой-либо стороны проверяемого треугольника с гранью поверхности, то переходим к первому шагу и берём следующие точки, сдвигаясь на одну почасовой стрелке - 2,3,4
  • если треугольник находится снаружи (в примере треугольник 5-6-7), то переходим к первому шагу и берём следующие точки, сдвигаясь на одну почасовой стрелке - 2,3,4.
Цикл проверок точек заканчивается только когда их остаётся 3, то есть это последний треугольник.

Для тех кто программирует на AS3, можете скачать класс Triangulation as или zip, который был написан как раз для триангуляции выше упомянутого пола, для 3D комнаты.