Пересечение многоугольников
народ!!! есть проблема - нужно написать функцию пересецения многоугольников, в самом общем случае... нашел описание алгоритма Вейлера-Азертона, но в этом описании не был освещен самый основной момент - как определять граничные точки. :(
какие еще алгоритмы есть? или можнт быть этот, но с полным описанием?
какие еще алгоритмы есть? или можнт быть этот, но с полным описанием?
Цитата: Relax
народ!!! есть проблема - нужно написать функцию пересецения многоугольников, в самом общем случае... нашел описание алгоритма Вейлера-Азертона, но в этом описании не был освещен самый основной момент - как определять граничные точки. :(
какие еще алгоритмы есть? или можнт быть этот, но с полным описанием?
какие еще алгоритмы есть? или можнт быть этот, но с полным описанием?
Алгоритмов куча: 1. Уже упомянутый - Вейлера-Азертона
2. Леонова
3. Холверда
4. На основе триангуляции
5. Маргалита-Кнотта
6. Линейно - узловой
Вот те ссылка http://www.inf.tsu.ru/library/Publications/2004/46.pdf
Вообще почитай Скворцова - у него много статей на эту тему.
Есть интерсная статья General Polygon Clipper library с кодом C #, Delphi, Java, Perl, Python, Haskell, Lua, VB.Net
Разница, пересечение, исключающее ИЛИ и операции объединения полигонов многоугольников.
Полигоны могут состоять из нескольких контуров не пересекаются. Контуры могут быть вложенными (т.е. многоугольники могут иметь отверстия).
Разница, пересечение, исключающее ИЛИ и операции объединения полигонов многоугольников.
Полигоны могут состоять из нескольких контуров не пересекаются. Контуры могут быть вложенными (т.е. многоугольники могут иметь отверстия).