Спасибо, а есть что-то готовое на паскале? Демо программка по ссылке не загружает полигоны, лишь генерит случайные. Мне придется перекладывать исходники на Делфи только, чтобы оценить подойдет ли алгоритм для моих полигонов.
Гугл выдает ссылки на стандартные функции OpenGL и других граф. библиотек, мне же нужно получить на выходе список индексов треугольников.
MBo советовал примеры на С. Судя по демке работает неплохо, жаль что не могу загрузить свои полигоны, программа хоть и понимает WaveFront OBJ файлы, открывает их, однако при демонстрации алгоритмов все равно генерит случайные фигуры.
Источник: delphimaster.net
Триангуляция многоугольников
Задача: разбить произвольный многоугольник на треугольники.
- Клас, что-то наподобие списка, где можно двигаться вперед-назад и конец соединен с началом. То есть замкнутый круг, элементами которого будут объекты описаны пунктом ниже.
- Клас для представления точки. В нем, как полагается, должны быть координаты х и у. Так же еще одно поле в котором записано значение угла соответствующего этой точке в многоугольнике
- Функция, на вход которой идут два векторы, а на выход — угол между ними
- Функция, на вход которой идет точка и треугольник, на выход — признак, лежит ли точка внутри треугольника.
- Создаем пустой список для хранения временных треугольников.
Если точка слева от «рабочий» (p(i)->left) имеет угол меньше чем 180 градусов и треугольник (p(i), p(i)->left, p(i)->left->left) не содержит внутри себя других точек многоугольника — заносим этот треугольник в наш временный список.
Если точка справа от «рабочий» (p(i)->right) имеет угол меньше чем 180 градусов и треугольник (p(i), p(i)->right, p(i)->right->right) не содержит внутри себя других точек многоугольника — заносим этот треугольник в наш временный список.
Если «рабочая» точка (p(i)) имеет угол меньше чем 180 градусов и треугольник ( p(i)->left, p(i),p(i)->right) не содержит внутри себя других точек многоугольника — заносим этот треугольник в наш временный список. - Если временный список не содержит треугольников — выбираем вместо «рабочий», точку слева от нее и возвращаемся к первому пункту.
Если содержит — выбираем треугольник с минимальной разницей между минимальным и максимальным углом (нужно пересчитать значение углов), заносим его в список result, удаляем из points среднюю точку из треугольника который выбрали а соседним точкам от нее (в points) пересчитываем значения углов, первую точку выбираем в качестве «рабочей» (p(i)).Если в points осталось только две точки — прекращаем работу, список треугольников содержится в res, иначе возвращаемся к первому пункту.
Треугольник Паскаля
Теперь пара слов об оптимизации алгоритма.
Треугольники в четырехугольники в Blender
На втором этапе выбирается треугольник с минимальной разницей между минимальным и максимальным углом для того, чтобы треугольник был максимально подобный к правильному, иногда это важно. Если же вам нет разницы как выглядит треугольник — тогда можно не создавать временный список треугольников, а выбрать первый из трех возможных треугольников который не содержит внутри себя другую точку многоугольника и угол, который образует средняя точка треугольника в многоугольнике меньше 180 градусов. Такое упрощение значительно снизит вычислительные затраты.
Еще, если уверены, что многоугольник выпуклый — тогда не нужно проверь содержит ли треугольник другие точки многоугольника.
П.С. Я не встречал такой алгоритм на просторах инета, хотя и уверен, что что-то подобное уже есть.
Источник: habr.com
Написать программу которая разбивает любой полигон на треугольники паскаль
По книге Laszlo
«Вычислительная геометрия и компьютерная графика на С++»
Используем метод «разделяй и властвуй» для триангуляции произвольного полигона Р. Идея заключается в расщеплении полигона Р вдоль некоторой хорды и затем в рекурсивной триангуляции получившихся двух подполигонов. В конце возникает ситуация, когда подлежащий триангуляции полигон является треугольником. Алгоритм менее эффективен, чем способ, использующий расщепление полигона на монотонные части и их поочередной триангуляции, но его гораздо проще запрограммировать. Алгоритм основан на непосредственном доказательстве следующей теоремы:
Теорема о триангуляции полигона:
n-угольник может быть разбит на n — 2 треугольника проведением n — 3 хорд.
Почувствовать справедливость этой теоремы можно путем выполнения триангуляции для некоторого придуманного полигона. Наиболее просто можно осуществить триангуляцию выпуклого полигона. Нужно выбрать одну из n вершин полигона и соединить ее с каждой из n — 3 несоседних вершин, получив n — 2 треугольников. Другой способ триангуляции выпуклого полигона основан на том факте, что каждая диагональ выпуклого полигона является его хордой: необходимо расщепить полигон вдоль любой диагонали и затем рекурсивно выполнить триангуляцию полученных двух выпуклых полигонов.
Триангуляция невыпуклых полигонов не так проста. Действительно, утверждение, что можно осуществить триангуляцию любого полигона, не так очевидна, если учитывать вогнутые полигоны. Мы будем доказывать теорему о триангуляции как для того, чтобы убедиться в справедливости теоремы, так и для мотивации разработки алгоритма триангуляции.
Доказательство теоремы ведется на основе индукции числа n, количества сторон полигона. Теорема тривиально справедлива для n = 3, что является основой для индукции. Так что пусть Р будет полигон с числом сторон n >= 4 и предположим (в качестве гипотезы индукции), что условия теоремы удовлетворяются для всех полигонов с числом сторон меньше, чем n. Будем искать хорду полигона Р.
Пусть b будет некоторая выпуклая вершина и пусть а и b будут ее соседи. Могут возникнуть две ситуации (рис. 1). В первом случае диагональ ac является хордой Р. Пусть Р’ будет n-1-сторонний полигон, получающийся в результате отсечения треугольника abc. По гипотезе индукции существует набор из n — 4 хорд, которые делят полигон на n — 3 треугольников.
Рис. 1: Две ситуации, рассматриваемые при доказательстве теоремы о триангуляции
Добавляя к ним хорду ac и треугольник abc, мы получим набор из n-2 хорд, которые делят исходный полигон Р на n—2 треугольника.
Во втором случае диагональ ac не является хордой Р, полагая, что внутрь треугольника abc должна попасть по крайней мере одна вершина полигона Р. Из всех вершин внутри треугольника abc пусть d будет вершиной, расположенной дальше всех от прямой линии со, . Эту вершину d будем называть вторгающейся вершиной. При таком выборе вершины d диагональ bd должна лежать внутри Р — ибо если бы какое-либо другое ребро полигона вторглось бы между b и d, то по крайней мере один из его концов должен находиться внутри треугольника abc на расстоянии от прямой са дальше, чем вершина d, что противоречило бы нашему выбору d. Следовательно, отрезок bd должен быть хордой.
Теперь хорда bd делит полигон Р на два меньших полигона P1 и Р2 с n1 и n2 сторонами соответственно. Поскольку n1 + n2 = n + 2 и n1,n2>=3, то каждое из n1 и n2 должно быть меньше n. Теперь мы можем применить гипотезу индукции к P1 и к P2. Подсчет числа хорд приводит к (n1 — 3) + (n2 — 3) + 1 = n — 3 хордам, а подсчет треугольников — к общему числу (n1 — 2) + (n2 — 2) = n — 2 треугольников. Теорема о триангуляции доказана.
* — Реализация использует классы, описанные в разделе ‘Структуры геометрических данных’.
Вышеприведенное доказательство теоремы прямо подводит к следующей программе для триангуляции полигонов. Программе передается полигон р и она возвращает список треугольников, представляющих его триангуляцию. Треугольники накапливаются в списке triangles:
List *triangulate (Polygon List*triangles = new List; if (p.size() == 3) triangles->append( else < findConvexVertex(p); Vertex *d = findIntrudingVertex(p); if (d == NULL) < // нет вторгающихся вершин Vertex *c = p.neighbor(CLOCKWISE); p.advance (COUNTER_CLOCKWISE); Polygon *q = p.split(c); triangles->append(triangulate(p)); triangles->append(q); > else < // d — вторгающаяся вершина Polygon *q = p.split(d); triangles->append (triangulate (*q)); triangles->append (triangulate (p)); > > return triangles; >
Используются функции findConvexVertex и findIntrudingVertex. При обработке полигона р функция findConvexVertex перемещает окно в полигоне р на некоторую выпуклую вершину. Это реализуется путем перемещения трех окон a, b и с, расположенных над тремя соседними вершинами, в направлении по часовой стрелке вокруг полигона до тех пор, пока не будет обнаружен поворот направо в вершине b:
void findConvexVertex (Polygon Vertex *a = p.neighbor (COUNTER_CLOCKWISE); Vertex *b = p.v(); Vertex *c = p.neighbor (CLOCKWISE); while (c->classify(*a, *b) != RIGHT) < a = b; b = p.aduance(CLOCKWISE); с = p.neighbor(CLOCKWISE); >>
В функцию findlntrudingVertex передается полигон p, для которого предполагается, что его текущая вершина является выпуклой. Функция возвращает указатель на вторгающуюся вершину, если она существует или NULL в противном случае.
Vertex *findIntrudingVertex (Polygon Vertex *a = p.neighbor(COUNTER_CLOCKWISE); Vertex *b = p.v(); Vertex *c = p.advance (CLOCKWISE); Vertex *d = NULL; // лучший кандидат на данный момент double bestD = -1.0; // расстояние до лучшего кандидата Edge ca(c->point(), a->point()); Vertex *v = p.advance (CLOCKWISE); while (v != a) < if (pointInTriangle(*v, *a, *b, *c)) < double dist = v->distance (ca); if (dist > bestD) < d = v; bestD = dist; >> v = p.advance (CLOCKWISE); > p.setV(b); return d; >
Функция pointInTriangle проверяет точки на попадание внутрь треугольника: функция возвращает значение TRUE, если точка р находится внутри треугольника с вершинами в точках а, b и с, в противном случае возвращаемое значение равно FALSE.
bool pointInTriangle (Point p, Point a, Point b, Point c)
Заметьте, что триангуляция, формируемая программой triangulate, зависит как от вида передаваемого ей полигона, так и от начальной текущей точки этого полигона. На рис. 2 представлены три различных результата триангуляции одного и того же полигона путем изменения его начальной текущей вершины.
При обработке n-угольника каждая из функций findConvexVertex и findIntrudingVertex затрачивает время О(n). Если не найдено ни одной вторгающейся вершины, то одиночный треугольник удаляется из п-угольника и подвергается рекурсивной триангуляции результирующий n-1-угольник. В худшем случае вторгающаяся вершина никогда не обнаруживается в процессе выполнения программы и размер полигона уменьшается на единицу на каждом последующем шаге. Это приводит к времени работы в худшем случае Т(n) = n + (n -1) + . + 1, что равно O(n 2 ). Такой самый плохой показатель получается при триангуляции выпуклого полигона.
Похоже, что программа будет работать значительно быстрее, если обнаруживается вторгающаяся вершина, поскольку в этом случае задача разбивается на две подзадачи, вполне возможно, примерно равного размера. Поскольку только вогнутая вершина может вторгаться в треугольник, то программа работает быстрее, если полигон имеет много вогнутых вершин. Однако не представляет труда составить такой полигон с Omega(n) вогнутыми вершинами, для триангуляции которого потребуется время Omega(n 2 ), хотя вогнутые вершины и существуют, но алгоритм их не обнаруживает или находит такие «плохие», что они приводят к разбиению на очень неравные части, одну большую, а другую маленькую.
Источник: algolist.ru