алгоритм разбиение невыпуклой фигуры на выпуклые фигуры

[antoshka1303]

У меня есть невыпуклая фигура. Ее нужно разбить на фигуры, которые являются выпуклыми. Какие существуют алгоритмы для решения данной задачи? Всем заранее спасибо! ссылка на изображение, где указан пример разбиения http://content.foto.mail.ru/mail/zurix/2/i-24.jpg

[worm2]

Фигура, как я полагаю --- это многоугольник? (а то, если ограничивающие отрезки непрямые, то может получиться, что на конечное число частей нельзя разбить).
Первое, что приходит в голову --- это триангулировать область, и затем пытаться объединять смежные треугольники, чтобы полученные в результате объединения фигуры оставались выпуклыми (как первое, так и второе можно делать разными способами).

[Zai]

worm2 писал(а):

затем пытаться объединять смежные треугольники

Насколько я понимаю треугольник является выпуклой фигурой и триангуляции вполне достаточно.
Наиболее простой алгоритм триангуляции - поиск минимального угла в внешней однополостной петле. Устранение узла с меньшим углом дает новую петлю. Рекурентное применение данного алгоритма всегда даст искомое разбиение.

[Brukvalub]

Zai писал(а):

Наиболее простой алгоритм триангуляции - поиск минимального угла в внешней однополостной петле.

Это как? Все слова по отдельности знаю, но вот вместе - просто не укладываются в голове, и всё тут....

[antoshka1303]

а как быть если нужно построить миниамальное число триангуляций?

[Zai]

Brukvalub писал(а):

Zai писал(а):

Наиболее простой алгоритм триангуляции - поиск минимального угла в внешней однополостной петле.

Это как? Все слова по отдельности знаю, но вот вместе - просто не укладываются в голове, и всё тут....

Пусть контур буквы "З" разбит на отрезки (назовем его петлей, угловые точки - вершины). Вычислим все углы между отрезками. Вычисление углов следующее. Если линия соединяющая две соседние вершины к данной лежит внутри разбиваемой области - угол меньше 180 градусов. Если нет - больше 180 градусов. Для вырожденного треугольника 180 градусов. Находим вершину с минимальным уголом. Образуем из двух отрезков, примыкающих к вершине треугольник. Исключаем из петли два отрезка прилежащих к данной вершине. Взамен вставляем один, соединяющий две соседние вершины. Проводим повторный поиск минимального угла и исключение.

Буду очень признателен Вам, если еще что-то нужно уточнить. Данный алгоритм я использовал для конечно-элементных сеток лет десять назад, до повсеместного в настоящее время использования коммерческих генераторов сеток.

[Brukvalub]

Zai писал(а):

Буду очень признателен Вам, если еще что-то нужно уточнить.

Спасибо, теперь мне стало понятно.

[Massaraksh]

Zai писал(а):

Вычисление углов следующее. Если линия соединяющая две соседние вершины к данной лежит внутри разбиваемой области - угол меньше 180 градусов. Если нет - больше 180 градусов. Для вырожденного треугольника 180 градусов. Находим вершину с минимальным уголом. Образуем из двух отрезков, примыкающих к вершине треугольник. Исключаем из петли два отрезка прилежащих к данной вершине. Взамен вставляем один, соединяющий две соседние вершины. Проводим повторный поиск минимального угла и исключение.

Буду очень признателен Вам, если еще что-то нужно уточнить. Данный алгоритм я использовал для конечно-элементных сеток лет десять назад, до повсеместного в настоящее время использования коммерческих генераторов сеток.

Каким образом с помощью этого алгоритма можно разбить, скажем, четырёхугольник с координатами (0;10) (2;-1) (0;-0.5) (-2;-1) ?

[ewert]

Zai в сообщении #95595 писал(а):

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

И если повезёт, то запросто получаем самопересечение.

[Skeptic]

На рисунке ТС изображён ключ с отверстием, т.е. ключ содержит кольцо. Как кольцо разбить на выпуклые части?

[slavav]

Zai в сообщении #95344 писал(а):

Наиболее простой алгоритм триангуляции - поиск минимального угла в внешней однополостной петле. Устранение узла с меньшим углом дает новую петлю.

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

-- 10.07.2015, 17:17 --

Skeptic в сообщении #1035484 писал(а):

На рисунке ТС изображён ключ с отверстием, т.е. ключ содержит кольцо. Как кольцо разбить на выпуклые части?

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

[ewert]

slavav в сообщении #1035511 писал(а):

(алгоритм отрезания ушей)

А почему, кстати, его обзывают $O(n^2)$? Гарантировано ведь вроде лишь $O(n^3)$ -- ведь на каждом шаге бог весть, через сколько подшагов очередное ухо встретится.

[slavav]

ewert в сообщении #1035575 писал(а):

slavav в сообщении #1035511 писал(а):

(алгоритм отрезания ушей)

А почему, кстати, его обзывают $O(n^2)$? Гарантировано ведь вроде лишь $O(n^3)$ -- ведь на каждом шаге бог весть, через сколько подшагов очередное ухо встретится.

Это правда, если без опитимизации.
Оптимизация такая - для всех вершин вычисляется валидность диагонали (в совокупности $O(N^2)$). Флажки с валидностью собираются в кольцо. При удалении валидной вершины, надо удалить из кольца три значения и вставить два. Эти два надо вычислить. На это уйдёт $O(N)$. В совокупности, на модификацию кольца тоже уйдёт $O(N^2)$.
Ещё одна оптимизация: можно показать, что если "правильно" перемещаться по кольцу, то его вообще можно не вычислять заранее. Но это требует сложного доказательства и никому не интересно потому что сама сложность в $O(N^2)$ не интересна.

[ewert]

(Оффтоп)

slavav в сообщении #1035581 писал(а):

и никому не интересно потому что сама сложность в $O(N^2)$ не интересна.

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

[slavav]

ewert в сообщении #1035588 писал(а):

(Оффтоп)

slavav в сообщении #1035581 писал(а):

и никому не интересно потому что сама сложность в $O(N^2)$ не интересна.

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

Триангуляция в этом смысле важна и нужна. Например, для задачи Art Gallery. Не интересен медленный алгоритм. Практически полезные алгоритмы работают за $NlogN$. Теоретически триангулировать можно за линейное время.