Пересечение объектов (структуры данных)

[Igors]

Добрый день

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

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

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

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

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

Спасибо

[SimpleSunny]

Если А пересекается со множеством (В, С).
Значит ли это что В или С пересекается с А?

Можно ли ввести отношения порядка для объектов?

[ufna]

Самое просто, имхо, квадродерево.

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

Еще более правильно - специализировать R-дерево под свои нужды.

[Igors]

Если А пересекается со множеством (В, С).
Значит ли это что В или С пересекается с А?

Да, но это не значит что B пересекается c С

Можно ли ввести отношения порядка для объектов?

По-моему нет, не вижу как.

Самое просто, имхо, квадродерево.

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

Еще более правильно - специализировать R-дерево под свои нужды.

Здесь "пересечение" - это как бы свойство просто (пока) хранимое в структурах данных. Как там в пространстве 3-х мерные объекты пересекутся во время движения - то др. вопрос. может еще и никаких "реальных" пересечений нет. А вот когда они возникнут - тогда и нужно (основываясь на заранее созданных данных) ответить разрешаем ли пересечение или нет.

[ufna]

Т.е. пока стоит задача только узнать о "перечесениях" на основе текущих данных и не более чем?

[Igors]

Т.е. пока стоит задача только узнать о "перечесениях" на основе текущих данных и не более чем?

Да, вернее "задать" (с помощью пользователя)