Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > z-order графических фигур, его хранение-изменение

Автор: KasMP 26.8.2009, 20:06

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

Автор: cardinal 26.8.2009, 20:18

Цитата(KasMP @  26.8.2009,  18:06 ) Какие еще есть способы? Я не очень внимательно прочитал твое сообщение, так что если что...   Вообщем другой способ - это в структуре объекта предусмотреть две спец. точки - самая близкая и самая дальняя. И будет тебе быстрое определение самой верхней фигуры (просто перебрал все эти точки всех фигур)...

Автор: Pavia 27.8.2009, 00:15

Достаточно обыкновенного списка. Номер по порядку соответсвует z позиции. Перемещать очень легко просто меняешь элементы списка местами. Элеметами списка являются описание фигуры и ссылки на предыдущий и следующий элемент списка. Добавлено через 3 минуты и 27 секунд Цитата(KasMP @  26.8.2009,  20:06 ) Возможность быстро узнать, какая фигура самая верхняя и находится ли что-то еще под некоторой фигурой, очень критична. Это уже другая задача.  Если объктов немного то можно перебором.  А для ускорения используй квадра деревья.

Автор: Earnest 27.8.2009, 07:23

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

Автор: KasMP 27.8.2009, 16:45

Цитата(cardinal @  26.8.2009,  20:18 ) в структуре объекта предусмотреть две спец. точки - самая близкая и самая дальняя Самая близкая и дальняя по отношению к чему? от чего  ? Цитата(Pavia @  27.8.2009,  00:15 ) Достаточно обыкновенного списка. Благодарю . А линейный список правда способен отразить все нюансы наложения? Фигуры могут накладываться самым причудливым образом, а в списке нет возможности сделать что-то типа ответвления. Цитата(Earnest @  27.8.2009,  07:23 ) KasMP, насколько я помню твои предыдущие посты, у тебя фигур раз два и обчелся (несколько десятков) Какая ты внимательная  . Да, их совсем-совсем мало. Цитата(Earnest @  27.8.2009,  07:23 ) При таком количестве нужно использовать самые простые способы - линейный список Z-order Подумаю над тем, как список способен передать все-все тонкости порядка... Цитата(Earnest @  27.8.2009,  07:23 ) и простой перебор для определения перекрытия фигур Пусть будет так. Думаю, это вполне приемлемо. Спасибо большое за советы  . Добавлено через 2 минуты и 40 секунд Хотя если вдуматься, то как бы причудливо не пересекались фигуры друг с другом, они все равно линейны по вертикали: если фигура1 лежит под фигурой2, то фигуры, которые под фигурой1, не могут оказаться над фигурой2, а фигуры, которые над фигурой2, не могут лежать над1. Добавлено через 7 минут и 32 секунды И все-таки меня смущает, например, такое наложение: http://radikal.ru/F/i036.radikal.ru/0908/3f/1d04b1fd01a5.jpg.html Как оно будет представлено в списке? Он будет кольцевым? Вдруг создадутся дополнительные сложности?

Автор: cardinal 27.8.2009, 18:04

Цитата(KasMP @  27.8.2009,  14:45 ) Самая близкая и дальняя по отношению к чему? от чего smile ? Относительно нуля (центр системы координат).

Автор: Earnest 28.8.2009, 07:45

Цитата(KasMP @  27.8.2009,  17:45 )  все-таки меня смущает, например, такое наложение: Ой! Такое у тебя может быть? Список этого, действительно, не предусматривает... Что за задача, где такая конфигурация возникает? Обычно фигуры предполагаются плоскими, а плоскости так переплестись не могут... Добавлено через 1 минуту и 23 секунды Можно попробовать заменить список графом, где связь будет между соседними по Z-порядку объектами. Но сначала хорошенько подумай - так действительно может быть?

Автор: KasMP 28.8.2009, 11:15

Цитата(cardinal @  27.8.2009,  18:04 ) Относительно нуля (центр системы координат).  Здесь возникает 2 вопроса: 1) нужно уметь находить эти точки для фигур любой формы; 2) как это поможет узнать, какая фигура над какой лежит? (скажем, есть точки b1 и d1, b2 и d2 (ближние и дальние точки двух фигур); какими бы не были эти числа, фигуры могут перекрываться в любом порядке - хоть 1 над 2, хоть 2 над 1) Earnest, ты мне очень помогла  . У меня были точно такие же мысли про плоскости и т.п., но я не была в них уверена и запостила такое "провокационное" наложение. Теперь я точно знаю, что все верно  . Цитата(Earnest @  28.8.2009,  07:45 ) Можно попробовать заменить список графом, где связь будет между соседними по Z-порядку объектами. Ты имеешь в виду что-то типа этого? http://radikal.ru/F/s42.radikal.ru/i098/0908/b5/1fd47505d7a4.jpg.html

Автор: KasMP 28.8.2009, 11:43

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

Автор: cardinal 28.8.2009, 16:05

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

Автор: KasMP 29.8.2009, 08:28

Цитата(KasMP @  28.8.2009,  11:43 ) Только делать я буду не список, а массив: Гм, все-таки делать я буду именно список по одной простой причине: очень часто надо будет элемент из середины хранилища перемещать в его начало, что потребует перемещения многих элементов в массиве (а это очень нерационально). cardinal, спасибо за желание помочь  .

Автор: KasMP 16.10.2009, 22:55

Цитата(cardinal @  26.8.2009,  20:18 ) Вообщем другой способ - это в структуре объекта предусмотреть две спец. точки - самая близкая и самая дальняя. И будет тебе быстрое определение самой верхней фигуры (просто перебрал все эти точки всех фигур)...  cardinal, пожалуйста, вспомни название этого метода  ! И тогда я смогу его изучить и буду очень тебе благодарна  .

Автор: cardinal 17.10.2009, 01:09

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

Автор: KasMP 18.10.2009, 11:54

Цитата(cardinal @  17.10.2009,  01:09 ) Нет у него названия, это просто моя идея решения проблемы..  Понятно  . Но вообще название у него есть  . Судя по всему, оно какое-то дурацкое, потому что никто не может его вспомнить   .

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)