Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 12.08.2008, 12:41
Новичок

Отправить личное сообщение для Кальной Александр Посмотреть профиль Найти все сообщения от Кальной Александр
 
Регистрация: 12.08.2008
Сообщений: 4

Триангуляция и разрезание полигона
Два вопроса, двумерное пространство:

1) Разбиение многоугольника на треугольники в двумерном пространстве
2) Разрезание многоугольника. Вот есть многоугольник (представим, что это торт) и есть линия (это нож), и вот этой линией (ножом) нужно разрезать многоугольник (торт).

Помогите пожалуйста!
  #2  
Старый 12.08.2008, 14:57
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

А в чём вопрос? Как сделать триангуляцию и т.д.?
  #3  
Старый 12.08.2008, 15:21
Новичок

Отправить личное сообщение для Кальной Александр Посмотреть профиль Найти все сообщения от Кальной Александр
 
Регистрация: 12.08.2008
Сообщений: 4

Ну конечно
  #4  
Старый 12.08.2008, 16:43
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Я могу помочь по триангуляции, но надо писать конкретнее, что нужно. Описание алгоритма или готовая программа? Если программа, то на каком языке? У меня есть программы на С++, но там достаточно сложная реализация. Если нужен простой алгоритм, то могу дать краткое описание.
  #5  
Старый 12.08.2008, 18:57
Новичок

Отправить личное сообщение для Кальной Александр Посмотреть профиль Найти все сообщения от Кальной Александр
 
Регистрация: 12.08.2008
Сообщений: 4

Давай краткое описание.
А вообще, у меня есть просто набор соединенных между собой точек - многоугольник. Его нужно разбить на треугольники.
  #6  
Старый 13.08.2008, 12:14
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Даю короткое описание простого алгоритма. Последовательно просматриваются вершины многоугольника. Если угол при вершине меньше 180 градусов ( вершина выпуклая ), то делается проверка для всех несоседних рёбер - попадают ли они внутрь треугольника образованного этой вершиной и двумя соседними. Если да, то переходим к следующей вершине. Если нет, то убираем эту вершину из многоугольника, а полученный треугольник записывем в результат. С оставшимся многоугольником повторяем процедуру пока в нём больше трёх вершин.
Только учти, вариантов триангуляции много и этот алгоритм находит какой-то из них. Можно задать качество триангуляции и тогда уже искать наилучшую.
  #7  
Старый 13.08.2008, 12:23
Новичок

Отправить личное сообщение для Кальной Александр Посмотреть профиль Найти все сообщения от Кальной Александр
 
Регистрация: 12.08.2008
Сообщений: 4

А если вершина вогнутая, то ее пропускать?

Последний раз редактировалось Кальной Александр, 13.08.2008 в 12:30.
  #8  
Старый 13.08.2008, 13:42
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Да, пропускать.
  #9  
Старый 23.03.2009, 22:35
гость

 
Сообщений: n/a

просьба
Сообщение от prografix Посмотреть сообщение
Я могу помочь по триангуляции, но надо писать конкретнее, что нужно. Описание алгоритма или готовая программа? Если программа, то на каком языке? У меня есть программы на С++, но там достаточно сложная реализация. Если нужен простой алгоритм, то могу дать краткое описание.
мне нужна программа на pythone
пожалуйста скиньте на мыло: esaj@inbox.ru
  #10  
Старый 21.04.2010, 18:56
saukhster

 
Сообщений: n/a

Help
Всем привет, у меня похожая проблема. У меня есть граф (вершины + некоторые ребра). Надо проверить возможность построения триангуляции Делоне. Посоветуйте пожалуйста, как это сделать.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Разбиение полилинии на сегменты по границам полигона Andrey59 Вычислительная геометрия 6 23.05.2008 06:29
Триангуляция поверхности в 3d гость Вычислительная геометрия 2 07.03.2008 15:34
Заливка сложного полигона Non-exterior гость Вычислительная геометрия 2 23.11.2007 18:25
n-мерная триангуляция Anna Математические алгоритмы 1 03.05.2007 19:36
триангуляция делоне Denich Математические алгоритмы 1 23.10.2006 17:07