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

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

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

Отправить личное сообщение для Nymph666 Посмотреть профиль Найти все сообщения от Nymph666
 
Регистрация: 28.11.2007
Сообщений: 5

Многоугольники
Поможите пжлста!
Задачка такая: даны простые(т.е.могут быть вогнутыми, но без самопересечений) многоугольники(их может быть хоть сколько). Каждый из них задается списком точек. Нужно найти их пересечение, объединение и разность.

какой метод лучше? Читала литературу по этой теме. Там написано, что лучше всего использовать триангуляцию. Так ли это? Или может быть лучше разбить невыпуклые многоугольники на выпуклые и применить к ним алгоритм пересечения(объединения, разности) для выпуклых?

Если есть какие-нибудь исходники по этой теме, - поделитесь пожалуйста.
  #2  
Старый 18.12.2007, 11:56
Mozilla

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

я бы использовал регионы(WinAPI), с помощью функций CreatePolygonRgn можно задать эти многоугольники, а с помощью функции CombineRgn и флагов(RGN_OR,RGN_XOR,RGN_AND) можно получить объединение, пересечение и т.д.
В общем глянь справку по Windows API, или MSDN.
Пример, если очень нужен могу написать.
Но! Этот метод можно использовать если результат нужно только отобразить!
В противном случае - используй библиотеку GPC, вот ссылка на тему:

Объединение областей
  #3  
Старый 18.12.2007, 13:54
MBo MBo вне форума
Местный

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

Погуглить GPC Alan Murta
  #4  
Старый 24.12.2007, 10:26
Новичок

Отправить личное сообщение для Nymph666 Посмотреть профиль Найти все сообщения от Nymph666
 
Регистрация: 28.11.2007
Сообщений: 5

Сообщение от Mozilla
я бы использовал регионы(WinAPI), с помощью функций CreatePolygonRgn можно задать эти многоугольники, а с помощью функции CombineRgn и флагов(RGN_OR,RGN_XOR,RGN_AND) можно получить объединение, пересечение и т.д.
В общем глянь справку по Windows API, или MSDN.
Спасиб, нужно не только отобразить, но и посчитать площадт...
А есть какие-нибудь хорошие сссылочки по WinAPI(так для себя хочу)?
  #5  
Старый 14.01.2008, 11:03
Новичок

Отправить личное сообщение для Nymph666 Посмотреть профиль Найти все сообщения от Nymph666
 
Регистрация: 28.11.2007
Сообщений: 5

появилась новая идея: все многоугольники ориентированы по часовой стрелке. Строя пересечение(объединение) мы двигаемся по точкам пересечения все время направо(налево при объединении). Правда там еще нужна навигационная информация расстояние до многоугольников, вектора. Плюс нужно знать как определять правый вектор...
Кто-нибудь сталкивался с таким алгоритмом?
 


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

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