Здравствуйте, единственные и неповторимые винградовцы  !

Думаю, из названия темы суть вопроса ясна: есть графические фигуры, определенным образом расположенные на полотне, и, соответственно, определенным образом накладывающиеся друг на друга; какие способы хранения порядка наложения существуют? желательно, (очень) простые в реализации
Возможность быстро узнать, какая фигура самая верхняя и находится ли что-то еще под некоторой фигурой, очень критична.

Сначала я думала, что незачем раздувать из этого проблему, мудрить что-то с бинарными деревьями или еще с чем-то, что в действительности все намного проще... Создаем булевскую матрицу NxN (N - кол-во фигур) и заполняем ее по простому правилу: a[i][j] = {фигура с номером i лежит над фигурой с номером j}. Можно урезать матрицу до треугольного вида, исключив и главную диагональ.
Вобщем я была в восторге от своей идеи - все очень просто, доступно, информативно и экономично; изменение порядка фигур - вообще раз плюнуть. Эта простота стала настораживать меня, но я не нашла подвох... И вот только в самый последний момент меня осенило, что при таком хранении порядка наложения потребуется много вычислений для того, чтобы узнать, какая фигура лежит выше всех, какая - вторая и т.п..

Я поняла, для  чего нужно бинарное дерево! Вернее, поняла только отчасти... У него по крайней мере есть голова - понятно, откуда все начинается и что сверху...
Но как именно его строить, чтобы можно было отразить все тонкости и нюансы порядка наложения (как в моей матрице)? Изменение порядка, конечно, не потребует гигантских усилий, но все равно помудрить придется...

Какие еще есть способы?

P.S.. Вы просто не представляете, как благодарна я буду  ...

Я не очень внимательно прочитал твое сообщение, так что если что...  

Вообщем другой способ - это в структуре объекта предусмотреть две спец. точки - самая близкая и самая дальняя. И будет тебе быстрое определение самой верхней фигуры (просто перебрал все эти точки всех фигур)...

Достаточно обыкновенного списка. Номер по порядку соответсвует z позиции. Перемещать очень легко просто меняешь элементы списка местами. Элеметами списка являются описание фигуры и ссылки на предыдущий и следующий элемент списка.

Добавлено через 3 минуты и 27 секунд

Это уже другая задача.  Если объктов немного то можно перебором.  А для ускорения используй квадра деревья.

KasMP, насколько я помню твои предыдущие посты, у тебя фигур раз два и обчелся (несколько десятков). При таком количестве нужно использовать самые простые способы - линейный список Z-order, как уже сказано, и простой перебор для определения перекрытия фигур.

Самая близкая и дальняя по отношению к чему? от чего  ?

Благодарю .
А линейный список правда способен отразить все нюансы наложения? Фигуры могут накладываться самым причудливым образом, а в списке нет возможности сделать что-то типа ответвления.

Какая ты внимательная  . Да, их совсем-совсем мало.

Подумаю над тем, как список способен передать все-все тонкости порядка...

Пусть будет так. Думаю, это вполне приемлемо. Спасибо большое за советы  .

Добавлено через 2 минуты и 40 секунд
Хотя если вдуматься, то как бы причудливо не пересекались фигуры друг с другом, они все равно линейны по вертикали: если фигура1 лежит под фигурой2, то фигуры, которые под фигурой1, не могут оказаться над фигурой2, а фигуры, которые над фигурой2, не могут лежать над1.

Добавлено через 7 минут и 32 секунды
И все-таки меня смущает, например, такое наложение:


Как оно будет представлено в списке? Он будет кольцевым?
Вдруг создадутся дополнительные сложности?

Относительно нуля (центр системы координат).

Ой! Такое у тебя может быть? Список этого, действительно, не предусматривает... Что за задача, где такая конфигурация возникает? Обычно фигуры предполагаются плоскими, а плоскости так переплестись не могут...

Добавлено через 1 минуту и 23 секунды
Можно попробовать заменить список графом, где связь будет между соседними по Z-порядку объектами. Но сначала хорошенько подумай - так действительно может быть?

Здесь возникает 2 вопроса:
1) нужно уметь находить эти точки для фигур любой формы;
2) как это поможет узнать, какая фигура над какой лежит?
(скажем, есть точки b1 и d1, b2 и d2 (ближние и дальние точки двух фигур); какими бы не были эти числа, фигуры могут перекрываться в любом порядке - хоть 1 над 2, хоть 2 над 1)

Earnest, ты мне очень помогла  .
У меня были точно такие же мысли про плоскости и т.п., но я не была в них уверена и запостила такое "провокационное" наложение. Теперь я точно знаю, что все верно  .


Ты имеешь в виду что-то типа этого?

Вобщем список мне вполне подходит .

Только делать я буду не список, а массив:

• для сути задачи разницы нет: объекты упорядочены линейно, можем бегать в обе стороны, знаем начало и конец;
• памяти займет не больше (не нужно хранить указатели), работать будет не медленнее (в соседнюю ячейку бежать все-таки проще, чем по указателю бог знает куда);
• одна из немногих положительных черт списка не нужна даром:  фигур как было n штук в начале, так и будет до конца программы - изменять кол-во элементов хранилища z-order не потребуется;
• к моменту создания хранилища я уже знаю, сколько фигур будет;
• мне приятнее и комфортнее: не надо следить, кто куда смотрит; бегать проще; для изменения порядка нужно несколько элементарных строчек;
• ну не люблю я списки!!!!!!!!

От всей души благодарю любимых винградовцев, участвовавших в этой теме  .

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

Гм, все-таки делать я буду именно список по одной простой причине: очень часто надо будет элемент из середины хранилища перемещать в его начало, что потребует перемещения многих элементов в массиве (а это очень нерационально).

cardinal, спасибо за желание помочь  .

cardinal, пожалуйста, вспомни название этого метода  ! И тогда я смогу его изучить и буду очень тебе благодарна  .

Нет у него названия, это просто моя идея решения проблемы..

Понятно  .
Но вообще название у него есть  . Судя по всему, оно какое-то дурацкое, потому что никто не может его вспомнить   .