САПР на Lazarus

[Mikhail]

У меня 3Д, 2д пока в разработке. но разница для дерева не принципиальная.
В 3Д - деление паралепипеда плоскостью, в 2Д - деление прямоугольника прямой.
Пытаюсь родить генерик для пространственного дерева. для 2д-3д случаев. Получается некрасиво, но вроде работает

Т.е просто делишь по полам вдоль одной из осей? Вдоль какой или по очереди?

[zub]

Пробовал несколько сценариев:
1)Тупо делить попалам по самому длинному габариту
2)Искать центр всех примитивов, делать 3 разбиения по всем осям и выбирать из них лучшее.
3)Искать центр всех примитивов, делать разбиение в этой точке по длинному габариту
Субъективно разницы между сценариями незаметил. но пользую 2 вариант, в надежде что он лучше))
Вот отчет о разбиении тестового чертежа:

Запущена команда:TreeStat
Total entities in drawing: 21250
Max tree depth: 16
Max in node entities: 500
Current drawing spatial index Info:
Total entities: 21250
Memory usage (bytes): 16965
Total nodes: 117
Total overflow nodes: 0
Fact tree depth: 8
By levels:
level 0
Entities: 31
Entities(%)[summary]: 0.15[0.15]
Nodes: 1
Overflow nodes: 0
level 1
Entities: 38
Entities(%)[summary]: 0.18[0.32]
Nodes: 2
Overflow nodes: 0
level 2
Entities: 70
Entities(%)[summary]: 0.33[0.65]
Nodes: 4
Overflow nodes: 0
level 3
Entities: 148
Entities(%)[summary]: 0.70[1.35]
Nodes: 8
Overflow nodes: 0
level 4
Entities: 1682
Entities(%)[summary]: 7.92[9.27]
Nodes: 16
Overflow nodes: 0
level 5
Entities: 4195
Entities(%)[summary]: 19.74[29.01]
Nodes: 26
Overflow nodes: 0
level 6
Entities: 6702
Entities(%)[summary]: 31.54[60.55]
Nodes: 30
Overflow nodes: 0
level 7
Entities: 6626
Entities(%)[summary]: 31.18[91.73]
Nodes: 24
Overflow nodes: 0
level 8
Entities: 1758
Entities(%)[summary]: 8.27[100.00]
Nodes: 6
Overflow nodes: 0
Nodes with population 0: 1
Nodes with population 2: 3
Nodes with population 3: 1
Nodes with population 4: 1
Nodes with population 5: 1
Nodes with population 6: 1
Nodes with population 7: 3
Nodes with population 8: 2
Nodes with population 9: 1
Nodes with population 11: 2
Nodes with population 12: 3
Nodes with population 13: 3
Nodes with population 14: 4
Nodes with population 15: 3
Nodes with population 16: 5
Nodes with population 17: 1
Nodes with population 18: 5
Nodes with population 19: 2
Nodes with population 20: 3
Nodes with population 21: 1
Nodes with population 23: 1
Nodes with population 24: 1
Nodes with population 25: 2
Nodes with population 27: 1
Nodes with population 28: 1
Nodes with population 30: 1
Nodes with population 31: 2
Nodes with population 34: 1
Nodes with population 37: 1
Nodes with population 40: 1
Nodes with population 109: 1
Nodes with population 136: 1
Nodes with population 208: 1
Nodes with population 218: 1
Nodes with population 223: 1
Nodes with population 226: 1
Nodes with population 228: 1
Nodes with population 241: 1
Nodes with population 247: 1
Nodes with population 252: 2
Nodes with population 266: 1
Nodes with population 280: 1
Nodes with population 282: 1
Nodes with population 286: 1
Nodes with population 288: 1
Nodes with population 290: 2
Nodes with population 294: 2
Nodes with population 300: 1
Nodes with population 301: 1
Nodes with population 302: 1
Nodes with population 313: 1
Nodes with population 314: 1
Nodes with population 318: 1
Nodes with population 319: 2
Nodes with population 323: 1
Nodes with population 340: 1
Nodes with population 343: 1
Nodes with population 344: 1
Nodes with population 359: 1
Nodes with population 360: 1
Nodes with population 364: 2
Nodes with population 372: 1
Nodes with population 378: 1
Nodes with population 387: 1
Nodes with population 397: 1
Nodes with population 403: 1
Nodes with population 406: 1
Nodes with population 407: 1
Nodes with population 412: 1
Nodes with population 414: 1
Nodes with population 416: 1
Nodes with population 418: 1
Nodes with population 433: 1
Nodes with population 448: 1
Nodes with population 456: 1
Nodes with population 467: 1
Nodes with population 473: 1
Nodes with population 482: 1
Nodes with population 484: 1
Nodes with population 489: 1
Nodes with population 495: 1
Nodes with population 496: 1
Nodes with population 497: 1
Nodes with population 498: 1

Max tree depth: 16 и Max in node entities: 500 - это граничные условия при которых разбиение прекращается. 500 в ноде конечно многовато, непомню из каких соображений остановился на этой цифре. Но всё легко настраивается

Добавлено спустя 6 минут 43 секунды:
в выложенной версии TreeStat не такая информативная, а возможно и называется подругому

[Mikhail]

Если примитив, отрезок например, попадает в оба полупространства он записывается в оба узла дерева? Как в этом случае решается проблема вывода дубликатов?

[zub]

он остается в этой ноде, ниже не уходит

level 0
Entities: 31
Entities(%)[summary]: 0.15[0.15]

т.е. на первом же разбиении 31 примитив пересек плоскость разбиения. эти примитивы записываются в "корневую" ноду и из дальнейшего разбиения удаляются. Так по отчету основная масса примитивов осела на 5,6,7 уровнях разбиения

Добавлено спустя 15 минут 39 секунд:
>>попадает в оба полупространства он записывается в оба узла дерева?
при таком подходе на неподготовленных данных будет очень много дублирования. Имхо такое стоит применять там где "чертеж" готовится с учетом последующего разбиения. например в геймдеве - карту уровня вполне можно опримизировать для последующего разбиения. Для векторного редактора такое неподходит ИМХО

[Mikhail]

он остается в этой ноде, ниже не уходит

level 0
Entities: 31
Entities(%)[summary]: 0.15[0.15]

т.е. на первом же разбиении 31 примитив пересек плоскость разбиения. эти примитивы записываются в "корневую" ноду и из дальнейшего разбиения удаляются. Так по отчету основная масса примитивов осела на 5,6,7 уровнях разбиения

Добавлено спустя 15 минут 39 секунд:
>>попадает в оба полупространства он записывается в оба узла дерева?
при таком подходе на неподготовленных данных будет очень много дублирования. Имхо такое стоит применять там где "чертеж" готовится с учетом последующего разбиения. например в геймдеве - карту уровня вполне можно опримизировать для последующего разбиения. Для векторного редактора такое неподходит

По моему это не слишком хорошо, получается что все объекты попавшие на первый уровень рисуются всегда.

[zub]

Да, и не только рисуются. на дерево завязано много действий. Собственно если такие примитивы писать в обе ветки то они тоже рисоваться будут всегда (и по несколько раз, если не потратить ресурсы на учет уже нарисованого)
Идеальным решением будет резать такой примитив на части по разделителю. Но это очень сложно для примитивов сложнее линии и ИМХО неоправдано. всегда есть еденицы примитивов не ложащиеся в дерево, общая масса обычно ложится

Добавлено спустя 4 минуты 2 секунды:
отчет про чертеж из 20000 рандомных линий

Код: Выделить всё

Запущена команда:TreeStat
Total entities in drawing: 20000
Max tree depth: 16
Max in node entities: 500
Current drawing spatial index Info:
Total entities: 20000
Memory usage (bytes): 4495
Total nodes: 31
Total overflow nodes: 7
Fact tree depth: 4
By levels:
level 0
  Entities: 4987
  Entities(%)[summary]: 24.93[24.93]
  Nodes: 1
  Overflow nodes: 1
level 1
  Entities: 3824
  Entities(%)[summary]: 19.12[44.06]
  Nodes: 2
  Overflow nodes: 2
level 2
  Entities: 4962
  Entities(%)[summary]: 24.81[68.86]
  Nodes: 4
  Overflow nodes: 4
level 3
  Entities: 2865
  Entities(%)[summary]: 14.33[83.19]
  Nodes: 8
  Overflow nodes: 0
level 4
  Entities: 3362
  Entities(%)[summary]: 16.81[100.00]
  Nodes: 16
  Overflow nodes: 0
  Nodes with population 171: 1
  Nodes with population 180: 1
  Nodes with population 187: 1
  Nodes with population 192: 1
  Nodes with population 199: 1
  Nodes with population 202: 1
  Nodes with population 203: 1
  Nodes with population 205: 2
  Nodes with population 215: 1
  Nodes with population 216: 1
  Nodes with population 223: 1
  Nodes with population 231: 1
  Nodes with population 233: 1
  Nodes with population 240: 1
  Nodes with population 260: 1
  Nodes with population 319: 1
  Nodes with population 327: 1
  Nodes with population 331: 1
  Nodes with population 341: 1
  Nodes with population 369: 1
  Nodes with population 378: 1
  Nodes with population 388: 1
  Nodes with population 412: 1
  Nodes with population 1207: 1
  Nodes with population 1228: 1
  Nodes with population 1258: 1
  Nodes with population 1269: 1
  Nodes with population 1908: 1
  Nodes with population 1916: 1
  Nodes with population 4987: 1


Добавлено спустя 1 минуту 28 секунд:
25% осталось в корневой ноде. но это лучше чем ничего((

[Mikhail]

Идеальным решением будет резать такой примитив на части по разделителю.

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

[zub]

что про данный чертеж сказал автокад:

Код: Выделить всё

Command: TREESTAT

Model-space branch
-------------------
Oct-tree, depth limit = 30
Subtree containing objects with defined extents:
    Nodes: 576   Objects: 20000   Maximum depth: 30
    Average objects per node: 34.72
    Average node depth: 23.25   Average object depth: 11.89
    Objects at depth 5: 5131   6: 3677   29: 16   30: 8
    Nodes with population 0: 295   1: 130   1856: 1   5131: 1
Total nodes: 579   Total objects: 20000

ситуация почти такаяже, только больше "ненужных" разбиений

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

[Mikhail]

Тогда примитив всеравно будет полюбому нарисован

Конечно будет, но только если он действительно виден в окне просмотра, а не всегда.

ситуация почти такаяже, только больше "ненужных" разбиений

Ну не совсем такая же, высота дерева в 3 раза больше, а число объектов на узел меньше на порядок.

[zub]

>> если он действительно виден в окне просмотра, а не всегда.
Всегда))
>>высота дерева в 3 раза больше, а число объектов на узел меньше на порядок.
"высота" больше за счет пустых нод. объекты начинают идти с уровня 5, и их там в одной ноде сразу 5131.
>>а число объектов на узел меньше на порядок.
за счет 295 пустых нод))
Если отбросить "пустоту", то всё точно также

Добавлено спустя 2 минуты 48 секунд:
автокад:
на 5 уровне: 5131; на 6 уровне: 3677 ...
зкад:
на 0 уровне: 4987; на 1 уровне: 3824 ...
почти один в один))

Добавлено спустя 2 минуты 51 секунду:
если бы автокад писал полный "Nodes with population" а не несколько штук, было бы яснее

Добавлено спустя 2 минуты 27 секунд:
>>на 5 уровне: 5131
можно решить что 5131 примитивов уже не в одной ноде, а в нескольких, но Nodes with population ... 5131: 1 говорит об обратном((

[Mikhail]

Если отбросить "пустоту", то всё точно также

Ну там окт-трее.

Всегда))

Ничего подобного. Каждый примитив содержит флаг, о том что он присутствует более чем в одном узле дерева. При разбиении, если примитив рассекается, то он заносится в оба узла, устаналивается специальный флаг внутри примитива и он не исключается из списка анализируемых объектов. При прорисовке примитивы с установленным флагом перед рисованием проверяем на наличие в специальном списке дубликатов, если он там еще отсутствует, то заносим его туда и рисуем, иначе не рисуем. Т.о. в областях в которых примитив не виден он не будет рисоваться, а там где частично или полностью виден будет рисоваться один раз.

[zub]

>>Ну там окт-трее.
Должно быть в 8 раз больше пустых нод чем у меня. у меня их 0))
>>Ничего подобного
В простом случае когда коротенькая линия попала на плоскость разделения - наверно. В общем случае примитив всеравно будет отрисован либо не даст в дальнейшем нормально строить дерево. Объясните как вы планируете обработать ситуацию на приложеной картинке. примитив - замкнутая полилиния

[Mikhail]

Объясните как вы планируете обработать ситуацию на приложеной картинке. примитив - замкнутая полилиния

Очевидно что ссылки на примитив будут только в тех узлах которые содержат примитив, в узлах дерева, указанной Вами области просмотра, его нет. Т.о. он не будет выводится.

[zub]

>>указанной Вами области просмотра, его нет. Т.о. он не будет
он есть во всех ветвях дерева. т.к. разбиение идет по габариту примитива

[Mikhail]

он есть во всех ветвях дерева. т.к. разбиение идет по габариту примитива

Гм, а почему по габариту? Можно ведь классифицировать:
- полностью в окне
- полностью вне окна
- частично в окне

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