Алгоритм для ZOrder?
От: Аноним  
Дата: 14.12.05 08:35
Оценка:
Привет!

Делаю контрол который отображает множество прямоугольников на плоскости, при этом один прямоугольник может иметь родителем другой прямоугольник. Каждому прямоугольнику присваивается ZOrder относительно родительского прямоугольника. Так как графический уровень не имеет доступа к логике, то ему нужно отдать список прямоугольников с реальными ZOrder, этот RealZOrder расчитывается как сумма ZOrder-ov от листка дерева до корня дерева.

Проблема: Пересекаются ZOrder-a дочерних прямоугольников и поэтому не правильно рисуется. Аналогия проблемы — это как бы некоторые контролы виндовз формы (ZOrder=1) вылазили поверх формы (ZOrder=2) при том что формы находятся на одном уровне от корня дерева.

P.S. Надеюсь доступно обьяснил

Необходим алгоритм правильной генерации ZOrder. Спасибо.

P.S. Может кто знает как в windows решили такую проблему?
Re: Алгоритм для ZOrder?
От: Кодт Россия  
Дата: 14.12.05 09:55
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Делаю контрол который отображает множество прямоугольников на плоскости, при этом один прямоугольник может иметь родителем другой прямоугольник. Каждому прямоугольнику присваивается ZOrder относительно родительского прямоугольника. Так как графический уровень не имеет доступа к логике, то ему нужно отдать список прямоугольников с реальными ZOrder, этот RealZOrder расчитывается как сумма ZOrder-ov от листка дерева до корня дерева.


Введём и различим понятия "порядок" (n), "толщина" (t) и "высота" (h)
На каждом уровне высоты может находиться только один узел иерархии (прямоугольник).
Диапазон высот (hmax-hmin+1) узла с подузлами (стопки прямоугольников) — это толщина. Фактически, толщина — это количество узлов в поддереве.

Твоему ZOrder соответствует n, RealZOrder — h.
Очевидно, что h узла относительно родителя равна 1 + сумме всех h предшествующих братьев (что, разумеется, >n)
А абсолютная h = относительная h + абсолютная h родителя
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[2]: Алгоритм для ZOrder?
От: Аноним  
Дата: 14.12.05 10:22
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Аноним, Вы писали:


А>>Делаю контрол который отображает множество прямоугольников на плоскости, при этом один прямоугольник может иметь родителем другой прямоугольник. Каждому прямоугольнику присваивается ZOrder относительно родительского прямоугольника. Так как графический уровень не имеет доступа к логике, то ему нужно отдать список прямоугольников с реальными ZOrder, этот RealZOrder расчитывается как сумма ZOrder-ov от листка дерева до корня дерева.


К>Введём и различим понятия "порядок" (n), "толщина" (t) и "высота" (h)

К>На каждом уровне высоты может находиться только один узел иерархии (прямоугольник).
К>Диапазон высот (hmax-hmin+1) узла с подузлами (стопки прямоугольников) — это толщина. Фактически, толщина — это количество узлов в поддереве.

К>Твоему ZOrder соответствует n, RealZOrder — h.

К>Очевидно, что h узла относительно родителя равна 1 + сумме всех h предшествующих братьев (что, разумеется, >n)
К>А абсолютная h = относительная h + абсолютная h родителя

Такое бы прокатило если бы не одно но:
Например указываем что толщина равна = 65535, то есть максмимольный локальный ZOrder для прямоугольника будет 65535. Но если заинсертить прямоугольник который имеет в себе чилдовые прямоугольники и поставить ему максимальный ZOrder, то RealZOrder для чилдовых прямоугольников уже перейдет через границу А это должна быть штатная фича перетягивать одни прямоугольники вместе с дочерними в другой прямоугольник.+ при этом юзер может менять ему локальный ZOrder. Вот поэтому с идеей толщины я отказался.
Re[3]: Алгоритм для ZOrder?
От: Кодт Россия  
Дата: 14.12.05 16:33
Оценка:
Здравствуйте, Аноним, Вы писали:

К>>На каждом уровне высоты может находиться только один узел иерархии (прямоугольник).


<>

А>Такое бы прокатило если бы не одно но:

А>Например указываем что толщина равна = 65535, то есть максмимольный локальный ZOrder для прямоугольника будет 65535. Но если заинсертить прямоугольник который имеет в себе чилдовые прямоугольники и поставить ему максимальный ZOrder, то RealZOrder для чилдовых прямоугольников уже перейдет через границу А это должна быть штатная фича перетягивать одни прямоугольники вместе с дочерними в другой прямоугольник.+ при этом юзер может менять ему локальный ZOrder. Вот поэтому с идеей толщины я отказался.

Толщина — это не прибитое гвоздями свойство узла, а функция: количество узлов в поддереве (включая себя, дочерних и т.д.)

Причём функция, которую можно один раз посчитать и затем только корректировать.

Переставляя дочерние узлы местами (меняя их z-order), ты не меняешь толщину ни каждого из них, ни родительского узла.
Перетаскивая узел (со всеми подузлами) из одного поддерева в другое — толщина всех предков (родителя, прародителя и т.д.) в первом поддереве уменьшается на толщину данного узла, а во втором, соответственно, — увеличивается.



z-order дочерних узлов принимает значения 1..+N (где N — количество непосредственных дочерних узлов данного узла).
Хотя, в принципе, никто не мешает раздавать любые числа — лишь бы они были уникальными.

Пусть толщина каждого узла — t(1)..t(N); толщина самого родителя без дочерних узлов to = 1.
Высота каждого узла относительно родителя — h(0)=0, h(1)=to+h(0), h(2)=h(1)+t(1) ... h(k)=h(k-1)+t(k-1), и наконец, высота верхнего края всей стопки H=t(N)+h(N), то есть, to+t(1)+...+t(N) = t(родительского узла)

Понятна разница между локальным z-order'ом и толщиной?



Абсолютная высота узла = абсолютная высота родителя + высота узла относительно родителя.
Если принять абсолютную высоту корня = 0, то абсолютная высота узла = сумма толщин его прародителей.

Нужно ли кешировать эти значения? В принципе, можно.

При изменении z-order'а узла — меняются высоты узлов в поддереве его родителя (можно ещё более сузить границы пересчёта, не трогая узлы ниже и выше позиций "откуда" и "куда").
При перетаскивании — меняются высоты в дереве, включающем оба поддерева (откуда, куда).



Мы так построили функцию абсолютной высоты, что для каждого узла она принимает уникальное значение (и, кстати говоря, диапазон значений сплошной).
И к тому же, zorder(i) < zorder(j) <=> h(i) < h(j) (где i,j — дочерние узлы одного родителя).

Поэтому абсолютная высота является глобальным z-order'ом.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[4]: Алгоритм для ZOrder?
От: Аноним  
Дата: 15.12.05 08:11
Оценка:
Здравствуйте, Кодт, Вы писали:

К>

К>z-order дочерних узлов принимает значения 1..+N (где N — количество непосредственных дочерних узлов данного узла).
К>Хотя, в принципе, никто не мешает раздавать любые числа — лишь бы они были уникальными.

Не нравится мне требование о том что бы они были уникальными, потому что если есть N подряд прямоугольников, которые имеют локальный ZOrder: 0,1,2,...,n; 0<=n<=N-1 то тогда нельзя будет понизить(уменьшить локальный ZOrder) прямоугольника N[j]; 0<j<=N-1; В принципе если у прямоугольников одинаковые ZOrder то какой из них нарисуется первым не является ошибкой (они будут иметь отметку об этом);

Главное что бы юзер не парился, то есть ему нужен свободный доступ к редактированию локального ZOrder и еще было бы не плохо что бы он не менялся (локальный ZOrder) если прямоугольник перетаскивается в другой прямоугольник это также касается и дочерних прямоугольников;

Спасибо!
Re[5]: Алгоритм для ZOrder?
От: Кодт Россия  
Дата: 15.12.05 08:29
Оценка:
Здравствуйте, Аноним, Вы писали:

К>>z-order дочерних узлов принимает значения 1..+N (где N — количество непосредственных дочерних узлов данного узла).

К>>Хотя, в принципе, никто не мешает раздавать любые числа — лишь бы они были уникальными.

А>Не нравится мне требование о том что бы они были уникальными, потому что если есть N подряд прямоугольников, которые имеют локальный ZOrder: 0,1,2,...,n; 0<=n<=N-1 то тогда нельзя будет понизить(уменьшить локальный ZOrder) прямоугольника N[j]; 0<j<=N-1; В принципе если у прямоугольников одинаковые ZOrder то какой из них нарисуется первым не является ошибкой (они будут иметь отметку об этом);


У одного понизил, у другого автоматически повысился. Z-order это всего лишь позиция в списке. Как ты этим списком управляешь — дело хозяйское.
Есть два способа:
— последовательный (4 команды: |<<, <-, ->, >>| ) — так сделано в подавляющем большинстве пользовательских интерфейсов (включая WinAPI )
— произвольный (указываешь номер, и объект выдёргивается из текущего места и вставляется в место по номеру) — так сделано в редакторе форм VB

А>Главное что бы юзер не парился, то есть ему нужен свободный доступ к редактированию локального ZOrder и еще было бы не плохо что бы он не менялся (локальный ZOrder) если прямоугольник перетаскивается в другой прямоугольник это также касается и дочерних прямоугольников;


Так оно и происходит. Список дочерних (а значит, и порядок их следования, т.е. z-order) не меняется, когда их родитель переезжает с места на место.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[6]: Алгоритм для ZOrder?
От: Аноним  
Дата: 15.12.05 09:10
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Аноним, Вы писали:


К>>>z-order дочерних узлов принимает значения 1..+N (где N — количество непосредственных дочерних узлов данного узла).

К>>>Хотя, в принципе, никто не мешает раздавать любые числа — лишь бы они были уникальными.

А>>Не нравится мне требование о том что бы они были уникальными, потому что если есть N подряд прямоугольников, которые имеют локальный ZOrder: 0,1,2,...,n; 0<=n<=N-1 то тогда нельзя будет понизить(уменьшить локальный ZOrder) прямоугольника N[j]; 0<j<=N-1; В принципе если у прямоугольников одинаковые ZOrder то какой из них нарисуется первым не является ошибкой (они будут иметь отметку об этом);


К>У одного понизил, у другого автоматически повысился. Z-order это всего лишь позиция в списке. Как ты этим списком управляешь — дело хозяйское.

К>Есть два способа:
К>- последовательный (4 команды: |<<, <-, ->, >>| ) — так сделано в подавляющем большинстве пользовательских интерфейсов (включая WinAPI )
К>- произвольный (указываешь номер, и объект выдёргивается из текущего места и вставляется в место по номеру) — так сделано в редакторе форм VB

Что то я не понял Получается что при изменении локального ZOrder-а нужно перестраивать все дерево начиная с того уровня дерева где локальный ZOrder менялся? Что бы не дай бог не было пересечений по абсолютному ZOrder, так?
Re[7]: Алгоритм для ZOrder?
От: Кодт Россия  
Дата: 15.12.05 10:49
Оценка: +1
Здравствуйте, Аноним, Вы писали:

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


Прекрати мыслить в терминах "нумерация". Нет нумерации. Есть упорядоченность.

Представь себе, скажем, дерево папок в эксплорере.
Если ты их всех развернёшь, то окажется, что папки и подпапки упорядочены по высоте: корень в самом верху окна, ниже идёт первая подпапка, затем её подпапки, ну и т.д. То есть, модель эквивалентная.

1) Переименовываешь подпапку — она перемещается в пределах папки (поскольку они отсортированы по имени). Внутренние папки поменялись или подвинулись относительно друг друга? Нет. Внешние? Тоже нет. Только соседние папки передвинулись.

2) Перетаскиваешь подпапку в другую папку. В первой папке содержимое ужалось, во второй раздвинулось. Опять же, больше нигде ничего не поменялось.

3) Добавил или удалил подпапку. Содержимое папки раздвинулось или ужалось, соответственно.

А вот теперь — глобально пронумеруем папки сверху вниз.
Каждый раз, изменяя структуру дерева, придётся пересчитать эту глобальную нумерацию. Причём диапазон пересчёта легко сузить.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[8]: Алгоритм для ZOrder?
От: Аноним  
Дата: 15.12.05 11:07
Оценка: +1
Здравствуйте, Кодт, Вы писали:

К>А вот теперь — глобально пронумеруем папки сверху вниз.

К>Каждый раз, изменяя структуру дерева, придётся пересчитать эту глобальную нумерацию. Причём диапазон пересчёта легко сузить.

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

Спасибо!
Re: Алгоритм для ZOrder?
От: Stanky  
Дата: 18.12.05 20:59
Оценка: +1
> P.S. Может кто знает как в windows решили такую проблему?
>
Не буду утверждать, что знаю, но когда делал оконный интерфейс, то при создании окна создавалась некая структура, все эти структуры были связаны в список (двунаправленный). И никакого ZOrder'а там на самом деле нет и не надо, а есть лишь порядок в списке. Каждое родительское окно имело свой список детей в котором глубина определялась тем же способом: чем раньше в списке, тем выше остальных. Если кто-то становился выше, то это вырождалось в переорганизацию списка — изменение нескольких ссылок. Более чем уверен, что у мелкомягких организованно если не точно так же, то крайне похоже.
Posted via RSDN NNTP Server 2.0
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[2]: Алгоритм для ZOrder?
От: Кодт Россия  
Дата: 19.12.05 09:51
Оценка:
Здравствуйте, Stanky, Вы писали:

S>Не буду утверждать, что знаю, но когда делал оконный интерфейс, то при создании окна создавалась некая структура, все эти структуры были связаны в список (двунаправленный). И никакого ZOrder'а там на самом деле нет и не надо, а есть лишь порядок в списке. Каждое родительское окно имело свой список детей в котором глубина определялась тем же способом: чем раньше в списке, тем выше остальных. Если кто-то становился выше, то это вырождалось в переорганизацию списка — изменение нескольких ссылок. Более чем уверен, что у мелкомягких организованно если не точно так же, то крайне похоже.


Я про это же и говорю. Номера z-order'а — это номера позиций в списке siblings.
В некоторых редакторах ресурсов (VB, VC) этот список переупорядочивают, задавая новые номера. В других (Zinc) — работают именно со списком.
Но на уровне API это всё-таки список: посмотрите на функцию SetWindowPos, в которой z-order определяется как HWND предшествующего окна. Да и внутри виндоуза тоже, скорее всего, список.
Потому что самому виндоузу для решения задач поиска, обрезки окон и диспетчеризации событий значения высоты совершенно не нужны.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: Алгоритм для ZOrder?
От: Аноним  
Дата: 19.12.05 12:01
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Потому что самому виндоузу для решения задач поиска, обрезки окон и диспетчеризации событий значения высоты совершенно не нужны.


Но есть исключения: дропдаунлист комбобокса, хинты и всякие балуны. Надо ж как то знать что они выше всех?
Re[4]: Алгоритм для ZOrder?
От: Stanky  
Дата: 19.12.05 17:11
Оценка:
> Но есть исключения: дропдаунлист комбобокса, хинты и всякие балуны.
> Надо ж как то знать что они выше всех?
>
А в чём проблема-то? Они находятся вначале списка — на самом верху.
Posted via RSDN NNTP Server 2.0
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[3]: Алгоритм для ZOrder?
От: Stanky  
Дата: 19.12.05 17:11
Оценка:
> Я про это же и говорю.
>
Не спорю.

> Но на уровне API это всё-таки список: посмотрите на функцию

> SetWindowPos, в которой z-order определяется как HWND предшествующего
> окна. Да и внутри виндоуза тоже, скорее всего, список.
>
Я про это же и говорю.
Posted via RSDN NNTP Server 2.0
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[5]: Алгоритм для ZOrder?
От: Кодт Россия  
Дата: 19.12.05 17:27
Оценка:
Здравствуйте, Stanky, Вы писали:

>> Но есть исключения: дропдаунлист комбобокса, хинты и всякие балуны.

>> Надо ж как то знать что они выше всех?
>>
S>А в чём проблема-то? Они находятся вначале списка — на самом верху.

Always-on-top-окна (челюсть комбобокса, хинты, меню, баллоны, а также обычные окна с выставленным флагом) — это popup-окна, т.е. их родитель — это desktop. (Почувствуйте разницу: в виндоузе есть иерархия владельцев и иерархия родителей; для client-окон родитель и владелец суть одно).
Список дочерних окон десктопа упорядочен таким образом, что окна с признаком always-on-top находятся в начале.

Ну а между собой иерархии клиентских окон этих always-on-top'ных окон не перемежаются. То есть — всё как обычно.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[6]: Алгоритм для ZOrder?
От: Stanky  
Дата: 19.12.05 18:29
Оценка:
> Список дочерних окон десктопа упорядочен таким образом, что окна с
> признаком always-on-top находятся в начале.
>
А я разве не это сказал?
Posted via RSDN NNTP Server 2.0
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[7]: Алгоритм для ZOrder?
От: Аноним  
Дата: 20.12.05 14:56
Оценка:
Здравствуйте, Stanky, Вы писали:

>> Список дочерних окон десктопа упорядочен таким образом, что окна с

>> признаком always-on-top находятся в начале.
>>
S>А я разве не это сказал?

А как же тогда нумеровать окна по ZOrder?
Re[8]: Алгоритм для ZOrder?
От: Stanky  
Дата: 20.12.05 18:54
Оценка:
> А как же тогда нумеровать окна по ZOrder?
>
Что именно это значит?
Posted via RSDN NNTP Server 2.0
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[9]: Алгоритм для ZOrder?
От: Аноним  
Дата: 21.12.05 09:11
Оценка:
Здравствуйте, Stanky, Вы писали:

>> А как же тогда нумеровать окна по ZOrder?

>>
S>Что именно это значит?

Уже разобрался, спасибо всем!!!
Re[9]: Алгоритм для ZOrder?
От: vdimas Россия  
Дата: 27.12.05 03:16
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Кодт, Вы писали:


К>>А вот теперь — глобально пронумеруем папки сверху вниз.

К>>Каждый раз, изменяя структуру дерева, придётся пересчитать эту глобальную нумерацию. Причём диапазон пересчёта легко сузить.

А>Аналогия супер! Теперь все ясно! То есть локальные ZOrder можно и не пересчитывать и не требовать их уникальность, только пересчитывать глобальную нумерацию при изменении дерева.


А>Спасибо!


Странно. Делаю аналогичную либу для себя — LiteControls. Никакого номера для Z-order не использую. Child-окошки — это просто двусвязанный список, даже не массив. Почему так? Потому что абсолютно все алгоритмы — последовательные, либо начиная с начала (вершины z-иерархии), либо начиная с конца (как раз перерисовка с конца идет)

Т.е. я вообще не вычисляю никакой Z-order и мне даже плохо понятно, на кой он мне во время перерисовки?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.