Задачка такая: Даны n простых многоугольников, заданные массивами точек. Найти их пересечение, объединение и разность.
Кто сталкивался поделитесь опытом
Сдача через 3 дня. Спасайте!
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Алгоритм] Многоугольники |
| Автор: Nymph666 24.12.2007, 09:58 |
| Всем доброго времени суток! Задачка такая: Даны n простых многоугольников, заданные массивами точек. Найти их пересечение, объединение и разность. Кто сталкивался поделитесь опытом Сдача через 3 дня. Спасайте! |
| Автор: Akina 24.12.2007, 10:10 | ||||||
это что за зверь?
1 и 2... результат - с 3... и так далее
тоже непонятно кто... |
| Автор: Nymph666 24.12.2007, 10:17 | ||
простые многоугольники- это можно сказать обыкновенные вогнутые многоугольники. Это Логические операции над многоугольниками. Пересечение -точки, которые принадлежат всем многоугольникам.(логич.И and) Объединение - точки, которые принадлежат любому из многоугольников. (логич. ИЛИ or) Разность - Точки одного многоугольника без точек, которые совпадают с точками второго.(xor) |
| Автор: Nymph666 14.1.2008, 09:59 |
| появилась новая идея: все многоугольники ориентированы по часовой стрелке. Строя пересечение(объединение) мы двигаемся по точкам пересечения все время направо(налево при объединении). Правда там еще нужна навигационная информация расстояние до многоугольников, вектора. Плюс нужно знать как определять правый вектор... Кто-нибудь сталкивался с таким алгоритмом? |
| Автор: maxdiver 29.1.2008, 23:16 |
| Мне тоже хотелось бы почитать что-нибудь про объединение многоугольников. Это на самом деле далеко не тривиальная задача, если учесть например, что несколько многоугольников при объединении дадут что-нибудь вроде кольца - т.е. в центре будет дырка; как обрабатывать и хранить такие вещи непонятно совершенно. |
| Автор: Nymph666 30.1.2008, 12:27 |
| Довольно не сложно это решается с помощью BSP-деревьев. Этот метод мне подсказал один хороший человек, который помог этим мне написать курсовую работу. Причем там легко обрабатываются и полигоны с дырами. |
| Автор: kilonet 4.2.2008, 10:41 |
| ну а всё-таки... можно хотя бы в общих чертах услышать подход к решению этой проблемы? |
| Автор: kilonet 6.2.2008, 10:30 |
| Обрисую свою проблему (использую NET Framework): есть многоугольники заданные координатами вершин. Над этими многоугольниками надо выполнять операции объединение или вычитание. Знаю что есть специальные алгоритмы для этого. Чтобы упростить задачу пытаюсь пока обойтись без них. Делаю так: многоугольники преобразую в регион (Region) для которых операции Union и Exclude уже реализованы в самом Framework-е. Единственное что потом можно с этим регионом сделать - аппроксимировать его массивом прямоугольников толщиной 1 пиксель (метод GetRegionScans) - т. е. у меня есть координаты вершин многоугольника, надо лишь отсортировать их в правильном порядке и если есть "дырки" внутри многоугольника как-то обнаружить их и найти их координаты в правильном порядке. У кого-нибудь есть идеи, как это можно сделать? |
| Автор: Nymph666 13.2.2008, 13:21 | ||||||
http://en.wikipedia.org/wiki/Binary_space_partitioning Вот посмотри здесь.
Я использовала ребра а потом рисую
Поэтому не нужно знать правильной последовательности ребер, просто рисуешь их подряд и все. В общем посмотри здесьhttp://forum.sources.ru/index.php?showtopic=216741&st=0. |
