Алгоритм для ZOrder? - Алгоритмы

Привет!

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

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

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

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

P.S. Может кто знает как в windows решили такую проблему?

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

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

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

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

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

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

А>>Делаю контрол который отображает множество прямоугольников на плоскости, при этом один прямоугольник может иметь родителем другой прямоугольник. Каждому прямоугольнику присваивается 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 для чилдовых прямоугольников уже перейдет через границу

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

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

<>

А>Такое бы прокатило если бы не одно но:
А>Например указываем что толщина равна = 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'ом.

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

К>

К>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) если прямоугольник перетаскивается в другой прямоугольник это также касается и дочерних прямоугольников;

Спасибо!

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

К>>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) не меняется, когда их родитель переезжает с места на место.

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

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

К>>>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, так?

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

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

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

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

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

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

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

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

Аналогия супер!

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

Спасибо!

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