Войти
ПрограммированиеФорумОбщее

Триангуляция невыпуклых полигонов. Алгоритмы ? (2 стр)

Страницы: 1 2 3 Следующая »
#15
12:44, 23 янв 2008

Gladiator
то полигол выпуклый==триангуляция выпуклого полигона не требует никаких проверок просто отрезаеш по одной вершине пока полигон не выродится в треугольник

#16
12:53, 23 янв 2008

Gladiator
угу. в наихудшем.
Зато работает наверняка :)

#17
13:36, 23 янв 2008

uss

Ты, можно сказать, рассказал частный случай алгоритма Зейделя ибо он тоже примерно так же делит. Правда зачем-то еще делит на трапеции.
Тоесть 1. Делит на трапеции полигон. 2. Проводит нужные диагонали. -- > получаем монотонный полигон, который можно спокойно триангулировать за O(N). Но там много непонятных деталей..

Но тут возникает у меня такие вопросы:
Допустим мы всё-таки разделили многоугольник на конечное число выпуклых многоугольников. Вопрос как с ними работать ? :) Надо же их как-то выделить во всей этой совокупность многоугольников. А еще: как узнать внутренний у тебя сейчас угол или внешний ? :)

#18
13:54, 23 янв 2008

Gladiator
общее у предложеного мной и зейделем слово триангуляция :)
теперь повторюсь....ты отресаеш от полигона полигон ПРОИЗВОЛЬНОЙ формы он может быть как выпуклый так и не выпуклый, он может быть гораздо больше по количеству вершин чем тот полигон который остаётся как первичный

для педставления полигона в памяти как по мне наилучшим является двусвязный список ( когда ты разрезаеш полигон на 2 части то никаких копирований не нада просто перенаправляеш указатели)

по поводу угла читай на форуме и копайся в школьном курсе по векторнам (синус,косинус двух векторов)

#19
14:31, 23 янв 2008

Gladiator
Если скорость особо не нужна, то проще всего, наверно, реализовать квадратичный алгоритм "Обрезания ушей" (otectomy).
Алгоритм, разбивающий полигоны на монотонные, работет за O(N*log(N)), он тоже не сильно сложный.

#20
14:36, 23 янв 2008

uss
Это всё понятно было и так.. Но как ты определишь внутренний у тебя угол или внешний ? Причем тут угол между 2-мя векторами.
Вот пример:
Проблема многоугольника | Триангуляция невыпуклых полигонов. Алгоритмы ?
Как тут поймешь какой угол брать alpha' или alpha '' ?
Визуально, всё просто, но я могу написать такой пример что это будет не так просто..

#21
15:57, 23 янв 2008

Gladiator
возмём 3 последовательные точки а, б, с
если составить из них 2 вектора аб и бс а потом векторно перемножить то....
вектор результата будет перпендикулярен этим двум векторам если он направлен вниз от полигона то угол больше 180 градусов и наоборот

#22
16:41, 23 янв 2008

uss
=(
Прости, либо я ничего не понимаю, либо ты не прав. Вот пример:
Триангуляция. Продолжение | Триангуляция невыпуклых полигонов. Алгоритмы ?

аб х бв даст alpha' насколько я понимаю а нужно alpha''.

#23
16:47, 23 янв 2008

Gladiator

обход у полигонов изначально ПО ЧАСОВОЙ СТРЕЛКЕ
хочеш чтоб был против часовой стрелки значит у тебя результат будет трактоватся наоборот

Никулин Е А -  Компьютерная геометрия и алгоритмы машинной графики
там есть все ответы на твои вопросы

#24
16:57, 23 янв 2008

uss
ok. Пасиб )

#25
17:33, 23 янв 2008

Хотя разницы особой не вижу

#26
1:13, 19 мар 2008

Привет. Мне когда-то пришлось выдумать свой алгоритм триангуляции, а теперь вот очень надо бы какой-нибудь доклад на конференции проделать, хочу узнать, мой алгоритм давно уже известен и я велосипед выдумал или есть всё же что-то новое?
Алгоритм очень простой. Было условие: чтобы минимальный угол не был меньше некоторого значения, и площадь также не превышала некоторое S. Считаем длину стороны равностороннего треугольника площадью S - пускай будет а. Разбиваем стороны полигона на одинаковые отрезки длиной не более а. Получаем набор точек по периметру полигона. Перебираем все пары противоположных точек и выбираем ту пару, расстояние между которыми меньше, чем у остальных пар. Противоположные - это если, например, у нас получилось 10 точек, то пары противоположных: 1 и 6, 2 и 7, 3 и 8, 4 и 9, 5 и 10. По отрезку, соединяющему выбраную пару, разбиваем полигон на 2. Далее рекурсия.
Получается приблизительно вот так:
триангуляция | Триангуляция невыпуклых полигонов. Алгоритмы ?
Триангулирует не слишком невыпуклые полигоны.
Мне показалось, что здесь есть люди корорые разбираються в триангуляции, подскажите, это можно кому-то показывать?

#27
17:55, 27 мар 2008

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

P.S. вчера тоже столкнулся с триангулированием, проблема в том чтоб просто построить невыпуклый четырехугольник правильно, правда я и не думал пока, крутятся мысли о расстоянии между точками... что то вроде если расстояние от одной до двух соседних больше чем расстояние до точки соседствующей уже с ними то соединить с этой последней точкой, так тока что в бошке проскользнуло) вдруг пригодится)

#28
21:39, 27 мар 2008

есть очень большой pdf на эту тему, работа двух каких-то ученых чуваков... описаны все ситуации и подходы... на английском... если интересно вышлю на мыло

#29
22:19, 6 мая 2008

Yurko
Ваш алгоритм решает классическую конечно-элементную задачу. Алгоритмы с такими же задачами используются в таких расчетных комплексах как AnsysWorker, Cosmos.

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

Freckle
Не могли бы вы поподробнее описать алгоритм, которым вы пользуютесь?

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.