Привет всем!
Недавно мне понадобилось для задач МКЭ разобраться с триангуцией. Проблема такая: пользователь в некоем редакторе рисует свою область в виде многоугольника, я её триангулирую. Я так понимаю, что моя проблема решается с помощью триангуляции Делоне? (или это не так?)
Прочитал все, что есть на сайте algolist.manual.ru про триангулцию, прочитал статью Скворцова "Обзор алгоритмов трингуляции Делоне". В связи с этим возник такой вот глупый вопрос: когда идет речь о триангуляции Делоне, то говорится, что есть некоторый набор точек (Триангуляция для конечного набора точек S), и по этим точкам строится триангуляция. Но! у меня ведь нет никакго множества точек!, пользователь просто нарисовал, например, четырехугольник и все, как тогда для такого четырехугольника построить триангуляцию Делоне?
Здравствуйте, Yuri, Вы писали:
Y>Привет всем! Y>Недавно мне понадобилось для задач МКЭ разобраться с триангуцией. Проблема такая: пользователь в некоем редакторе рисует свою область в виде многоугольника, я её триангулирую. Я так понимаю, что моя проблема решается с помощью триангуляции Делоне? (или это не так?)
Y>Прочитал все, что есть на сайте algolist.manual.ru про триангулцию, прочитал статью Скворцова "Обзор алгоритмов трингуляции Делоне". В связи с этим возник такой вот глупый вопрос: когда идет речь о триангуляции Делоне, то говорится, что есть некоторый набор точек (Триангуляция для конечного набора точек S), и по этим точкам строится триангуляция. Но! у меня ведь нет никакго множества точек!, пользователь просто нарисовал, например, четырехугольник и все, как тогда для такого четырехугольника построить триангуляцию Делоне?
А разве МКЭ не говорит какие треугольники нужно брать. Кажется эти точки расчитываются в зависимости от нагрузок
Здравствуйте, Yuri, Вы писали:
Y>Привет всем! Y>Недавно мне понадобилось для задач МКЭ разобраться с триангуцией. Проблема такая: пользователь в некоем редакторе рисует свою область в виде многоугольника, я её триангулирую. Я так понимаю, что моя проблема решается с помощью триангуляции Делоне? (или это не так?)
Y> Но! у меня ведь нет никакго множества точек!, пользователь просто нарисовал, например, четырехугольник и все, как тогда для такого четырехугольника построить триангуляцию Делоне?
Тебе критично, чтобы триангуляция была именно триангуляцией Делоне?
Если да, посмотри другие работы Скворцова. В одной из них, "Алгоритмы построения триангуляции с ограничениями", содержится описание подходящего алгоритма триангуляции — "... в общем случае в задаче триангуляции с ограничениями задается множество отрезков, с которыми ребра триангуляции не пересекаются, а только проходят по ним...".
Если нет, то можно поискать алгоритмы триангуляции многоугльников. Потребуется помощь, пиши.
Здравствуйте, Yuri, Вы писали:
Y>Привет всем! Y>Недавно мне понадобилось для задач МКЭ разобраться с триангуцией. Проблема такая: пользователь в некоем редакторе рисует свою область в виде многоугольника, я её триангулирую. Я так понимаю, что моя проблема решается с помощью триангуляции Делоне? (или это не так?)
Y>Прочитал все, что есть на сайте algolist.manual.ru про триангулцию, прочитал статью Скворцова "Обзор алгоритмов трингуляции Делоне". В связи с этим возник такой вот глупый вопрос: когда идет речь о триангуляции Делоне, то говорится, что есть некоторый набор точек (Триангуляция для конечного набора точек S), и по этим точкам строится триангуляция. Но! у меня ведь нет никакго множества точек!, пользователь просто нарисовал, например, четырехугольник и все, как тогда для такого четырехугольника построить триангуляцию Делоне?
Правильный ответ: Триангуляция Делоне — это триангуляция области (а не многоугольника!!!), содержащей некоторый набор точек S. В Вашем случае набором точек являются вершины многоугольника. Недостаток триангуляции Делоне — возможность появления треугольников, пересекающих границу многоугольника, если многоугольник невыпуклый. Поэтому для триангуляции произвольного многоугольника рекомендуется использовать другие алгоритмы, например разбиение многоугольника на выпуклые части с последующей триангуляцией каждой из них (триангуляция выпуклого многоугольника — задача тривиальная).
Здравствуйте, Олейник Олег, Вы писали:
ОО>Правильный ответ: Триангуляция Делоне — это триангуляция области (а не многоугольника!!!), содержащей некоторый набор точек S.
А что такое область?
Def. Триангуляцией называется планарный граф G, все внутренние области которого являются треугольниками.
При чем тут набор точек?
ОО>Поэтому для триангуляции произвольного многоугольника рекомендуется использовать другие алгоритмы, например разбиение многоугольника на выпуклые части с последующей триангуляцией каждой из них (триангуляция выпуклого многоугольника — задача тривиальная).
Не лучший по вычислительной сложности и точности алгоритм (возможно образование узких, вытянутых треугольников), но для начала вполне сгодится.
