![]() |
Модераторы: Poseidon |
![]() ![]() ![]() |
|
Nymph666 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 25 Регистрация: 28.11.2007 Репутация: нет Всего: нет |
Всем доброго времени суток!
Задачка такая: Даны n простых многоугольников, заданные массивами точек. Найти их пересечение, объединение и разность. Кто сталкивался поделитесь опытом ![]() Сдача через 3 дня. Спасайте! ![]() |
|||
|
||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
это что за зверь? 1 и 2... результат - с 3... и так далее тоже непонятно кто... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Nymph666 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 25 Регистрация: 28.11.2007 Репутация: нет Всего: нет |
простые многоугольники- это можно сказать обыкновенные вогнутые многоугольники. Это Логические операции над многоугольниками. Пересечение -точки, которые принадлежат всем многоугольникам.(логич.И and) Объединение - точки, которые принадлежат любому из многоугольников. (логич. ИЛИ or) Разность - Точки одного многоугольника без точек, которые совпадают с точками второго.(xor) |
|||
|
||||
Nymph666 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 25 Регистрация: 28.11.2007 Репутация: нет Всего: нет |
появилась новая идея: все многоугольники ориентированы по часовой стрелке. Строя пересечение(объединение) мы двигаемся по точкам пересечения все время направо(налево при объединении). Правда там еще нужна навигационная информация расстояние до многоугольников, вектора. Плюс нужно знать как определять правый вектор...
Кто-нибудь сталкивался с таким алгоритмом? |
|||
|
||||
maxdiver |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: нет Всего: 18 |
Мне тоже хотелось бы почитать что-нибудь про объединение многоугольников. Это на самом деле далеко не тривиальная задача, если учесть например, что несколько многоугольников при объединении дадут что-нибудь вроде кольца - т.е. в центре будет дырка; как обрабатывать и хранить такие вещи непонятно совершенно.
|
|||
|
||||
Nymph666 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 25 Регистрация: 28.11.2007 Репутация: нет Всего: нет |
Довольно не сложно это решается с помощью BSP-деревьев. Этот метод мне подсказал один хороший человек, который помог этим мне написать курсовую работу. Причем там легко обрабатываются и полигоны с дырами.
Это сообщение отредактировал(а) Nymph666 - 30.1.2008, 12:27 |
|||
|
||||
kilonet |
|
|||
Новичок Профиль Группа: Участник Сообщений: 24 Регистрация: 13.3.2006 Репутация: нет Всего: нет |
ну а всё-таки...
можно хотя бы в общих чертах услышать подход к решению этой проблемы? |
|||
|
||||
kilonet |
|
|||
Новичок Профиль Группа: Участник Сообщений: 24 Регистрация: 13.3.2006 Репутация: нет Всего: нет |
Обрисую свою проблему (использую NET Framework): есть многоугольники заданные координатами вершин. Над этими многоугольниками надо выполнять операции объединение или вычитание.
Знаю что есть специальные алгоритмы для этого. Чтобы упростить задачу пытаюсь пока обойтись без них. Делаю так: многоугольники преобразую в регион (Region) для которых операции Union и Exclude уже реализованы в самом Framework-е. Единственное что потом можно с этим регионом сделать - аппроксимировать его массивом прямоугольников толщиной 1 пиксель (метод GetRegionScans) - т. е. у меня есть координаты вершин многоугольника, надо лишь отсортировать их в правильном порядке и если есть "дырки" внутри многоугольника как-то обнаружить их и найти их координаты в правильном порядке. У кого-нибудь есть идеи, как это можно сделать? |
|||
|
||||
Nymph666 |
|
||||||
Новичок Профиль Группа: Участник Сообщений: 25 Регистрация: 28.11.2007 Репутация: нет Всего: нет |
Binary_space_partitioning Вот посмотри здесь.
Я использовала ребра а потом рисую
Поэтому не нужно знать правильной последовательности ребер, просто рисуешь их подряд и все. В общем посмотри здесьМногоугольники. Это сообщение отредактировал(а) Nymph666 - 13.2.2008, 13:22 |
||||||
|
|||||||
![]() ![]() ![]() |
Правила форума "Центр помощи" | |
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Центр помощи | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |