Надеюсь, последнее не означает самопересечений исходного? Если означает, то нужно уточнить, что тут понимать под триангуляцией. Иначе так:
На входе — последовательность вершин (необязательно выпуклого, но без самопересечений) многоугольника, взятых по часовой стрелке, А1, А2, ..., Аi, ..., Аn.
Перебираем последовательность циклически, до тех пор, пока в ней > 3 вершин.
Определяем угол при текущей вершине, как разность углов наклона векторов А[i-1]А[i] и А[i]А[i+1].
Если угол > развернутого, идем дальше
иначе добавляем в результат треугольник А[i-1]А[i]А[i+1]
и выбрасываем из последовательности А[i]
Вам сюда.
Тут есть ссылка (в конце) на качественный алгоритм (на английском) даже для триангуляции многоугольников с дырками.
P.S. У меня есть статья (pdf) про построение объединений, пересечений, разностей многоугольников в среднем (не в худшем случае) за линейное время с помощью, в том числе, триангуляции. Это если тема связана с построением оверлеев.
P.P.S. Еще есть pdf статьи Скворцова "Применение триангуляции для решения задач вычислительной геометрии". Там описывается как строить триангуляцию для произвольного набора вершин, полиполилиний и полиполигонов.
Отличительной особенностью современной вычислительной геометрией является высокая востребованность во многих прикладных приложениях, поэтому возможно, неприятным открытием будет то, что многие ценные документы или публикации отсутствуют в открытом виде…
Повторюсь, очень сложная задача. Если скажешь, зачем она понадобилась, именно в такой формулировке, то можно будет помозговать насчет упрощения исходных условий.
Здравствуйте, FreshMeat, Вы писали:
FM>Здравствуйте, _Dreamer_, Вы писали:
_D_>>Нужен алгоритм триангуляции многоугольника, _D_>>корректно обрабатывающий пересечение сторон.
FM>Вообще говоря, задача является очень плохо изученной. Мне ее решение неизвестно.
Вообще говоря, задача является довольно хорошо изученной. Вот одна из неплохих работ по этой теме.
Её автор Скворцов А.В. является специалистом по вопросам траингуляции, поэтому, можно попробовать поискать там же другие его работы, касающиеся триангуляции.
Здравствуйте, FreshMeat, Вы писали:
FM>Повторюсь, очень сложная задача. Если скажешь, зачем она понадобилась, именно в такой формулировке, то можно будет помозговать насчет упрощения исходных условий.
Прога читает из файла координаты вершин, а т.к. файл создавался людьми, то о
кооректности данных говорить не приходится . Как-то корректировать данные в
файле нельзя, поэтому надо обрабатывать всю ботву(в том числе самопересечения).
Огромное спасибо за ссылку. Более ценных ресурсов по вычислительной геометрии я в последнее время не встречал. Скажи, пожалуйста, как тебя зовут, хочется включить в список благодарностей, в своей работе :)
Здравствуйте, _Dreamer_, Вы писали:
_D_>Прога читает из файла координаты вершин, а т.к. файл создавался людьми, то о _D_>кооректности данных говорить не приходится :( . Как-то корректировать данные в _D_>файле нельзя, поэтому надо обрабатывать всю ботву(в том числе самопересечения).
Понятно. Подхода в таком случае два:
1. Ввести проверку на самопересечение многоугольников и выдавать ошибку при попытке загрузки некорректного файла. Т.е. проще говоря, заставить людей исправлять свои ошибки (если это ошибки).
2. Есть просто бесценная ссылка от Анонима :). Я сегодня бегло пробежался по работам Скворцова, мужик судя по всему – второй Препарата. Посмотри как минимум сюда http://www.inf.tsu.ru/Decanat/staff.nsf/95bac94775489956c7256629003c9a9a/3267899a06bb1326c72569ba0034f4ee?OpenDocument
Непосредственного решения задачи твоей задачи, возможно, там и нет, но точно можно найти решения смежных задач, отталкиваясь от которых можно искать решение твоей.
Точно может помочь: “Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции”.
Если будут еще вопросы, пиши...
Здравствуйте, _Dreamer_, Вы писали:
D>Здравствуйте, FreshMeat, Вы писали:
FM>>Повторюсь, очень сложная задача. Если скажешь, зачем она понадобилась, именно в такой формулировке, то можно будет помозговать насчет упрощения исходных условий.
D>Прога читает из файла координаты вершин, а т.к. файл создавался людьми, то о D>кооректности данных говорить не приходится . Как-то корректировать данные в D>файле нельзя, поэтому надо обрабатывать всю ботву(в том числе самопересечения).
Ну, собственно, взять считать весь массив, найти все точки пересечения, преобразовать многоугольник в многоугольник без самопересечений. Один из вариантов, как это сделать
попробуй поиск в google библиотеки triangle-1.3 Роберта Шевчука
Re[4]: Re[3]: триангуляция (2D).
От:
Аноним
Дата:
01.06.03 12:49
Оценка:
Здравствуйте, FreshMeat, Вы писали:
FM>Огромное спасибо за ссылку. Более ценных ресурсов по вычислительной геометрии я в последнее время не встречал. Скажи, пожалуйста, как тебя зовут, хочется включить в список благодарностей, в своей работе
Вот если б я был автором, то, наверное, не отказался б от благодарности
А так, собсно, не за что.
Но всё равно спасибо.
Apapa.gif)
. Как-то корректировать данные в
