Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Алгоритм] Многоугольники 
:(
    Опции темы
Nymph666
  Дата 24.12.2007, 09:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 25
Регистрация: 28.11.2007

Репутация: нет
Всего: нет



Всем доброго времени суток!
Задачка такая: Даны n простых многоугольников, заданные массивами точек. Найти их пересечение, объединение и разность. 
Кто сталкивался поделитесь опытом smile 
Сдача через 3 дня. Спасайте! smile 
PM MAIL   Вверх
Akina
Дата 24.12.2007, 10:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454



Цитата(Nymph666 @  24.12.2007,  10:58 Найти цитируемый пост)
простых многоугольников

это что за зверь?

Цитата(Nymph666 @  24.12.2007,  10:58 Найти цитируемый пост)
Найти их пересечение, объединение 

1 и 2... результат - с 3... и так далее

Цитата(Nymph666 @  24.12.2007,  10:58 Найти цитируемый пост)
и разность

тоже непонятно кто...


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
Nymph666
Дата 24.12.2007, 10:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 25
Регистрация: 28.11.2007

Репутация: нет
Всего: нет



Цитата(Akina @ 24.12.2007,  10:10)
это что за зверь?

простые многоугольники- это можно сказать обыкновенные вогнутые многоугольники.

 Это Логические операции над многоугольниками.
Пересечение -точки, которые принадлежат всем многоугольникам.(логич.И and)
Объединение - точки, которые принадлежат любому из многоугольников. (логич. ИЛИ or)
Разность - Точки одного многоугольника без точек, которые совпадают с точками второго.(xor) 
PM MAIL   Вверх
Nymph666
Дата 14.1.2008, 09:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 25
Регистрация: 28.11.2007

Репутация: нет
Всего: нет



появилась новая идея: все многоугольники ориентированы по часовой стрелке. Строя пересечение(объединение) мы двигаемся по точкам пересечения все время направо(налево при объединении). Правда там еще нужна навигационная информация расстояние до многоугольников, вектора. Плюс нужно знать как определять правый вектор...
Кто-нибудь сталкивался с таким алгоритмом?
PM MAIL   Вверх
maxdiver
Дата 29.1.2008, 23:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: нет
Всего: 18



Мне тоже хотелось бы почитать что-нибудь про объединение многоугольников. Это на самом деле далеко не тривиальная задача, если учесть например, что несколько многоугольников при объединении дадут что-нибудь вроде кольца - т.е. в центре будет дырка; как обрабатывать и хранить такие вещи непонятно совершенно.
PM MAIL WWW ICQ   Вверх
Nymph666
Дата 30.1.2008, 12:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 25
Регистрация: 28.11.2007

Репутация: нет
Всего: нет



Довольно не сложно это решается с помощью BSP-деревьев. Этот метод мне подсказал один хороший человек, который помог этим мне написать курсовую работу. Причем там легко обрабатываются и полигоны с дырами. 

Это сообщение отредактировал(а) Nymph666 - 30.1.2008, 12:27
PM MAIL   Вверх
kilonet
Дата 4.2.2008, 10:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 24
Регистрация: 13.3.2006

Репутация: нет
Всего: нет



ну а всё-таки...
можно хотя бы в общих чертах услышать подход к решению этой проблемы?

PM MAIL ICQ   Вверх
kilonet
Дата 6.2.2008, 10:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 24
Регистрация: 13.3.2006

Репутация: нет
Всего: нет



Обрисую свою проблему (использую NET Framework): есть многоугольники заданные координатами вершин. Над этими многоугольниками надо выполнять операции объединение или вычитание.
Знаю что есть специальные алгоритмы для этого. Чтобы упростить задачу пытаюсь пока обойтись без них. Делаю так: многоугольники преобразую в регион (Region) для которых операции Union и Exclude уже реализованы в самом Framework-е.  Единственное что потом можно с этим регионом сделать - аппроксимировать его массивом прямоугольников толщиной 1 пиксель (метод GetRegionScans) - т. е. у меня есть координаты вершин многоугольника, надо лишь отсортировать их в правильном порядке и если есть "дырки" внутри многоугольника как-то обнаружить их и найти их координаты в правильном порядке.
У кого-нибудь есть идеи, как это можно сделать?
PM MAIL ICQ   Вверх
Nymph666
Дата 13.2.2008, 13:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 25
Регистрация: 28.11.2007

Репутация: нет
Всего: нет



Цитата(kilonet @ 6.2.2008,  10:30)


Binary_space_partitioning
Вот посмотри здесь. 
Цитата
 у меня есть координаты вершин многоугольника, надо лишь отсортировать их в правильном порядке и если есть "дырки" внутри многоугольника как-то обнаружить их и найти их координаты в правильном порядке.

Я использовала ребра а потом рисую 
Код

line(ребро.нач_точка, ребро.конеч_точка);

Поэтому не нужно знать правильной последовательности ребер, просто рисуешь их подряд и все. 
В общем посмотри здесьМногоугольники.


Это сообщение отредактировал(а) Nymph666 - 13.2.2008, 13:22
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »


 




[ Время генерации скрипта: 0.0731 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.