Многоугольники
Задачка такая: даны простые(т.е.могут быть вогнутыми, но без самопересечений) многоугольники(их может быть хоть сколько). Каждый из них задается списком точек. Нужно найти их пересечение, объединение и разность.
какой метод лучше? Читала литературу по этой теме. Там написано, что лучше всего использовать триангуляцию. Так ли это? Или может быть лучше разбить невыпуклые многоугольники на выпуклые и применить к ним алгоритм пересечения(объединения, разности) для выпуклых?
Если есть какие-нибудь исходники по этой теме, - поделитесь пожалуйста.
Первая же ссылка дала подсказку:
"Вначале ищутся вершины первого многоугольника лежащие внутри второго многоугольника и наоборот вершины второго многоугольника лежащие внутри первого многоугольника".
Что такое многоугольник? "Геометрическое место точек...", как сказали бы в школе. То бишь, множество точек.
Что-нибудь слышал про пересечение множеств?
---
Дальше объяснять?
Найти пересечение - найти многоугольник, не важно как заданный- главное его изобразить на Image и т.п.
Площадь тоже нужна, но если знаешь координаты вершин, это не трудно.
Первая же ссылка дала подсказку:
"Вначале ищутся вершины первого многоугольника лежащие внутри второго многоугольника и наоборот вершины второго многоугольника лежащие внутри первого многоугольника".
А ты сам не пробовал реализовывать?
Сама не пробовала, но говорят, что он не устойчив и косячит...
Еще там куча исключительных случаев, которые не описываются в самом алгоритме.
Ну решаются они вроде как по разному...
Хотела узнать что лучше в смысле простоты программной реализации?
Читала книжку, - там пишется, что нужно сначала триангулировать сразу все многоугольники(триангуляция с ограничениями), а потом сортировать треугольники по признаку вхождения в многоугольники. Если входит в оба многоугольника - пересечение, в один из них -объединение, в один входит, в другой нет - разность.
Вот тока какую триангуляцию использовать и как потом объединять эти треугольники????
Nymph666, нет, сам я никогда этим не занимался :)
Именно, так. Мало того, их может быть несколько..:)
Кто-нибудь сталкивался с таким алгоритмом?
В такой системе данных строить алгоритм объединения уже не так сложно. Другие тоже.