LINUX.ORG.RU
Форум — Development  

[wanted advice] размещение 2д-объектов


0

2

стоит задача: на плоскости следует разместить произвольное количество любых прямоугольников. в дальнейшем их надо будет отображать, поэтому желательно иметь возможность найти все прямоугольники, попадающие «в кадр», т.е. пересекающиеся с заданным прямоугольником.

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

если у кого-нибудь на примете есть работающий код, способный со сложностью порядка log(n) выбирать какие прямоугольники отображать можно, а какие нельзя- буду рад за ссылки.

☆☆☆

Не париться и использовать select buffer openGL'я?

Eddy_Em ☆☆☆☆☆
()

у меня была немного другая задача но возможно тебе стоит рассмотреть вариант,
разбить плоскость (в моем случае это был экран) на мелкие квадраты (прямоугольники), на сколько мелкие зависит от погрешности.
при добавлении объекта вычислить прямоугольники плоскости, запомнить инфу (у меня был большой bitset)
результат получаешь аналогично

anonymous2 ★★★★★
()

R-trees как посоветовали, но я использовал свою вариацию k-d деревьев в четырехмерном пространстве. Все хорошо, но балансировки не было у меня. Честно говоря, не знаю, можно ли балансировать R-trees.

dave ★★★★★
()

Код можно посмотреть в Qt, там эта задача решена для QGraphicsScene. Насколько помню, R-trees используются.

unC0Rr ★★★★★
()
Ответ на: комментарий от unC0Rr

> Код можно посмотреть в Qt, там эта задача решена для QGraphicsScene. Насколько помню, R-trees используются.

Там bsp (QGraphicsScene::BspTreeIndex).

Amp ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development