ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Georgy Udov                          2:5030/49.1    10 Apr 2003  13:30:53
 To : All
 Subject : Задачка про прямоугольники, всплывающая при написании САПР
 -------------------------------------------------------------------------------- 
 

 Здравствуй, All!
 
 Всплыла любопытная задачка, на абстрактном языке формулируется вот как:
 
 Hа двумерной координатной плоскости задано большое количество
 прямоугольников со сторонами, параллельными координатным осям.
 Прямоугольники задаются координатами левой верхней и правой нижней вершин.
 Hу пусть для определённости они имеют какие-нибудь там номера.
 
 Задан ещё один прямоугольник на этой же плоскости. Требуется определить, с
 какими из прямоугольников данный пересекается. Естественно, хочется понять,
 как реализовать это оптимально.
 
 Из определённых источников известно, что AutoCAD для решения данной задачи
 использует дерево, у которого каждая вершина имеет максимум 4 потомка.
 Вероятно, потомки по принципу ниже-левее, ниже-правее, выше-левее, и т. д.
 
 Мне приходит в голову мысль только с двумя деревьями, хранящими левые
 верхние и правые нижние вершины исходных прямоугольников соответственно.
 Таким образом, при решении задачи находим множества
 
 1) Прямоугольников, чей левый-верхний угол лежит выше-левее правого нижнего
 угла "ещё одного прямоугольника"
 2) Прямоугольников, чей правый-нижний угол лежит ниже-правее левого верхнего
 угла "ещё одного прямоугольника"
 
 Далее множества (1) и (2) пересекаем, и вот он результат.
 
 Hепонятным остаётся:
 
 1) Можно ли придумать что-нибудь более оптимальное?
 2) Как балансировать такое дерево?
 3) Исходная куча прямоугольников может меняться. То есть, надо бы уметь
 эффективно удалять/вставлять вершины в дерево...
 
 Спасибо за внимание. Может, кто-нибудь скажет что-нибудь?..
 
 Vale, Georgy Udov.  E-mail: udovgeorgy#SPAMOFFchat.ru
 --- ifmail v.2.15
  * Origin: http://news.kaa.ru (2:5030/49.1)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор