Russian Qt Forum
Ноябрь 23, 2024, 10:36 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Общий > Пересечение объектов (структуры данных)
Страниц: [1]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Пересечение объектов (структуры данных)  (Прочитано 3308 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Март 24, 2011, 14:04 »
Добрый день

Есть набор объектов в виде стандартной иерархии parent-child дерево. По умолчанию объекты не могут пересекаться друг с другом, но в UI пользователь может задать исключения (индивидуально для каждого объекта)

- объект может пересекаться со своим parent'ом
- объект может пересекаться с заданным множеством др. объектов

Кроме того, если объект имеет "жесткую связь" с parent'ом, то пересечение разрешено независимо от установок пользователя

Пересечение "взаимно", т.е. если A может пересекаться с B, то и B c A. Однако если напр. A и B могут пересекаться оба с одним и тем же множеством (напр. C. D, E), то это не значит что A и B могут пересекаться между собой.

Задача построить такую структуру(ы) данных которая бы обеспечивала быстрый ответ на запрос о пересечении любых 2 объектов. Ваши предложения?

Спасибо
« Последнее редактирование: Март 24, 2011, 14:09 от Igors » Записан
SimpleSunny
Гость
« Ответ #1 : Март 24, 2011, 14:53 »
Если А пересекается со множеством (В, С).
Значит ли это что В или С пересекается с А?

Можно ли ввести отношения порядка для объектов?
« Последнее редактирование: Март 24, 2011, 14:59 от SimpleSunny » Записан
ufna
Гость
« Ответ #2 : Март 24, 2011, 15:13 »
Самое просто, имхо, квадродерево.

Более правильное - семейство R-деревьев.

Еще более правильно - специализировать R-дерево под свои нужды.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #3 : Март 24, 2011, 15:34 »
Цитата: SimpleSunny от Март 24, 2011,  14:53
Если А пересекается со множеством (В, С).
Значит ли это что В или С пересекается с А?
Да, но это не значит что B пересекается c С

Цитата: SimpleSunny от Март 24, 2011,  14:53
Можно ли ввести отношения порядка для объектов?
По-моему нет, не вижу как.

Цитата: ufna от Март 24, 2011,  15:13
Самое просто, имхо, квадродерево.

Более правильное - семейство R-деревьев.

Еще более правильно - специализировать R-дерево под свои нужды.
Здесь "пересечение" - это как бы свойство просто (пока) хранимое в структурах данных. Как там в пространстве 3-х мерные объекты пересекутся во время движения - то др. вопрос. может еще и никаких "реальных" пересечений нет. А вот когда они возникнут - тогда и нужно (основываясь на заранее созданных данных) ответить разрешаем ли пересечение или нет.
Записан
ufna
Гость
« Ответ #4 : Март 24, 2011, 16:13 »
Т.е. пока стоит задача только узнать о "перечесениях" на основе текущих данных и не более чем?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #5 : Март 24, 2011, 17:57 »
Цитата: ufna от Март 24, 2011,  16:13
Т.е. пока стоит задача только узнать о "перечесениях" на основе текущих данных и не более чем?
Да, вернее "задать" (с помощью пользователя)
Записан
Страниц: [1]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.054 секунд. Запросов: 22.