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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.12.2009, 21:01
гость

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

пересечение многоугольников
народ, у кого есть алгоритм построения пересечения двух выпуклых многоугольников на каком-нибудь языке алгоритмов, срочно нужно, помогите пжл
  #2  
Старый 04.12.2009, 22:15
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

один из алгоритмов описан в книге O'Rourke Computational Geometry in C
  #3  
Старый 05.12.2009, 12:17
Местный

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

Предлагаю следующее решение этой задачи. Построим по сторонам первого многоугольника прямые и затем обрежим этими прямыми второй многоугольник. Обрезание сделаем так. Каждая прямая делит плоскость на 2 полуплоскости - положительную и отрицательную. Будем считать, что многоугольник находится в отрицательной полуплоскости. Из каждой стороны второго могоугольника оставляем часть лежащую в отрицательной полуплоскости. Полученные разрывы соединяем отрезкоми. Получим снова многоугольник.
Этот метод пересечения многоугольников подходит и для случая, когда один из многоугольников невыпуклый.
  #4  
Старый 05.12.2009, 13:02
гость

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

т.е нужно составить по координатам точек уравнения прямой для каждой пары точек для обоих многоугольников, и производить полный перебор?
  #5  
Старый 05.12.2009, 13:03
гость

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

[quote=гость;9447]т.е нужно составить по координатам точек уравнения прямой для каждой пары точек для обоих многоугольников, и производить полный перебор пересечения двух прямых
  #6  
Старый 05.12.2009, 13:03
гость

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

т.е нужно составить по координатам точек уравнения прямой для каждой пары точек для обоих многоугольников, и производить полный перебор пересечения двух прямых
  #7  
Старый 05.12.2009, 14:04
Местный

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

Сообщение от гость Посмотреть сообщение
т.е нужно составить по координатам точек уравнения прямой для каждой пары точек для обоих многоугольников, и производить полный перебор?
Нет. Уравнения прямой надо сделать только для одного многоугольника. Он должен быть выпуклым, а второй не обязательно. Затем одной прямой обрезать рёбра второго многоугольника ( здесь нужно будет считать расстояния от вершины многоугольника до прямой ) и если в результате будут нестыковки ребер добавить недостающие. Аналогично сделать с остальными прямыми.
  #8  
Старый 05.12.2009, 15:33
гость

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

Сообщение от prografix Посмотреть сообщение
Затем одной прямой обрезать рёбра второго многоугольника ( здесь нужно будет считать расстояния от вершины многоугольника до прямой ) и если в результате будут нестыковки ребер добавить недостающие. Аналогично сделать с остальными прямыми.
для чего нужно считать расстояния от вершины многоугольника до прямой?
  #9  
Старый 05.12.2009, 19:22
Местный

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

Для того чтобы отрезать ребро. Если обе вершины ребра лежат в отрицательной полуплоскости, то ребро сохраняется полностью. Если обе вершины ребра лежат в положительной полуплоскости, то ребро выбрасывается. Если одна вершина ребра лежат в отрицательной полуплоскости, а другая в положительной полуплоскости, то ребро делится на две части, одна из которых сохраняется и деление это происходит пропорционально расстоянию вершин от прямой. Ещё из этого следует, что рёбра лучше хранить в списке, т.к. они могут добавляться и удаляться в разных местах.
  #10  
Старый 05.12.2009, 22:23
гость

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

а может у кого-нить код или формальная запись алгоритма найдется, можно на псевдоСи
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вычитание многоугольников BOB4uK Математические алгоритмы 3 19.01.2009 17:33
Сравнение формы многоугольников гость Вычислительная геометрия 1 15.05.2008 13:31
Поиск многоугольников на плоскости гость Вычислительная геометрия 4 12.05.2008 19:39
площадь пересечения многоугольников Artemon Вычислительная геометрия 1 20.03.2008 13:45
Пересечение отрезков гость Реализация, исходники, языки 1 26.12.2007 00:29