[АлексЮстасу]

Наверное, есть отработанные и даже общепризнанные способы оптимизировать обработку в программах большого числа элементов dwg-файлов?
Я имею в виду программы, которые решают задачи вроде: найти все пересечения или найти все не пересекающееся, найти все, попадающее в контур или вне его, создать все возможные замкнутые контуры или т.п.
И имею в виду не использование чисто программных способов, а на уровне алгоритмов.
Может быть опытные поделятся, если не оч. большой секрет, конечно
Это нужно мне для общения с моим программистом, а может пригодиться начинающим программистом вообще.
Я сам не программист, но постараюсь в целом понять ответы, да и поспрашиваю, если что, у разбирающихся.

Как непосвещенный, я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления, т.е. их взаимные связи (соединение, наложение, пересечение и т.п.) никак не описаны, и их взаимное положение никак не структурировано, не описано. Это правильно? И поэтому, если действовать в лоб, в подобных программах приходится определять отношение всего со всем, и, возможно, не один раз?
Если же как-то ловко описать взаимное положение и/или взаимные связи элементов, то можно будет анализировать не все элементы, а только взаимно связанные или указанным образом расположенные. Что в теории скажется на скорости работы.

И подвопрос: для файлов примерно какого размера (+-полмегабайта) или какого числа элементов (+-1000), или числа вершин элементов (+-1000) подобные ухищрения имеют смысл на не очень мощных и на хороших компьютерах? Эмпирически-экспертно, конечно.

[trir]

Один ответ

[hwd]

Ты можешь итеративно перебрать все элементы базы данных чертежа, получив все ObjectId и попутно (если нужно) группируя результаты по своему усмотрению (всё зависит от твоего алгоритма обработки). Например, итерация чертежа, размером 50Мб, с выборкой всех ObjectId и их группировкой по типам примитивов у меня заняло меньше секунды.

[trir]

Если же как-то ловко описать взаимное положение и/или взаимные связи элементов

- это называется топология

[Дима_]

Сообщение от АлексЮстасу Как непосвещенный, я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления, т.е. их взаимные связи (соединение, наложение, пересечение и т.п.) никак не описаны, и их взаимное положение никак не структурировано, не описано. Это правильно? И поэтому, если действовать в лоб, в подобных программах приходится определять отношение всего со всем, и, возможно, не один раз?

То что они храняться росто по порядку создания - это так. По второму вопросу - тут явно у вашего программиста пробелы в численных методах. Способов много - но каждый завистит от ситуации - вот подобная тема, я там излагал пару вариантов (#10,#13). Суть в общем сводиться к предварительному структурированию, либо индексированию данных в зависимости от предполагаемого их использования, в любом случае, даже если стуктура получается очень сложной для группировки - все обращение к автокаду (считывание характеристик объектов) - не более 1 раза - вся обработка должна происходить в памяти (благо с этим ресурсом сейчас в 99% задач проблем нет).

[АлексЮстасу]

Сообщение от trir Один ответ

Сообщение от trir - это называется топология

Алгоритмы-то какие?

Сообщение от hwd попутно (если нужно) группируя результаты по своему усмотрению (всё зависит от твоего алгоритма обработки)

В этом и состоит же, наверное, задача - как лучше группировать, какие самые универсальные и эффективные способы такого группирования?

Сообщение от Дима_ вот подобная тема, я там излагал пару вариантов (#10,#13). Суть в общем сводиться к предварительному структурированию, либо индексированию данных в зависимости от предполагаемого их использования

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

Еще подвопрос: что делается быстрее - получение габаритов элементов или списков их вершин? Габариты получают каким-то специальным методом или как раз просмотром координат вершин?

[gomer]

Сообщение от АлексЮстасу Габариты получают каким-то специальным методом

да.

[АлексЮстасу]

Сообщение от gomer да.

А что в целом быстрее - получить габариты или просмотреть вершины?

[trir]

Алгоритмы-то какие?

Много их, а вместе они называются - Вычислительная Геометрия

Читать:
Ф. Препарата, М. Шеймос - Вычислительная Геометрия: Введение
Майкл Ласло - Вычислительная геометрия и компьютерная графика на C++

И все они реализованы в "Пространственных базах данных" - бери и пользуйся, самые лучшие ;=)

[gomer]

Сообщение от АлексЮстасу А что в целом быстрее - получить габариты или просмотреть вершины?

габариты не всегда определяются положением вершин

[АлексЮстасу]

Сообщение от gomer габариты не всегда определяются положением вершин

Вы имеете в виду габариты криволинейных элементов, текстовых и блоков?

[hwd]

Сообщение от АлексЮстасу В этом и состоит же, наверное, задача - как лучше группировать, какие самые универсальные и эффективные способы такого группирования?

Всё зависит от того, как эти данные будут использоваться. Как вариант я когда-то показывал вот такую штуку.

[АлексЮстасу]

Сообщение от hwd Всё зависит от того, как эти данные будут использоваться. Как вариант я когда-то показывал вот такую штуку.

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

[gomer]

Сообщение от АлексЮстасу Вы имеете в виду габариты криволинейных элементов, текстовых и блоков?

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

[АлексЮстасу]

Сообщение от gomer да. но вы до сих пор не раскрыли язык на котором будете обрабатывать данные

Я думал, что язык значения для алгоритмов не имеет. Или незначительное. Потому и не упомянул. На ObjectARX.
Я допускаю, что в разных языках одни и те же действия с данными могут быть лучше-хуже обеспечены. Но здесь мне бы хотелось обсуждать больше алгоритмы, чем программистские приемы.

[DEM]

Оооо
Ты это лисперам расскажи про алгоритмы то....

[gomer]

зависит не только от языка, но и от среды в которой работает алгоритм

[hwd]

Сообщение от АлексЮстасу Если я правильно понял Вашу ссылку, то там речь идет об оптимизации обработки свойств элементов

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

[АлексЮстасу]

Сообщение от DEM Оооо Ты это лисперам расскажи про алгоритмы то....

Сообщение от gomer зависит не только от языка, но и от среды в которой работает алгоритм

Offtop: ...да, похоже, до обсуждения самих алгоритмов мы не доберемся. Видно, шибко они секретные. Или наоборот.

Сообщение от hwd Нет, это просто элементарный пример на произвольную тему. Основная идея в том, чтобы быстро получать идентификаторы нужных объектов (на основе любых фильтров, соответствующих задаче), затем на основе этих идентификаторов получать сами объекты и выполнять любую их модификацию (при необходимости). В качестве условия фильтрации можно передать любое выражение, возвращающее логическое значение. В качестве операции можно передать любой метод, соответствующий обозначенной в интерфейсе сигнатуре.

Т.е. Ваш подход оптимизирует получение всех идентификаторов и всех объектов, и применение к ним каких-то операций. Это поможет программе в целом, но это же не оптимизация определения взаимного положения и отношений элементов друг к другу? Так понимаю, что оптимизация геометрических отношений элементов конечном итоге сводится к уменьшению числа рассматриваемых в каждый момент элементов?

[gomer]

так вы давайте задачу и обсудим ее, а так все как-то абстрактно...

[hwd]

Сообщение от АлексЮстасу Это поможет программе в целом, но это же не оптимизация определения взаимного положения и отношений элементов друг к другу?

Это, как минимум, формирует наборы данных в удобной вам форме для их дальнейшей обработки в коде вашего алгоритма.

[АлексЮстасу]

Сообщение от gomer так вы давайте задачу и обсудим ее, а так все как-то абстрактно...

Конкретная задача - это же и будет абстрактно.
Чем не задачи, которые я привел в первом сообщении и в "т.п."? Мы сейчас пишем почти одновременно примерно семь подобных программ, и во всех делается фактически одно - многократный перебор всех элементов с установлением их взаимного положения, отношений и связей. И такого же рода программ придется писать еще несколько и в ближайшее время, и, похоже, позже.

Сообщение от hwd Это, как минимум, формирует наборы данных в удобной вам форме для их дальнейшей обработки в коде вашего алгоритма.

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

[hwd]

Сообщение от АлексЮстасу Оптимизирует ли это количество обрабатываемых в каждый момент элементов? Вероятно, просмотр всех элементов неизбежен, и в этом Ваше решение может быть очень полезным. Но это только подход к задаче. Как бы в процессе этого просмотра элементов создать такое описание их положения и формы, чтобы при последующем анализе просматривать уже не все, а в основном потенциально необходимые элементы?

Возможность оптимизации набора и избежание лишних просмотров конечно же присутствуют (в этом-то и заключается основная идея). Чтобы ответить на эти вопросы более конкретно, мне нужно видеть код, к которому это нужно прикрутить.

[zamtmn]

>>Как непосвещенный, я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления,т.е. их взаимные связи (соединение, наложение, пересечение и т.п.) никак не описаны, и их взаимное положение никак не структурировано, не описано. Это правильно?
Нет, не правильно. При обработке примитивов автокад вовсю использует пространственное разбиение
>>для файлов примерно какого размера (+-полмегабайта) или какого числа элементов (+-1000), или числа вершин элементов (+-1000) подобные ухищрения имеют смысл на не очень мощных и на хороших компьютерах? Эмпирически-экспертно, конечно.
Всякого рода "ухищрения" имеют смысл всегда, иначе программа будет тормозить на любом компьютере

[АлексЮстасу]

Сообщение от hwd Возможность оптимизации набора и избежание лишних просмотров конечно же присутствуют (в этом-то и заключается основная идея). Чтобы ответить на эти вопросы более конкретно, мне нужно видеть код, к которому это нужно прикрутить.

Но я не вижу в Вашем описании упоминания о геометрической оптимизации. Если она есть, то опишите, плз, эту часть Вашего алгоритма. По возможности общечеловеческими словами.

Сообщение от zamtmn При обработке примитивов автокад вовсю использует пространственное разбиение

Можно узнать какое, в чем оно выражается? И как им лучше воспользоваться?

[hwd]

Сообщение от АлексЮстасу Но я не вижу в Вашем описании упоминания о геометрической оптимизации.

Похоже мы на разных языках разговариваем... Обозначенный мною выше код позволяет манипулировать данными, имеющими свой ObjectId, создавая наборы элементов, подлежащих обработке и, при необходимости, модифицируя их. Код писался не для некой "геометрическую оптимизации", а для более общих задач. Я не знаю как ещё объяснять - вроде там всё должно быть понятно из кода, т.к. постарался там разжевать всё как можно подробней, насколько это возможно.

[zamtmn]

>>Можно узнать какое, в чем оно выражается?
Выражается в скорости работы, недостижимой при подходе "я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления,т.е.". Т.е. в dwg файле они так и хранятся (хотя там присутствуют некие SPATIAL_FILTER, SPATIAL_INDEX - не вникал что они в себе несут), но обрабатывается всё это хозяйство явно не "всё по очереди"
>>И как им лучше воспользоваться?
Это вопрос к местным корифеям, какие свои механизмы автокад предоставляет наружу.
В порядке ознакомления что это и зачем лучше заглянуть в википедию и почиать про http://en.wikipedia.org/wiki/K-d_tree и подобные алгоритмы

[АлексЮстасу]

Сообщение от hwd Похоже мы на разных языках разговариваем... Обозначенный мною выше код позволяет манипулировать данными, имеющими свой ObjectId, создавая наборы элементов, подлежащих обработке и, при необходимости, модифицируя их. Код писался не для некой "геометрическую оптимизации", а для более общих задач. Я не знаю как ещё объяснять - вроде там всё должно быть понятно из кода, т.к. постарался там разжевать всё как можно подробней, насколько это возможно.

Просто я не вижу, где в Вашем способе описано, что он позволит для созданного набора элементов оптимизировать (ускорить, упростить) решение геометрических задач. С помощью чего в нем становится известно, что такую-то полилинию могут, допустим, пересекать такие-то полилинии, а другие можно не рассматривать, что в допустимой близости могут находиться вот эти полилинии, а другие нет и т.д. и т.п.? Хотя бы укажите соответствующие пункты или абзацы в Вашей ссылке.

Сообщение от zamtmn Выражается в скорости работы, недостижимой при подходе "я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления,т.е.". Т.е. в dwg файле они так и хранятся (хотя там присутствуют некие SPATIAL_FILTER, SPATIAL_INDEX - не вникал что они в себе несут), но обрабатывается всё это хозяйство явно не "всё по очереди"

Т.е. сама фирма некую оптимизацию использует, но какую - неизвестно? И Вы считаете, что в самих dwg файлах есть что-то вроде индексации или т.п., но что именно - тоже неизвестно?

[zamtmn]

>>Т.е. сама фирма некую оптимизацию использует, но какую - неизвестно? И Вы считаете, что в самих dwg файлах есть что-то вроде индексации или т.п., но что именно - тоже неизвестно?
Неизвестно мне и вам. Я же говорю, пусть знатоки выскажутся - что на эту тему можно выудить из arx - вполне возможно что ничего, но это не значит что не использует. Говоря про dwg файл я подразумеваю файл лежащий на диске, а не dwg открытый автокадом.

[АлексЮстасу]

Сообщение от zamtmn Неизвестно мне и вам. Я же говорю, пусть знатоки выскажутся - что на эту тему можно выудить из arx - вполне возможно что ничего, но это не значит что не использует. Говоря про dwg файл я подразумеваю файл лежащий на диске, а не dwg открытый автокадом.

Offtop: В тему наблюдение из жизни: Microstation в среднем работает явно быстрее Автокада. В том числе и с dwg-файлами.
Расколюсь. В пятницу, 13-го, в конце рабочего дня породил некий алгоритмище оптимизации (ну, сами понимаете, что может придумать 13-го в пятницу вечером не программист ). Стеснялся об этом здесь поминать.
Но попробую приложить - для некоего примера того, что я имею в виду.

[trir]

Книжки читать видимо не модно, то что вы изобретаете - называется k-d дерево, в книжке Препараты глава 2 Геометрический поиск, 2.3.2. Метод многомерного двоичного дерева (k-D-дерева)

[АлексЮстасу]

Сообщение от trir Книжки читать видимо не модно, то что вы изобретаете - называется k-d дерево, в книжке Препараты глава 2 Геометрический поиск, 2.3.2. Метод многомерного двоичного дерева (k-D-дерева)

Приведенные Вами книги обязательно передам программисту.
Почему именно этот метод? Чем этот метод лучше других?
Вы полагаете, что этот метод не только лучший, но еще и хорошо реализуется программно?
Вам известны примеры его применения в каких-то программах под Автокад?

Кстати, в #27 zamtmn привел в пример именно K-d_tree.

[zamtmn]

trir
Придумывать, а потом читать книжки реально интересней))

АлексЮстасу
Добавте в алгоритм пару пунктов:
-Лучше ввести древовидную структуру данных, т.к. 1)еще больший профит за счет отбраковки всех дочерних "подпространств" путем отбраковки вышестоящего, 2) реальные а не подготовленные данные наврятли можно вписать в какую либо "сетку" - всегда будут примитивы которые будут всё портить - пересекать границы в которые хорошо вписываются другие примитивы, 3) удобно "ограничить" процесс построения такого дерева количеством примитивов в "листах" и глубиной вложенности
-В случае наличия в данных "длинных" примитивов - например полилиний с большим кол-вом сегментов ваш алгоритм стоит применять и внутри примитивов (т.е. грубо говоря считать полилинию набором отрезков и дуг)

update:

Offtop: В тему наблюдение из жизни: Microstation в среднем работает явно быстрее Автокада. В том числе и с dwg-файлами.

хз, Microstation видел лет 10 назад. В качестве примера программы которяа не использует подобные оптимизации могу привести LibreCAD - он всё обрабатывает "в лоб". Поставте, сравните на большом чертеже.

update2:
когда я вникал в потроха LibreCAD он был еще 1.0, сейчас уже 2.0rc, такчто возможно он уже поумнел и не "в лоб"

[gomer]

что будет, если после того, как вы посадили дерево, кто-то захочет приклеить еще листик к чертежу? И что, охранять дерево всю жизнь? А если оно разрастется так, что перестанет влезать в ваш кабинет?

[zamtmn]

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

[АлексЮстасу]

Сообщение от gomer что будет, если после того, как вы посадили дерево, кто-то захочет приклеить еще листик к чертежу? И что, охранять дерево всю жизнь? А если оно разрастется так, что перестанет влезать в ваш кабинет?

Я предложил алгоритм без изысков, во-первых, чтобы в принципе объяснить, что имею в виду, и, во-вторых, мне - непрограммисту - неизвестна трудоемкость операций для Автокада или для программиста. Возможный ассортимент действий тоже неизвестен. Поэтому пытался использовать минимум действий с элементами. Фактически два: определять общие габариты элементов и определять габариты сегментов. Написал, было, создавать при ID элементов для ячеек списки вершин, попадающих в эти ячейки, но убрал. Все потому же - не могу оценить трудоемкость (вредоносность/эффективность).
Т.е. этот алгоритм следует понимать не совсем буквально, а как некий эскиз для предложений.
Алгоритм предназначен для работы самой программы, его описание данных живет только в процессе выполнения программ - и никак не влияет на сами данные, на их структурирование в файле. Поэтому и изменение данных ("приклеивание листьев", веток и пр. к чертежу) не влияет на него.

Сообщение от zamtmn -Лучше ввести древовидную структуру данных, т.к. 1)еще больший профит за счет отбраковки всех дочерних "подпространств" путем отбраковки вышестоящего, 2) реальные а не подготовленные данные наврятли можно вписать в какую либо "сетку" - всегда будут примитивы которые будут всё портить - пересекать границы в которые хорошо вписываются другие примитивы, 3) удобно "ограничить" процесс построения такого дерева количеством примитивов в "листах" и глубиной вложенности -В случае наличия в данных "длинных" примитивов - например полилиний с большим кол-вом сегментов ваш алгоритм стоит применять и внутри примитивов (т.е. грубо говоря считать полилинию набором отрезков и дуг)

Поясните, плз, пункт 2).
Габарит сетки >= габариту файла.

Сообщение от zamtmn Если автокад не предоставляет подобных "интерфейсов" то дерево садить придется только перед проведением массивных геометрических вычислений, после рубить на дрова. Хотя уверенн что все элементарные операции (типа поиска пересечений или примитивов в окресности) в автокаде подобным образом и устроены и только ради них такое городить нестоит

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

[zamtmn]

>>Поясните, плз, пункт 2).
Для примера файл из 10 полилиний по 10000 сегментов в каждой. Построение дерева на уровне примитивов в таком случае эффекта иметь не будет. Если же для каждой полилинии выполнить разбиение (отдельно или в общей структуре данных) эффект появится - т.к. перебор 10000 сегментов заменится двоичным поиском.

>>Все потому же - не могу оценить трудоемкость (вредоносность/эффективность).
на коленке написаный алгоритм разбиения на паскале занял ~500 строк. эффект получился значительный - в программе-тормозилке стало возможно вполне комфортно работать. Но были большие сложности подружить его с уже работающими фрагментами.
построение дерева для 21000 примитивов, 500 примитивов в ноде, максимальная глубина берева 16:

Running command:RebuildTree Rebuild drawing spatial: 0.04 second Total entities: 21250 Tree depth : 8

построение дерева для 21000 примитивов, 10 примитивов в ноде, максимальная глубина берева 16:

Running command:RebuildTree Rebuild drawing spatial: 0.07 second Total entities: 21250 Tree depth : 15

[АлексЮстасу]

Сообщение от zamtmn построение дерева для 21000 примитивов, 500 примитивов в ноде, максимальная глубина берева 16

Что такое "примитивы в ноде"?
Можете на пальцах изложить принципы, метод "построения дерева"? Для не математиков в том числе

[hwd]

Сообщение от АлексЮстасу Что такое "примитивы в ноде"? Можете на пальцах изложить принципы, метод "построения дерева"? Для не математиков в том числе

Node (узел). Уже сто раз можно было в интернете самостоятельно найти и прочитать информацию по теме построения деревьев...

[zamtmn]

Я не програмист поэтому извиняюсь если путаю термины. Также это всё хозяйство было написано без оглядки на толковые книжки - я их читал когдато давно в детстве.
Нода в моей реализации - ограничивающий объем+плоскость делящая ноду+ссылка на ноду "левее" плоскости+ссылка на ноду "правее" плоскости+список примитивов которые пересекаются плоскостью

1.На вход приходит срисок примитивов+уже посчитаный ограничивающий объем всех примитивов
2.создаем ноду
3.если (примитивов<примитивов в ноде)или(глубина дерева>максимальная глубина берева) то пишем все примитивы в список пересекающихся плоскостью, выходим возвращая созданную ноду
3.выбираем плоскость разбиения (тут я прибумывал всякие хитрые способы, но просто разбивать пополам перпендикулярно самой длинной оси ничють не хуже всяких хитростей)
4.список примитивов делим на 3 списка 1-левее плоскости, 2-правее плоскости, 3-пересекаются плоскостью
5. пишем список 3 в список пересекающихся плоскостью
6. ссылка на ноду "левее" плоскости=рекурсивный вызов п.1 со списком 1 и его ограничивающим объемом
7. ссылка на ноду "правее" плоскости=рекурсивный вызов п.1 со списком 2 и его ограничивающим объемом

на выходе получается рекурсивное дерево ограничивающих объемов с перечнем примитивов в него попавших. разбиение продолжается пока не будет достигнута максимальная глубина или количество примитивов в ноде не будет меньше заданного

Что такое "примитивы в ноде"?

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

ps. На оптимальность алгоритма я не претендую

[АлексЮстасу]

"Плоскость", "объем" - у Вас анализ 3D или это просто такие термины?

[zamtmn]

Алгоритм работает одинакво и для 3Д и для 2Д. но нужно либо учесть вырождение объема\плоскости в прямоугольник\прямую, либо в случае "плоского" ограничивающего объема дать ему минимальную разбежку по нулевой оси (т.е. сделать совсем чуть чуть неплоским)
Я использую второй вариант, по "плоской" оси разбиение производится небудет, т.к. она всегда будет минимальной

[АлексЮстасу]

Сообщение от zamtmn Алгоритм работает одинакво и для 3Д и для 2Д. но нужно либо учесть вырождение объема\плоскости в прямоугольник\прямую, либо в случае "плоского" ограничивающего объема дать ему минимальную разбежку по нулевой оси (т.е. сделать совсем чуть чуть неплоским) Я использую второй вариант, по "плоской" оси разбиение производится небудет, т.к. она всегда будет минимальной

Делящие плоскости вертикальные? По осям XZ, YZ?

Пока перевариваю.........

Могу предложить тем, кому желательны примеры, задачу: находить (создавать) для всего набора линейных элементов все возможные минимальные замкнутые контуры. Контуры точные, полные и все - в отличие от фирменной BOUNDARY, которая к тому же только штучная. Задача вполне реальное решение имеет. Например, FlashPolygons от Delicad.
Offtop: Правда, попробовал сегодня свежезагруженную версию FlashPolygons, и такое ощущение, что они что-то так улучшили, что она еле телепается. Опробовал ее в 2010 на файлах с десятками тысяч элементов, и она строила все контуры считанные секунды. А компьютер был послабее, и был XP. Видимо, они ее оптимизировали Во-вторых, она не видит сплайны и 3D элементы. Пользоваться ей можно бесплатно 20 раз.
Предполагаю, что в этой задаче процедуры только самые простые: найти все пересечения всех элементов, и на их основе собрать все замкнутые минимальные контуры. Элементы и их части после разбивания на пересечениях, чьи начальные-конечные точки ни к чему не примыкают, игнорируются. Для упрощения сплайны,трехмерные элементы не рассматриваем. Исходные элементы сохраняются в их исходном состоянии. Допустим, добиваемся, чтобы результат получался на 2-3 десятках тысяч элементов из десятков и сотен сегментов каждый за, максимум, 5-7 секунд.

[zamtmn]

>>Делящие плоскости вертикальные? По осям XZ, YZ?
да (еще XY для 3Д случая), ограничвающий объем тоже "выровнен" по осям - т.н. AABB (Axis-Aligned Bounding Box) При этом ограничивающий объем "левого" и "правого" списка можно почесному пересчитать, а можно рассеч плоскостью исходный. Я не пересчитываю, при этом "хватается" лишнее пустое пространство, но для "среднестатистического" чертежа это ИМХО не критично. критично для очень "разряженного" чертежа
Поиск пересечений я сегодня организую, если будет свободная минута, для самого элементарного случая - чертеж из N линий. Из спортивного интереса - посмотреть как влияют параметры "дерева" на время нахождения всех пересечений.
А вот искать контуры (насколько понимаю это возня с графами) на данный момент мне не интересно и не по зубам))

update:
В #37 забыл упомянуть циферки про расход памяти под всё это дело:
чертеж тотже, 21250 примитивов, x86_64 сборка

для случая с 500 примитивов в ноде
выделено памяти под списки примитивов в нодах: 223912 байт
выделено памяти под сами ноды: 22042 байт

для случая с 10 примитивов в ноде
выделено памяти под списки примитивов в нодах: 223912 байт
выделено памяти под сами ноды: 702460 байт

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

[АлексЮстасу]

Сообщение от zamtmn Поиск пересечений я сегодня организую, если будет свободная минута, для самого элементарного случая - чертеж из N линий. Из спортивного интереса - посмотреть как влияют параметры "дерева" на время нахождения всех пересечений. А вот искать контуры (насколько понимаю это возня с графами) на данный момент мне не интересно и не по зубам))

Хорошо бы где-то нарыть соответствующего объема и содержания тестовый файл. Я, к сожалению, не успеваю пока его соорудить, но постараюсь в ближайшее время.

[zamtmn]

Вроде сделал поиск пересечений, особо не проверял, но с виду работает правильно, даже если и пропускает несколько пересечений, то на общую картину это не влияет - для замера времени пойдет
Для теста соорудил 2 файла, скриншоты с визуализацией сетки (серым сетка, красным - линии) разбиения прилагаю (для случая с 10 примитивами в ноде)
regular.dxf - представляет собой регулярную сетку из крестов образованных 2мя короткими линиями, всего 20000 линий, 10000 пересечений. Это идеальный случай - он отлично пространственно разбивается
nonregular.dxf - мешанина из 20000 случайных линий сопоставимых по размерам с габаритами чертежа, кол-во пересечений 11559108. Наихудший случай - в разбивку попадает очень мало линий, они слишком длинные и "кучные"

тест прилагаю в виде лога последовательного выполнения 2х команд разделенных "-------------------------------------" для разных условий
первая RebuildTree строит "дерево"
вторая FindAllIntersections собственно ищет пересечения
тест проводил для разбиений до 10,100,1000,10000 примитивов в "ноде" (Max in node entities), последний случай (100000) представляет собой фактическое отсутствие разбиения, все примитивы находятся в корневой "ноде", никакого разбития нет

пояснения для вывода команд:

Запущена команда:RebuildTree Rebuild drawing spatial: -затраченое время на построение дерева Total entities: -всего обработано примитивов Fact tree depth: -фактическая глубина полученного "дерева" Max tree depth: -заданная максимальная глубина Max in node entities: -заданное кол-во примитивов в ноде при котором дальнейшее разбиение не ведется Запущена команда:FindAllIntersections Search intersections: -затраченое время на поиск пересечений Line-AABB tests count: -количество проведенных тестов попадания линии в ограничивающий объем Line-Line tests count: -количество проведенных тестов пересечения линий Intersections count: -количество найденных пересечений линий

Лог для regular.dxf

Запущена команда:RebuildTree Rebuild drawing spatial: 0.05 секунд Total entities: 20000 Fact tree depth: 11 Max tree depth: 16 Max in node entities: 10 Запущена команда:FindAllIntersections Search intersections: 0.06 секунд Line-AABB tests count: 114732 Line-Line tests count: 653750 Intersections count: 10000 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.04 секунд Total entities: 20000 Fact tree depth: 8 Max tree depth: 16 Max in node entities: 100 Запущена команда:FindAllIntersections Search intersections: 0.10 секунд Line-AABB tests count: 35356 Line-Line tests count: 1323427 Intersections count: 10000 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.04 секунд Total entities: 20000 Fact tree depth: 5 Max tree depth: 16 Max in node entities: 1000 Запущена команда:FindAllIntersections Search intersections: 0.43 секунд Line-AABB tests count: 5556 Line-Line tests count: 6922899 Intersections count: 10000 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.02 секунд Total entities: 20000 Fact tree depth: 1 Max tree depth: 16 Max in node entities: 10000 Запущена команда:FindAllIntersections Search intersections: 6.16 секунд Line-AABB tests count: 0 Line-Line tests count: 99990000 Intersections count: 10000 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.01 секунд Total entities: 20000 Fact tree depth: 1 Max tree depth: 0 Max in node entities: 10000 Запущена команда:FindAllIntersections Search intersections: 13.90 секунд Line-AABB tests count: 0 Line-Line tests count: 199990000 Intersections count: 10000

Лог для nonregular.dxf

Запущена команда:RebuildTree Rebuild drawing spatial: 0.03 секунд Total entities: 20000 Fact tree depth: 7 Max tree depth: 16 Max in node entities: 10 Запущена команда:FindAllIntersections Search intersections: 7.97 секунд Line-AABB tests count: 568084 Line-Line tests count: 87192949 Intersections count: 11559108 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.03 секунд Total entities: 20000 Fact tree depth: 5 Max tree depth: 16 Max in node entities: 100 Запущена команда:FindAllIntersections Search intersections: 7.99 секунд Line-AABB tests count: 269616 Line-Line tests count: 87862625 Intersections count: 11559108 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.03 секунд Total entities: 20000 Fact tree depth: 3 Max tree depth: 16 Max in node entities: 1000 Запущена команда:FindAllIntersections Search intersections: 8.52 секунд Line-AABB tests count: 88848 Line-Line tests count: 94110466 Intersections count: 11559108 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.02 секунд Total entities: 20000 Fact tree depth: 1 Max tree depth: 16 Max in node entities: 10000 Запущена команда:FindAllIntersections Search intersections: 13.26 секунд Line-AABB tests count: 10268 Line-Line tests count: 144740952 Intersections count: 11559108 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.01 секунд Total entities: 20000 Fact tree depth: 1 Max tree depth: 0 Max in node entities: 100000 Запущена команда:FindAllIntersections Search intersections: 17.04 секунд Line-AABB tests count: 0 Line-Line tests count: 199990000 Intersections count: 11559108

Собственно результат налицо - в идеальном случае разница "хитрого" и "влоб" подходов на порядки 0.11сек против 13.9сек, в худшем случае разница в разы 8сек против 17.04сек при копеечных затратах на построение этого самого "дерева". Реальные чертежи обычно хорошо "разбиваются", случаев подобных nonregular.dxf мне не попадалось

[АлексЮстасу]

Приложите nonregular.dxf здесь или во всем доступное место.
Чтобы использовать как тестовый для разных методов и программ.
И на компьютере с какими характеристиками это делалось?

Еще интересно посмотреть, как оптимизация влияет на работу программ на небольших файлах. Допустим, элементов на 1000.

[zamtmn]

>>Чтобы использовать как тестовый для разных методов и программ.
Приложил. Я его взял как наихудший из возможных, в реальности так плох небывает. Для тестов нужно чтото реальнеое.
>>И на компьютере с какими характеристиками это делалось?
i5-2400, 8Gb, Kubuntu 13.04, x86_64
>>Еще интересно посмотреть, как оптимизация влияет на работу программ на небольших файлах. Допустим, элементов на 1000.
Давайте файл, посмотрю

[АлексЮстасу]

Сообщение от zamtmn Давайте файл, посмотрю

А Вы обрежьте файл nonregular.dxf.

[zamtmn]

мешанину из 1000 примитивов нужно на компе послабже тестить
файл приложен - 1172 линии, 22067 пересечения, картинка для "разбиения" "по 10" приложена.
лог для случаев 10, 100, 1000, 2000(без разбиения)

Запущена команда:RebuildTree Rebuild drawing spatial: 0.01 секунд Total entities: 1172 Fact tree depth: 6 Max tree depth: 16 Max in node entities: 10 Запущена команда:FindAllIntersections Search intersections: 0.02 секунд Line-AABB tests count: 7850 Line-Line tests count: 113453 Intersections count: 22067 Запущена команда:RebuildTree ------------------------------------- Rebuild drawing spatial: 0.01 секунд Total entities: 1172 Fact tree depth: 4 Max tree depth: 16 Max in node entities: 100 Запущена команда:FindAllIntersections Search intersections: 0.02 секунд Line-AABB tests count: 2092 Line-Line tests count: 135698 Intersections count: 22067 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.01 секунд Total entities: 1172 Fact tree depth: 1 Max tree depth: 16 Max in node entities: 1000 Запущена команда:FindAllIntersections Search intersections: 0.04 секунд Line-AABB tests count: 54 Line-Line tests count: 360342 Intersections count: 22067 ------------------------------------- Запущена команда:RebuildTree Rebuild drawing spatial: 0.01 секунд Total entities: 1172 Fact tree depth: 1 Max tree depth: 0 Max in node entities: 2000 Запущена команда:FindAllIntersections Search intersections: 0.06 секунд Line-AABB tests count: 0 Line-Line tests count: 686206 Intersections count: 22067

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

upd:
было бы интересно услышать результаты для приложенных файлов полученные штатными ARX средствами на сопоставимом компьютере

[АлексЮстасу]

Сообщение от zamtmn Вроде сделал поиск пересечений

Вы делаете пересечения, т.е. разбиваете элементы или только их находите?
Дело в том, что просто поиском пересечений никакие готовые программы не занимаются. Их находят, и что-то с ними делают - разбивают элементы в них, вставляют что-то и пр. Т.е. время затрачивается еще и на это. Если Вы их только находите, то сравнивать скорости программ невозможно.

[zamtmn]

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

[АлексЮстасу]

Сообщение от zamtmn Порезат по этой информации линии или вставить туда чтото в принципе несложно, но это другая тема - тут геометрическая оптимизация непоможет

Тут оптимизация и не ожидается. Действие нужно для сравнения скорости.

Сообщение от zamtmn было бы интересно услышать результаты для приложенных файлов полученные штатными ARX средствами на сопоставимом компьютере

Нашей программы еще не существует.
Запустил этот файл на разбиение в пересечениях штатным инструментом Autocad Map 3D - Drawing cleanup-Break intersections. На неплохой машине, и машине немного похуже. Оба раза прождал минут сорок-пятьдесят - так и закрывал Автокад, не дождавшись.
Запустил здешней лисп-программой от VVA - BreakObjects22а. Результат такой же - тоже закрыл Автокад прерыванием работы через час молотьбы.
Пока что получается, что Ваша программа и без всякой оптимизации работает с однозначно фантастической скоростью. Либо Автокад тормозит на собственно разбивании, на создании новых элементов.

В этих файлах у элементов отрицательные координаты. Если меньший чертеж передвинуть в положительные координаты, то Drawing cleanup-Break intersections сделала все пересечения примерно за 8 секунд. А лисп BreakObjects22а по-прежнему не может завершить обработку.
На большем чертеже и Drawing cleanup-Break intersections тоже не может закончить.
Как-то непонятно... Тем более, что файлы я перед этим полечил, почистил, перекопировал содержимое в новый файл на основе штатного шаблона.

[Кулик Алексей aka kpblc]

АлексЮстасу, не путай нахождение пересечений и выполнений операций с примитивами. Первое может занимать во много раз меньше времени, чем второе.

[zamtmn]

Приделал установку примитива "точка" в найденных точках пересечения, в выводе появился параметр Placing points - соответственно время затраченное на расстановку точек.
Результат для regular.dxf:

Запущена команда:RebuildTree Rebuild drawing spatial: 0.05 секунд Total entities: 20000 Fact tree depth: 11 Max tree depth: 16 Max in node entities: 10 Запущена команда:FindAllIntersections Search intersections: 0.07 секунд Placing points: 0.01 секунд Line-AABB tests count: 114732 Line-Line tests count: 653750 Intersections count: 10000

Результат для nonregular2.dxf:

Запущена команда:RebuildTree Rebuild drawing spatial: 0.01 секунд Total entities: 1172 Fact tree depth: 6 Max tree depth: 16 Max in node entities: 10 Запущена команда:FindAllIntersections Search intersections: 0.02 секунд Placing points: 0.03 секунд Line-AABB tests count: 7850 Line-Line tests count: 113453 Intersections count: 22067

С nonregular.dxf всё сложно - 11 миллилнов точек это не хухры-мухры. Процесс автоматически грохается сторожем памяти на этапе расстановки точек, т.к. работаю я без файла подкачки а памяти всего 8Gb. Последнее что я вижу в системном мониторе - расход памяти процесса переваливает за 5Gb.

[trir]

"Процесс автоматически грохается сторожем памяти на этапе расстановки точек" - поэтому я и говорю, что надо использовать Пространственную БД.
1. Пространственный индекс - то же дерево или лучше
2. SQL позволяет выполнять выборку нужных объектов
3. Сервер БД сам заморачивается с памятью
Нефиг изобретать велосипед, когда есть готовое решение...

[zamtmn]

>>Нефиг изобретать велосипед, когда есть готовое решение...
Я неспорю что это всё есть, но пожалуйста озвучте циферки результатов. Иначе это не готовое решение а "чтото там есть" и "вроде как для этого и задумывалось".
Свои поделки я никому не навязываю как готовое решение, просто мне это интересно.

update:
Приделал резалку по точкам пересечения. результаты для nonregular2.dxf с коментариями к новым параметрам:

Запущена команда:RebuildTree Rebuild drawing spatial: 0.01 секунд Total entities: 1172 Fact tree depth: 6 Max tree depth: 16 Max in node entities: 10 Запущена команда:FindAllIntersections Search intersections and storing data: 0.03 секунд - кроме поиска появилсь обработка данных для последующей нарезки, время немного выросло Placing points: 0.03 секунд Cutting lines: 0.09 секунд - время на подрезку линий Lines modified: 1169 - линий изменено Lines created: 44134 - создано новых линий Freeing memory: 0.01 секунд Line-AABB tests count: 7850 Line-Line tests count: 113453 Intersections count: 22067

Обработанный файл прилагаю. В оригинале у меня на местах пересечения еще точки стояли, но чето с их сохранением в DXF появились проблемы, поэтому без них.

[АлексЮстасу]

Сообщение от trir я и говорю, что надо использовать Пространственную БД

Такие чисто геометрические процессы, как разбивать пересечения, создавать контуры, находить попавшее в контуры и пр. больше всего нужны для первичной подготовки данных. Еще сугубо графических - линий, блоков, текстов и пр. В том числе для сбора и подготовки сырья для наполнения пространственных БД. Которую технологично делать в голых CADах или в них же, но дополненных для подготовки данных для этих пространственных БД. В такие БД нельзя же загружать неподготовленное соответствующим образом сырье - без топологической коррекции и пр. Поэтому программки типа разбивания пересечений и пр. нужны в первую очередь еще на уровне собственно CADов.
Против возможностей самих пространственных БД совершенно ничего не имею! Прямо наоборот.

Сообщение от zamtmn Я неспорю что это всё есть, но пожалуйста озвучте циферки результатов.

Все, кто просил примеры и конкретные задачи, куда-то испарились

Сообщение от zamtmn результаты для nonregular2.dxf с коментариями к новым параметрам:

У Вас там в сумме и полсекунды не набирается. Время на отрисовку на экране как-то влияет? Или Вы обрабатываете не загруженные файлы?
На чем у Вас написано? В целом же как-то несравнимо у Вас все быстро и без оптимизаций.

[zamtmn]

Функция разбиения сырая, но не неоптимизированная. Там отсутствуют проверки на всякие закрытые слои, обрабатывается вся модель, а не выбранные примитивы... и прочие "мелочи". Поиск пересечений оптимизировать наврятли получится, разве что обнаружится какойнибудь глобальный косяк в алгоритме. Время создания-изменения примитивов возрастет раза в полтора-два после заворачивания в undo\redo. Наверно можно будет выиграть несколько процентов "подтасовывая" данные приготавливаемые к последующей нарезке - но кординально оптимизировать там нечего

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

[АлексЮстасу]

Сообщение от zamtmn для самодельной кад программы

Гм... В этом случае сравнивать вообще невозможно. Мне говорят, что в Автокаде просто по разу просмотреть 1000 элементов никак в 0.01 секунды не уложишься. И т.д.

[zamtmn]

>>Мне говорят, что в Автокаде просто по разу просмотреть 1000 элементов никак в 0.01 секунды не уложишься. И т.д.
На лиспе может быть. Но на ARX - очень сомнительно

[АлексЮстасу]

Сообщение от zamtmn Но на ARX - очень сомнительно

Это мне и сказал ARX-вец, хотя и не очень еще опытный.

[gomer]

лисп на порядок медленнее, чем аркс

[hwd]

Сообщение от АлексЮстасу Мне говорят, что в Автокаде просто по разу просмотреть 1000 элементов никак в 0.01 секунды не уложишься. И т.д. На лиспе может быть. Но на ARX - очень сомнительно.

Сообщение от АлексЮстасу Это мне и сказал ARX-вец, хотя и не очень еще опытный.

Говорят кур доят... Это с каких пор AutoLISP\Visual Lisp стал быстрее, чем C++ или .NET?.

Теперь насчёт этого:

Сообщение от zamtmn по разу просмотреть 1000 элементов никак в 0.01 секунды не уложишься.

Это звездёж и вот тому подтверждение. Результаты обозначены на .NET, а ARX будет даже побыстрее (хоть и не намного). Как видим в файле, объёмом 51Мб на то, чтобы в итерации перебрать 736 323 примитива, уходит 0,278 сек. А теперь разделите 0,278 на 736,323 и узнаете, за какое время просмотрено 1000 элементов: 0,000378 сек.

[АлексЮстасу]

Сообщение от hwd Результаты обозначены на .NET, а ARX будет даже побыстрее (хоть и не намного). Как видим в файле, объёмом 51Мб на то, чтобы в итерации перебрать 736 323 примитивов, уходит 0,278 сек.

А вот это уже серьезно вдохновляет!

[hwd]

Сообщение от АлексЮстасу А вот это уже серьезно вдохновляет!

Но если делать через ж@пу, то эти же данные можно перебирать и целых 5 мин 36 сек.

[zamtmn]

hwd
Цитаты все попутаны
>>Говорят кур доят... Это с каких пор AutoLISP\Visual Lisp стал быстрее, чем C++ или .NET?.
очень сомнительно - значит я сомневаюсь что ARX не осилит такой элементарщины. И что имхо он гораздо быстрее. Но точно сказать немогу - не в зуб ногой в нем

[hwd]

Сообщение от zamtmn Цитаты все попутаны

Спасибо, исправил.

Сообщение от zamtmn очень сомнительно - значит я сомневаюсь что ARX не осилит такой элементарщины.

Значит я тебя неправильно понял.

Сообщение от АлексЮстасу А вот это уже серьезно вдохновляет!

А эта фраза свидетельствует о том, что ты нихрена не смотришь ссылки, которые тебе дают в ответах. В #3 я тебе уже писал об этом эксперименте:

Сообщение от hwd Например, итерация чертежа, размером 50Мб, с выборкой всех ObjectId и их группировкой по типам примитивов у меня заняло меньше секунды.

а в #12 я тебе давал ссылку на то, что тебя так "вдохновило" аж в посте #65 (спустя четыре страницы).

[gomer]

AcDbZombieObject

[Boxa]

Сообщение от gomer Цитата: AcDbZombieObject

ну да, особенное чувство юмора у автодеска
смотрел тут...

Код:

[Выделить все]

 if (entId.ObjectClass.Name == "AcDbZombieEntity")
{
ProxyEntity ent =  (ProxyEntity)tr.GetObject(entId, OpenMode.ForRead);
}

[zamtmn]

Щас глянул выложенные файлы в автокаде, извиняюсь за ошибки в них - в линуксе брикс грузил их не ругаясь - поэтому недоглядел. Хотя в принципе нестрашно - восстановление помогает

[gomer]

Сообщение от zamtmn в линуксе брикс грузил их не ругаясь

брикскад много чего не считает за ошибку...

[АлексЮстасу]

Сообщение от hwd А эта фраза свидетельствует о том, что ты нихрена не смотришь ссылки, которые тебе дают в ответах. В #3 я тебе уже писал об этом эксперименте: Например, итерация чертежа, размером 50Мб, с выборкой всех ObjectId и их группировкой по типам примитивов у меня заняло меньше секунды. а в #12 я тебе давал ссылку на то, что тебя так "вдохновило" аж в посте #65 (спустя четыре страницы).

Эта фраза свидетельствует о том, что я совсем в программировании не спец., и элементарно не ведал, что даже само считывание элементов может представлять проблему.
И до #60 пытался сконцентрировать внимание на основном вопросе темы.
Но в первую очередь о том, что хорошие идеи находят признание.

Запрашиваемый пример задачи выложен в #43. Сейчас он пока сузился до создания пересечений. Тестовые файлы: большой в #48 и меньший в #50.
Есть ли шанс получить в Автокаде скорость обработки, сравнимую с результатами zamtmn?
Пока что получены только отрицательные результаты обработки лисп-программой BreakObjects и фирменной Break Intersections от Autocad Map 3D - не могут они обработать больший файл вообще, а меньший наполовину.
От тех же, кто просил примеры задачи, результатов не поступило

[trir]

regular.dxf

SELECT t1.featid as f1, t2.featid as f2, astext(t1.geom), astext(t2.geom) FROM fdo_test.t1 as t1, fdo_test.t1 as t2 where t1.featid<>t2.featid and st_Intersects(t1.geom, t2.geom)=1

- 383 секунды, key_buffer_size = 104857600

[АлексЮстасу]

Сообщение от trir - 383 секунды, key_buffer_size = 209715200

Т.е. над оптимизацией придется поработать самим?

[zamtmn]

trir
>>key_buffer_size = 104857600
это координаты пересечений или порезаные линии?

[trir]

key_buffer_size - это размер индекса в памяти

[gomer]

Сообщение от АлексЮстасу От тех же, кто просил примеры задачи, результатов не поступило

http://forum.dwg.ru/showpost.php?p=1152361&postcount=89
В автокаде программа работала в течение часа

[zamtmn]

>>key_buffer_size - это размер индекса в памяти
это я понял. Только интдекс та чего?

[trir]

SPATIAL INDEX на геометрию, поле geom

[zamtmn]

Понятно, а какие нибудь подробности о типе индекса известны или "черный ящик"? Если распологаешь свободным временем, сделай пожалуйста тоже для nonregular и nonregular2 - очень интересует сравнение результатов для легко и трудноиндексируемых данных

[trir]

в документации написано, что это R-дерево
Времени сейчас нет, к сожалению...

[АлексЮстасу]

Сообщение от hwd Как видим в файле, объёмом 51Мб на то, чтобы в итерации перебрать 736 323 примитива, уходит 0,278 сек. А теперь разделите 0,278 на 736,323 и узнаете, за какое время просмотрено 1000 элементов: 0,000378 сек.

Есть ли у нас шанс увидеть цифры для создания пересечений с использованием этого способа?

[zamtmn]

trir
Переодически подумываю переделать бинарное дерево в R, но чето напрягает то что объемы могут пересекаться - неоднозначно както - будут трудности с быстрой перестройкой при изменении части чертежа. В бинарном все просто - примитив сдвинули, вышел за пределы объема - переношу его на уровень выше и так пока не окажется в объеме. Если какаято нода оказывается переполненной, то перестройка касается только ее и дочерние ноды. В R всё сложнее - всё перестраивать придется чаще чем бинарное.

АлексЮстасу
В продолжение темы. Я для наглядности чуток переделал процедуру постройки дерева, чтоб выудить побольше информации о структуре
Резльтаты для regular.dxf с пояснениями:

Код:

[Выделить все]

Running command:RebuildTree
Total entities: 20000
Max tree depth: 16
Max in node entities: 10
Create tree...
Rebuild drawing spatial:  0.07 second
Done
as a result: //по факту получилось:
Total entities: 20000 //всего примитивов
Total nodes: 3105 //всего нод
Total overflow nodes: 264 //всего "переполненных" нод, т.е. в которых больше 10 примитивов
Fact tree depth: 11 //глубина дерева по факту
by levels: //далее детализация по уровням вложенности
level 0 //уровень 0 - корневая нода
  Entities: 0//примитивов на уровне
  Entities(%): 0.00//тоже в процентах
  Nodes: 1//нод на уровне
  Overflow nodes: 0 //переполненных нод на уровне
level 1 //следующий уровень вложенности и т.д.
  Entities: 80
  Entities(%): 0.40
  Nodes: 2
  Overflow nodes: 2
level 2
  Entities: 199
  Entities(%): 1.00
  Nodes: 4
  Overflow nodes: 4
level 3
  Entities: 239
  Entities(%): 1.20
  Nodes: 8
  Overflow nodes: 8
level 4
  Entities: 496
  Entities(%): 2.48
  Nodes: 16
  Overflow nodes: 16
level 5
  Entities: 843
  Entities(%): 4.22
  Nodes: 32
  Overflow nodes: 32
level 6
  Entities: 917
  Entities(%): 4.59
  Nodes: 64
  Overflow nodes: 63
level 7
  Entities: 1570
  Entities(%): 7.85
  Nodes: 128
  Overflow nodes: 98
level 8
  Entities: 1866
  Entities(%): 9.33
  Nodes: 256
  Overflow nodes: 38
level 9
  Entities: 2612
  Entities(%): 13.06
  Nodes: 512
  Overflow nodes: 3
level 10
  Entities: 6310
  Entities(%): 31.55
  Nodes: 1024
  Overflow nodes: 0
level 11
  Entities: 4868
  Entities(%): 24.34
  Nodes: 1058
  Overflow nodes: 0

Резльтаты для nonregular.dxf:

Код:

[Выделить все]

Running command:RebuildTree
Total entities: 20000
Max tree depth: 16
Max in node entities: 500
Create tree...
Rebuild drawing spatial:  0.03 second
Done
as a result:
Total entities: 20000
Total nodes: 31
Total overflow nodes: 7
Fact tree depth: 4
by levels:
level 0
  Entities: 5134
  Entities(%): 25.67
  Nodes: 1
  Overflow nodes: 1
level 1
  Entities: 3675
  Entities(%): 18.38
  Nodes: 2
  Overflow nodes: 2
level 2
  Entities: 5105
  Entities(%): 25.52
  Nodes: 4
  Overflow nodes: 4
level 3
  Entities: 2689
  Entities(%): 13.44
  Nodes: 8
  Overflow nodes: 0
level 4
  Entities: 3397
  Entities(%): 16.99
  Nodes: 16
  Overflow nodes: 0

Собственно как оно и предпологалось в первом случае основная масса примитивов находится ближе к концу дерева, во втором почти всё в начале и все ноды переполнены.

[АлексЮстасу]

Сообщение от zamtmn Нода в моей реализации - ограничивающий объем+плоскость делящая ноду+ссылка на ноду "левее" плоскости+ссылка на ноду "правее" плоскости+список примитивов которые пересекаются плоскостью 1.На вход приходит срисок примитивов+уже посчитаный ограничивающий объем всех примитивов 2.создаем ноду 3.если (примитивов<примитивов в ноде)или(глубина дерева>максимальная глубина берева) то пишем все примитивы в список пересекающихся плоскостью, выходим возвращая созданную ноду 3.выбираем плоскость разбиения (тут я прибумывал всякие хитрые способы, но просто разбивать пополам перпендикулярно самой длинной оси ничють не хуже всяких хитростей) 4.список примитивов делим на 3 списка 1-левее плоскости, 2-правее плоскости, 3-пересекаются плоскостью 5. пишем список 3 в список пересекающихся плоскостью 6. ссылка на ноду "левее" плоскости=рекурсивный вызов п.1 со списком 1 и его ограничивающим объемом 7. ссылка на ноду "правее" плоскости=рекурсивный вызов п.1 со списком 2 и его ограничивающим объемом на выходе получается рекурсивное дерево ограничивающих объемов с перечнем примитивов в него попавших. разбиение продолжается пока не будет достигнута максимальная глубина или количество примитивов в ноде не будет меньше заданного

Интересно, сколько времени занимает получение списка примитивов?
И еще немного все-таки вопросов от малопосвещенного и неопытного:
1. Вхождение примитивов в объем или пересечение с режущими плоскостями рассматривается по всем вершинам примитивов или по их габаритам?
2. Как хранятся описания самих узлов (объемов)?
3. Один и тот же примитив может входить во множество объемов разного уровня?
4. В первом, верхнем узле хранятся все элементы?
5. На нижнем уровне каждый примитив входит только в один узел? (Пересекаемые плоскостями не в счет).
6. Пересекаемые плоскостями примитивы описываются только один раз - в том узле, в котором они первый раз были пересечены?

[zamtmn]

>>Интересно, сколько времени занимает получение списка примитивов?
Максимально быстрое, т.к. внутри программы имеется прямой доступ ко всем структурам данных по указателям (а не по идентификаторам как в примере hwd). в том числе к спискам примитивов и самим примитивам - это положительно сказывается на скорости, но требует аккуратности - чуть что не так - вылет
1. На этапе аостройки "дерева" работа осуществляется только с габаритами примитивов, что из себя представляет примитив - безразницы
2. AABB описаны в виде 2х точек - левая-нижняя-ближняя и правая-верхняя-дальняя - диагональные точки ограничивающего объема
3. Примитив может находится только в одной "ноде"
4. Нет только те объем которых пересекся плоскостью и соответсвенно их невышло "разбить двльше"
5. "Пересекаемые плоскостями не в счет" я неверно сразу выразился - пересекаемый - значит он остается в этой нооде. и соответственно "список пересекаемых" это и есть примитивы лежащие в этой ноде
6. да. см п.3 и п.5

update:
Сейчас глянул исходники, у меня там еще некоторые "оптимизации" присутствуют:
- точка по по которой объем рассекается полскостью - выбирается как центр габаритов всех примитивов
- проводится расчет для всех 3 возможных плоскостей и выбирается оптимальная - (меньше всего примитивов в ноде и примерно равное разбиение для списков "слева" и "справа")
На эти процедуры тратится значительное время (т.к. требуется перебор всех примитивов), а толку от них не много - разбиение почти не отличается от простого рассекания пополам длинной стороты объема
Если придумаете какойнить легкий способ выбора оптимальной плоскости - дайте знать

[АлексЮстасу]

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

[zamtmn]

Можно сразу пробежать всё с корня отбраковывая ноды которые не попадают в объем (p-l,p+l), в остальных перебирая примитивы

[АлексЮстасу]

В теме написано аж на пять страниц, а сухой остаток что-то жидковат
1. Узнали, что пространственные базы данных (не Автокад) используют оптимизацию. Даже узнали, что в каком-то случае это R-дерево. И получили рекомендацию использовать k-d tree.
2. Узнали, что можно очень эффективно оптимизировать считывание, просмотр огромного числа примитивов. С помощью .NET (реализовано), и, возможно, ARX (не испробовано).
3. Узнали, что в самодельном CAD, работающем с dxf-файлами, можно писать на Паскале чрезвычайно эффективные программы обработки данных. В том числе мы узнали подробности реализованного для этого CAD оригинального алгоритма оптимизации деревом собственной конструкции.
4. Узнали, что имеющиеся программы (создания пересечений) под Автокад могут вообще не обрабатывать тяжелые файлы.
Не узнали ни об одной реализации под Автокад оптимизации обработки геометрических отношений данных.
Не произошло обсуждения предложенных алгоритмов обработки геометрических отношений данных. Если не считать моих глупых вопросов и законного ответа zamtmn, что древовидные структуры - признанный метод оптимизации.
Итого: исходный вопрос об оптимизации обработки геометрических отношений элементов файлов в Автокаде фактически не обсуждался.

Все-таки что-нибудь скажете про мой алгоритм оптимизации регулярным разделением файла?

Сообщение от trir Книжки читать видимо не модно, то что вы изобретаете - называется k-d дерево

Мне кажется, что регулярное разбиение файла на ячейки - не дерево. Но включает и преимущества деревьев.

Сообщение от zamtmn Добавте в алгоритм пару пунктов: -Лучше ввести древовидную структуру данных, т.к. 1)еще больший профит за счет отбраковки всех дочерних "подпространств" путем отбраковки вышестоящего, 2) реальные а не подготовленные данные наврятли можно вписать в какую либо "сетку" - всегда будут примитивы которые будут всё портить - пересекать границы в которые хорошо вписываются другие примитивы, 3) удобно "ограничить" процесс построения такого дерева количеством примитивов в "листах" и глубиной вложенности -В случае наличия в данных "длинных" примитивов - например полилиний с большим кол-вом сегментов ваш алгоритм стоит применять и внутри примитивов (т.е. грубо говоря считать полилинию набором отрезков и дуг)

1. Регулярное разбиение - это фактически только определение шага, дельт по осям координат, на которые условно разбивается пространство. Индексом ячейки такого разбиения могут быть сами координаты x, y, z угла ячейки или некие номера ячеек.
2. Регулярное разбиение обладает возможностями дерева, т.к. в любой момент для любой точки можно рассматривать прямоугольник (объем) любой суммы смежных ячеек. Причем, поскольку все ячейки равноценны, в рассмотрение не попадет сильно избыточное число примитивов, как было бы в дереве, если нужный объем захватывает соседние "ветви".
3. Доступ к нужным площадям (объемам) при регулярном разбиении много проще - не нужно просматривать списки габаритов узлов (нод). Сам индекс ячейки указывает на определенную часть пространства.
Т.е. никакого "разбиения", определения, описания ячеек не производится - определяется только попадание габаритов примитивов в ячейки как проверка на > < координат, кратных размерам ячеек. Нет необходимости и хранить описания самих ячеек. Достаточно хранить только не пустые списки элементов ячеек в порядке возрастания индекса.
4. При этом, регулярное разбиение позволяет считать пространство разбиения бесконечным и в +, и в -. Если принять за начало 0,0,0, и допустить индексы не только положительные, но и отрицательные. Т.е. изменение габаритов файлов не требует перестроения разбиения в целом.
5. Регулярное разбиение безусловно - проверка идет только на пересечение габаритов примитивов с ячейкой, т.е. не тратится время на анализ и принятие решений о том, в какой узел что помещать, как элементы относятся к другим элементам. Т.е. задачи стараться "вписать" примитивы нет, и "другие примитивы" не будут ничего "портить". Главное - подобрать оптимальный размер ячеек разбиения.

Резервы:
1. Уже писал, что можно попробовать уточнять положение примитивов в ячейках за счет проверки попадания в них габаритов сегментов примитивов. Причем, делать это можно не сразу, не для всех примитивов, а по мере их обработки.
2. Можно попробовать хранить списки не только примитивов в ячейках, но и списки ячеек, в которые попадают примитивы. Возможно, что это еще упростило бы обработку. Т.е., рассматривая любой примитив, можно было бы сразу знать о других примитивах, находящихся в "его" ячейках. Причем, "его" ячейки в общем случае не образуют прямоугольник, т.е. не захватятся избыточные примитивы.

[trir]

Пурга, читай книжки ISBN: 978-5-8459-1744-7 (рус.)

Update:
1. Сложность поиска в списке O(n) - где n - количество элементов. Сложность поиска в дереве O(h) - где h - высота дерева. Смотри у zamtmn

Max tree depth: 16

Total entities: 20000

- Почувствуй разницу

[zamtmn]

Имхо регулярное разбиение имеет приемущество только для постоянно меняющихся данных (желательно специально подготовленных) за счет возможно более быстрого "построения", ито это нужно провеить экспериментально или почитать книжки
>>а сухой остаток что-то жидковат
Нифигасебе)) показано и как просто примитивы перебирать, и умные ссылки даны на всякие пространственные хитрости, и есть пример не очень умной реализации - всё разжевано, что еще надо то? Осталось только уволить програмиста и самому за реализацию взяться))
1 - это главный минус - размер ячейки фиксирован - мелкие детализованные учстки чертежа окажутся в 1-2-3-4 "ячейках". Т.е. повышение детализации фрагмента чертежа не вызывает повышение детализации сетки. В случае даже самого простого бинарного дерева разбиение автоматически повышает детализацию на насыщенных участках чертежа.
2 - достоинство дерева при отбраковке вышестоящей ноды автоматом отбраковываются все нижестоящие. т.е. если мы ткнули мимо чертежа, тест корневой ноды сразу нам об этом скажет, а в сетке что об этом скажет? перебор всех ячеек?
3 - этот момент полностью аналогичен и в дереве и в сетке, т.к. разбивка хочешь нехочешь строится в габаритах чертежа, а не в абсолютных координатах в "бесконечном" пространстве
4 - нет, иначе придется хранить бесконечное количество пустых ячеек, для сохранения доступа к ним по индексу, см. п.3
5 - непонял. имхо все также как и с деревом, идеально выбрать сетку не выйдет и будет куча примитивов которые сидят в куче ячеек

trir
>>Сложность поиска в списке O(n) - где n - количество элементов. Сложность поиска в дереве O(h) - где h - высота дерева. Смотри у zamtmn
Насколько я понимаю АлексЮстасу хочет сказать что в его сетке сложность будет O(1), но это действительно пурга, т.к. идеально разбить не подготовленные специально данные не получится.

[Дима_]

Сообщение от АлексЮстасу В теме написано аж на пять страниц, а сухой остаток что-то жидковат

А по моему все необходимое для реализации, есть уже на 1 странице, разжеванно до уровня птушника на 2 и представленна реализация на 3. Вы, наверное, ожидали к 5 странице готовый инсталятор? По моему Вы, на пару со своим программистом, уже должны zamtmn'у как земля колхозу, а Вам "остаток жидковат", да реализация неэффективна.

Все-таки что-нибудь скажете про мой алгоритм оптимизации регулярным разделением файла?

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

[АлексЮстасу]

Сообщение от trir Пурга, читай книжки ISBN: 978-5-8459-1744-7 (рус.)

Сообщение от Дима_ А по моему все необходимое для реализации, есть уже на 1 странице, разжеванно до уровня птушника на 2 и представленна реализация на 3. Вы, наверное, ожидали к 5 странице готовый инсталятор? По моему Вы, на пару со своим программистом, уже должны zamtmn'у как земля колхозу, а Вам "остаток жидковат", да реализация неэффективна.

Сообщение от zamtmn >>а сухой остаток что-то жидковат Нифигасебе)) показано и как просто примитивы перебирать, и умные ссылки даны на всякие пространственные хитрости, и есть пример не очень умной реализации - всё разжевано, что еще надо то? Осталось только уволить програмиста и самому за реализацию взяться))

Посоветованные книги, упомянутые алгоритмы, общие идеи, реализация zamtmn - это очень здорово. За все это однозначное, не из вежливости, спасибо!
Но совершенно непонятно, что из этого практически применимо, эффективно для специфики Автокада, при программировании под Автокад, для нашего вида данных? Какой из видов деревьев для автокадовских данных эффективнее, в каких случаях, какие из деревьев, как лучше реализовать на том-другом языке, какой это может дать, дало реальный результат?
zamtmn, результаты Вашей оптимизации впечатляют, бьют наповал, но что из этого выйдет в Автокаде? Впечатляет фантастическая скорость просмотра примитивов hwd, но неясно, как это помогает анализу геометрических отношений примитивов?
Кроме этих двух реальных, реализованных примеров (не в Автокаде, не для анализа геометрии), получается, ничего не абстрактно-теоретичекого нет или великая тайна.
Ну, значит, так.

[Дима_]

Сообщение от АлексЮстасу (не в Автокаде, не для анализа геометрии), получается, ничего не абстрактно-теоретичекого

Вы уверены, что понимаете о чем Вам пишут, а где и для чего по Вашему?? Если Вам этого мало - то просто не пытайтесь этим заниматься - это, так сказать, не Ваше...

[zamtmn]

>>но что из этого выйдет в Автокаде?
Должно получиться гораздо лучше

[АлексЮстасу]

Сообщение от trir regular.dxf - 383 секунды, key_buffer_size = 104857600

regular.dxf я до сих пор не проверял:
- Autocad Map 3D - Drawing cleanup - Break intersections сделало на средней машине за примерно 3.5 секунды!
- Лисп BreakObjects - на двадцатой, примерно, минуте я остановил процесс.
Получается, что Autocad Map 3D для своих действий оптимизацию очень даже применяет.

И про FlashPolygons от Delicad - сделал из всех пересечений элементов в меньшем nonregular2.dxf полигоны за 30 секунд.

Выберите объекты: Противоположный угол: найдено: 1172 Выберите объекты: >> Processing, please wait ... >> 20896 Internal polylines created in layer 'internal_polylines' >> 7 External polylines created in layer 'external_polylines' >> 0 Polylines with area under 0.000 ignored.

Похоже, что при создании пересечений есть еще одна задача для оптимизации - число получаемых при пересечениях примитивов оч. большое, миллионы. В nonregular.dxf пересечений, наверное, по 200 на линию.Вероятно, Drawing cleanup и лисп BreakObjects на создании этих миллионов примитивов и зависают.
Как бы сделать создание новых примитивов из пересечений, чтобы и ресурсов хватало, и скорость была высокой? Общие подходы можете посоветовать?

[zamtmn]

>>Общие подходы можете посоветовать?
x86_64, максимум ОЗУ, толстый свап

[Boxa]

Сообщение от АлексЮстасу Общие подходы можете посоветовать?

1. Не сравнивать производительность компилируемых и скриптовых ЯП
2. Использовать компилируемые ЯП

[Мансур]

Извиняюсь, что встреваю в мудрые разговоры.
Раз дело касается AutoCAD, то и используйте его возможности.
Как, например, здесь: объединение большого количества отрезков.
Волшебная функция (ssget "_C" p1 p2) наверняка уже тыщу раз оптимизирована разработчиками, берите и используйте - тогда даже на обыкновенном autolisp все шустро просчитывается. Если непонятно: берете примитив, получаете его bounding box, по ним ssget - получаете (обычно) небольшой набор, по нему уже тупо перебором проверили реальные пересечения. И не надо никакой мороки со всякими индексами, ибо индексы уже есть в самом автокаде.

[bargool]

Сообщение от Мансур ssget

Поправьте меня, если я ошибаюсь: эта волшебная функция требует, что бы данный прямоугольник был на экране. Т.е. либо скакать по всему чертежу, либо масштабировать, что бы весь чертёж сразу был на экране.
При самостоятельной обработке я могу работать даже без открытия чертежа (открывая только базу данных), что гораздо быстрее при пакетной обработке, скажем.
Да и в целях тестируемости лучше изолировать код, работающий непосредственно с автокадом как можно дальше (т.е. выделить зависимости от автокада в как можно меньшее кол-во классов, и только изредка их использовать)
Так что оба метода имеют право на жизнь, у каждого своё предназначение.
Аналог ssget в .net данном случае будет метод Editor.SelectCrossingPolygon

[Мансур]

Сообщение от bargool Поправьте меня, если я ошибаюсь: эта волшебная функция требует, что бы данный прямоугольник был на экране. Т.е. либо скакать по всему чертежу, либо масштабировать, что бы весь чертёж сразу был на экране.

Да, именно так. Скакать по чертежу имхо не стоит, можно принудительно делать "zoom extents".
Абсолютно согласен, каждый подход имеет свое предназначение. Просто про вариант с ssget мало кто задумывается, а в большинстве случаев надо "не шашечки, а ехать". Да и объем кода получается на порядок меньше, проще сопровождать потом, в случае надобности.

[Дима_]

ssget действительно хорошо оптимизированна но работать общая программа будет медленно - т.к. между вызовами ей все равно все по новой пересчитывать.

[Мансур]

Сообщение от Дима_ ssget действительно хорошо оптимизированна но работать общая программа будет медленно - т.к. между вызовами ей все равно все по новой пересчитывать.

Или я чего-то недопонял, или...
С чего программе работать медленно? Возьмем цифры с потолка - пусть в чертеже 10000 объектов. Если устроить тупой перебор: каждая линия с остальными, можете сами посчитать количество сочетаний (если не ошибаюсь, это будет 10000*9999/2= 49 995 000). А если пользуемся ssget (опять же условно возьмем, что в среднем ssget вернул 10 объектов для каждой анализируемой линии), то количество сочетаний 10000*10 = 100 000. Есть разница между 50 миллионами итераций и сотней тысяч? У меня чертеж с 20 000 объектов обрабатывается в лиспе за пару десятков секунд.

[Дима_]

Сообщение от Мансур А если пользуемся ssget (опять же условно возьмем, что в среднем ssget вернул 10 объектов для каждой анализируемой линии)

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

Сообщение от Мансур У меня чертеж с 20 000 объектов обрабатывается в лиспе за пару десятков секунд.

а 40 тысяч за сколько он обработает - линейная зависимость??

[zamtmn]

>>Ведь для создания двревовидной структуры нужно время и для эффективного выполнения она создается 1 раз - а ssget'у не известно проходили-ли изменения чертежа между вызовами или нет.
Думаю в автокаде оная структура поддерживается в актуальном состоянии всегда. т.к. она важна не только для поиска чегонибудь, а практически для всех операций с чертежем.

но ssget даже в реализации на компилируемом языке всеравно проиграет поиску с прямым доступом к "дереву" - т.к. он вынужден всегда начинать поиск с корня. также свое дерево заглаза себя оправдает для операций не на всем чертеже, а только над частью примитивов - дерево нужно будет строить только для них - операции с ним будут быстрее и сбалансированность лучше

[Дима_]

Сообщение от zamtmn Думаю в автокаде оная структура поддерживается в актуальном состоянии всегда. т.к. она важна не только для поиска чегонибудь, а практически для всех операций с чертежем.

Ну вряд-ли бы "прятали" соответствующее апи - как минимум на уровне ARX.
Offtop: В этой строке немой намек вопрос главному по ARX А.Ривилису.

[zamtmn]

>>Ну вряд-ли бы "прятали" соответствующее апи - как минимум на уровне ARX.
Чудес не бывает, без "дерева" автокад бы ползал. Даже если в arx этого нет (хотя имхо и недолжно быть) много других "следов"

[Мансур]

Сообщение от Дима_ а 40 тысяч за сколько он обработает - линейная зависимость??

Код:

[Выделить все]

Команда: DATE
Fri 2013/9/27 20:20:16.621

Команда:
Команда: MTMDJOIN

Выберите объекты: Противоположный угол: найдено: 42921

Выберите объекты:

Допустимое отклонение <0.2>:
3666 polylines generated, 23978 lines joined

Команда:
Команда: DATE
Fri 2013/9/27 20:22:01.750

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

[zamtmn]

Мансур
>>тем не менее скорость более чем приемлемая
для лиспа очень даже.
Пожалуйста прогоните через "объеденялку" файл из #57 ,будут теже 2 митуты? мне интересно для статистики.

[АлексЮстасу]

Сообщение от Мансур Волшебная функция (ssget "_C" p1 p2) наверняка уже тыщу раз оптимизирована разработчиками, берите и используйте - тогда даже на обыкновенном autolisp все шустро просчитывается. Если непонятно: берете примитив, получаете его bounding box, по ним ssget - получаете (обычно) небольшой набор, по нему уже тупо перебором проверили реальные пересечения.

Для непосвещенных.
Эта ssget выдает набор чего? Примитивов, пересекающих указанный? Примитивов, попадающих в габарит указанного примитива? Или еще что-то?
Эта ssget чисто лисповская или у нее есть аналоги в ARX?

[Александр Ривилис]

Сообщение от Дима_ Ну вряд-ли бы "прятали" соответствующее апи - как минимум на уровне ARX.

Так вроде никуда и не прячут. AcGi/AcGs классы. Вообще-то ssget (acedSSGet в ObjectARX), кроме варианта с опцией "_X" работает с проекцией примитивов на плоскость. На виртуальный экран.

[Дима_]

Я не про то, что там есть аналог ssget - может из ARX можно разглядеть структуру которую использует эта функция (то есть определяет простым перебором по БД, либо она таки использует пространственное индексирование - на основе например R-tree)?

[Александр Ривилис]

Алгоритм конечно не виден. Но точно не простой перебор по БД, т.к. эта функция вообще с БД (AcDbDatabase) не работает, а работает с виртуальным экраном, т.е. с проекциями примитивов. Но этот подход имеет свой минус - примитивы должны быть видны и различимы.

[zamtmn]

>>а работает с виртуальным экраном
т.е. acedSSGet не выберет например сплайн если в область выбора попадает "математически правильный" фрагмент кривой но не попадает его кусочно-линейная апроксимация?

[Александр Ривилис]

Сообщение от zamtmn т.е. acedSSGet не выберет например сплайн если в область выбора попадает "математически правильный" фрагмент кривой но не попадает его кусочно-линейная апроксимация?

Да. Во всяком случае так было в те времена, когда я это проверял. Возможно что-то изменилось в последних трёх-четырёх версиях, но я сомневаюсь.

[zamtmn]

Собственно ничего не мешает автокаду строить "деревъя" не над базой данных, а над хозяйством полученым после worldDraw (или что там для "отрисовки") всех примитивов, так даже проще на уровне примитивов - все сложности уходят в дпугой "слой" программы. Однако теже привязки считаются не над "проекциями" примитивов - иначе они бы сильно врали

[Кулик Алексей aka kpblc]

Сообщение от zamtmn Однако теже привязки считаются не над "проекциями" примитивов - иначе они бы сильно врали

Не совсем так.

[zamtmn]

>>Не совсем так.
В смысле? насколко помню из своих экспериментов например пересечение сплайнов это действительно пересечение сплайнов с точностью заданной в примитивах, а не пересечение линий их апроксимирующих

[АлексЮстасу]

Сообщение от trir Пурга. Сложность поиска в списке O(n) - где n - количество элементов. Сложность поиска в дереве O(h) - где h - высота дерева.

Вы не поняли моего предложения. Предлагается не список примитивов, а списки примитивов, попадающих в ячейки сетки. Массив списков примитивов по ячейкам.

Сообщение от zamtmn Насколько я понимаю АлексЮстасу хочет сказать что в его сетке сложность будет O(1), но это действительно пурга, т.к. идеально разбить не подготовленные специально данные не получится.

Сообщение от Дима_ Ваш "алгоритм" будет эффективен только на специально приготовленных для него чертежах.

Вы говорите о необходимости подготовке данных, наверное, исходя из посылки, что один примитив необходимо описывать в одной единице объема. Да, один примитив при регулярном разбиении в общем случае окажется в нескольких ячейках, и ничего не нужно подготавливать. Но ничего страшного в этом нет - по вершинам примитива, по его габариту, просто просмотром соседних ячеек находятся все нужные ячейки. Да, это издержка метода. Но, возможно, единственная.
Общее соображение: т.к. в общем случае примитивы равнозначны, то привязывать сведения о положении в пространстве примитивов к разным уровням дерева некорректно. Естественно определять их на одном, нижнем уровне. А на уровнях выше, соответственно, определять сведения о положении уже их множеств. Точнее - подпространств, из которых состоит пространство файла.
При регулярном разбиении пространства файла есть преимущества. Оно представляет весь файл в виде матрицы или в виде как бы "растра"- кому какой образ больше говорит. На построение и сохранение собственно дерева время тратить не нужно. Но по регулярным ячейкам можно использовать любой подходящий для конкретной задачи алгоритм поиска, в том числе и дерево. Разделяя все множество ячеек (все пространство) на любые подходящие их подмножества: делением на две части, на четыре, сразу на 16, на нужное число уровней и т.п. Т.е. регулярное разбиение уже содержит все возможности дерева, уже есть дерево, причем, допущу, любого типа.
Или, при анализе "снизу", можно брать смежные ячейки в нужном количестве. И не обязательно прямоугольниками, но и в наборе произвольной формы.
При этом, взаимное положение любых ячеек априори известно без всякого дополнительного структурирования, без обращения к возможностям дерева.
Сам оценить O() регулярного разбиения не возьмусь.

[zamtmn]

>>При регулярном разбиении пространства файла есть преимущества. Оно представляет весь файл в виде матрицы или в виде как бы "растра"- кому какой образ больше говорит
Возмите regular.dxf и сдвинте 1 "крестик" коданибудь в сторону например на 10000000 едениц чертежа - все "приемущества" регулярного разбиения на этом сразу закончатся, древовидная структура проглотит это незаметив, просто увеличив глубину на еденицу и сохранив тоже качество разбивки

[bargool]

АлексЮстасу, я не очень вникал в ваш алгоритм, но если претит R-Tree, или другие предложенные варианты, может будет более понятно quadtree
Но мне лично кажется, что для работы с объектами произвольных размеров (не точками), лучше работать с помощью R-Tree, хотя может я и ошибаюсь, quadtree я не пробовал

[АлексЮстасу]

Сообщение от zamtmn сдвинте 1 "крестик" коданибудь в сторону например на 10000000 едениц чертежа - все "приемущества" регулярного разбиения на этом сразу закончатся

В чем именно при таком сдвиге проблема для регулярного разбиения?

Сообщение от bargool я не очень вникал в ваш алгоритм, но если претит R-Tree, или другие предложенные варианты, может будет более понятно quadtree Но мне лично кажется, что для работы с объектами произвольных размеров (не точками), лучше работать с помощью R-Tree, хотя может я и ошибаюсь, quadtree я не пробовал

И совсем не против деревьев, и ни одно из них мне не претит. Да и регулярное разбиение содержит в себе возможности деревьев.
Пытаюсь разобраться, какое или как лучше. Не в последнюю очередь - практически. Ведь из названных в теме вариантов пока нет под Автокад ни одного реализованного.

[zamtmn]

>>В чем именно при таком сдвиге проблема для регулярного разбиения?
ээх, сколько можно об одном и томже)) В этом случае может быть 2 варианта реализации:
1 - ячейки в линейном "массиве" с быстрым доступом по индексу (как вы и предлагаете насколько я понял), но 99.99999% "ячеек" пустые и занимают всю доступную память - расход памяти зависит от геометрических размеров модели, а не от ее наполнения.
2 - храним только "заполненные" ячейки - доступ к ним не по индексу, а "перебором" с поиском нужной. И тут, ВНИМАНИЕ, для ускорения поиска в этой структуре придется вводить бинарное дерево.

>>Ведь из названных в теме вариантов пока нет под Автокад ни одного реализованного
Давайте уже делайте и выкладывайте))

[Мансур]

Сообщение от zamtmn Мансур >>тем не менее скорость более чем приемлемая для лиспа очень даже. Пожалуйста прогоните через "объеденялку" файл из #57 ,будут теже 2 митуты? мне интересно для статистики.

Команда: MTMDJOIN
Выберите объекты: Противоположный угол: найдено: 45306
Допустимое отклонение <0.2>: 1235 polylines generated, 43776 lines joined
Выполнено за 21.013 сек.
Что сырой лисп, что компилированный - время примерно одно - 20-21 сек на моей машине.
UPD: только что проверил на свежескачанной бете BricsCAD 14 x64 - на глаз скорость чуть ли не в два раза выше, чем AutoCAD. Где-то читал, что Бриксис очень хорошо оптимизировал свой лисп-движок

[АлексЮстасу]

Сообщение от zamtmn Давайте уже делайте и выкладывайте))

Первые результаты на неплохой машине 64-разрядной, 16 Гб памяти:
regular.dwg

Элементов для обработки: 20000 Построение сетки: 0.06 сек. Размер сетки: 64x64 Поиск пересечений: 0.02 сек. Пересечений: 9003 Создание объектов: 2.19 сек.

Это, кстати, раза в 1.5-2 лучше, чем у Autocad Map 3D, Drawing cleanup.
nonregular2.dwg

Элементов для обработки: 1172 Построение сетки: 0.03 сек. Размер сетки: 64x64 Поиск пересечений: 0.01 сек. Пересечений: 23856 Создание объектов: 2.20 сек.

nonregular.dwg

Элементов для обработки: 20000 Построение сетки: 143.7 сек. Размер сетки: 64x64 Поиск пересечений: 6.07 сек.

И результата для nonregular.dwg я за 1.5 часа не дождался - все ресурсы компьютера были съедены созданием 10 с гаком миллионов новых примитивов.
Взял regular.dwg, и перенес один крест на 10000000 в сторону:

Построение сетки: 9.43 сек. Размер сетки: 64x64 Поиск пересечений: 0.34 сек. Пересечений: 8020 Создание объектов: 1.99 сек.

Т.е. в сумме почти 12 секунд.
Это первый блин, который только сегодня мне, наконец, выложили.
Как видите, "сетка" пока всегда одинаковая - 64x64.
И что за "сетка", как что куда записывается, создается ли параллельно дерево и т.п. - пока не спрашивайте. Даже не спрашивайте, сетка ли там на самом деле или баобаб. Поскольку и наш программист тоже разговаривает на другом языке
Надеюсь, мы "сетку" еще оптимизируем. Тогда главная будет проблема - требуются гигантские ресурсы на создание новых элементов, т.е. на разбиение на пересечениях?

[zamtmn]

Поздравляю с первым блином)) не совсем понял толко почему время создания так отличается на исходном и сдвинутом regular - сетка то там и там одинаковая - видимо реализация очень "наколенная". Также неясно с колвом пересечений - в регуляр их 10000 точно, в нонрегуляр2 - 22067 и нонрегуляр - 11559108 по моим результатам
Неплохо было бы приводить результаты для сетки 1х1 - чтоб было наглядно видно ускорение от повышения разрешения "сетки"

>>требуются гигантские ресурсы на создание новых элементов
требуется создание ~23 миллионов примитивов, помоему невыполнимая задача без промежуточных сохранений результатов. Да и нужно оно толко для "теста" - в реалной жизни такого не попадется.
Имхо зря вы так схватились за сетку - это интересно только как "эксперимент", с практической точки зрения закончится тупиком - причины выше описаны

[zamtmn]

Попал в руки ноут с i7 16Гб озу и 32Гб свапа.
nonregular.dxf таки был порезан, но с получеными на выходе миллионами линий графический движек зкада не совладал и впал в большую тоску(( поэтому цитата с лога, а не с вывода командной строки

Код:

[Выделить все]

!!!! 23:40:28  HISTORY: Запущена команда:FindAllIntersections---- t:=10:17.849, dt:=10:17.849 tick:=739738009, dtick:=739738009
!!!! 23:40:40  HISTORY: Search intersections and storing data:  14.49 секунд t:=10:30.367, dt:=10:30.367 tick:=754725139, dtick:=754725139
!!!! 23:40:52  HISTORY: Placing points:  14.04 секунд--------------------- t:=10:42.497, dt:=10:42.497 tick:=769247721, dtick:=769247721
!!!! 23:48:09  HISTORY: Cutting lines:  505.55 секунд--------------------- t:=17:59.329, dt:=17:59.329 tick:=1292258916, dtick:=1292258916
!!!! 23:48:09  HISTORY: Lines modified: 20000----------------------------------- t:=17:59.331, dt:=17:59.331 tick:=1292261051, dtick:=1292261051
!!!! 23:48:09  HISTORY: Lines created: 23118220--------------------------------- t:=17:59.331, dt:=17:59.331 tick:=1292261241, dtick:=1292261241
!!!! 23:48:10  HISTORY: Freeing memory:  0.47 секунд---------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744068, dtick:=1292744068
!!!! 23:48:10  HISTORY: Line-AABB tests count: 601354--------------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744348, dtick:=1292744348
!!!! 23:48:10  HISTORY: Line-Line tests count: 86247095------------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744502, dtick:=1292744502
!!!! 23:48:10  HISTORY: Intersections count: 11559110--------------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744652, dtick:=1292744652

всё тоже самое, только обрамлено дополнительной информацией - t и tick - отладочная информация о времени и тиках процессора, ее можно не глядеть. 14.5 сек поиск пересечений, 14 сек расстановка точек, 506 сек подрезка линий. в процессе работы было съедено всё озу и 50% свапа, по окончании перед повисанием на отображении полученое месиво из линий весило 9Гб в ОЗУ.

update:
откудато набежало 2 "лишних" пересечения, вроде ничего серъезного не менял((. и со времнем внутри программы и фиксации в логе чтото нето((

[zamtmn]

Расчехлю лопату.
Переделал статистику по разбиению пространства и приделал визуализацию. может кому будет интересно.

regular.dwg

Запущена команда: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): 18415 Total nodes: 127 Total overflow nodes: 0 Fact tree depth: 6 By levels: level 0 Entities: 0 Entities(%)[summary]: 0.00[0.00] Nodes: 1 Overflow nodes: 0 level 1 Entities: 80 Entities(%)[summary]: 0.40[0.40] Nodes: 2 Overflow nodes: 0 level 2 Entities: 199 Entities(%)[summary]: 1.00[1.40] Nodes: 4 Overflow nodes: 0 level 3 Entities: 239 Entities(%)[summary]: 1.20[2.59] Nodes: 8 Overflow nodes: 0 level 4 Entities: 495 Entities(%)[summary]: 2.47[5.07] Nodes: 16 Overflow nodes: 0 level 5 Entities: 795 Entities(%)[summary]: 3.97[9.04] Nodes: 32 Overflow nodes: 0 level 6 Entities: 18192 Entities(%)[summary]: 90.96[100.00] Nodes: 64 Overflow nodes: 0 Nodes with population 0: 1 Nodes with population 24: 18 Nodes with population 25: 26 Nodes with population 26: 1 Nodes with population 27: 1 Nodes with population 28: 2 Nodes with population 32: 1 Nodes with population 33: 1 Nodes with population 37: 1 Nodes with population 38: 1 Nodes with population 40: 2 Nodes with population 49: 3 Nodes with population 50: 5 Nodes with population 244: 1 Nodes with population 245: 1 Nodes with population 247: 1 Nodes with population 248: 1 Nodes with population 249: 1 Nodes with population 252: 1 Nodes with population 254: 1 Nodes with population 256: 1 Nodes with population 260: 1 Nodes with population 262: 1 Nodes with population 264: 1 Nodes with population 269: 6 Nodes with population 270: 5 Nodes with population 271: 2 Nodes with population 272: 4 Nodes with population 273: 1 Nodes with population 280: 1 Nodes with population 281: 1 Nodes with population 288: 2 Nodes with population 291: 3 Nodes with population 292: 1 Nodes with population 293: 2 Nodes with population 294: 4 Nodes with population 296: 2 Nodes with population 297: 3 Nodes with population 298: 2 Nodes with population 300: 3 Nodes with population 308: 1 Nodes with population 318: 3 Nodes with population 319: 3 Nodes with population 320: 2 Nodes with population 321: 2

nonregular.dwg

Запущена команда: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

nonregular2.dwg

Запущена команда:TreeStat Total entities in drawing: 1172 Max tree depth: 16 Max in node entities: 500 Current drawing spatial index Info: Total entities: 1172 Memory usage (bytes): 1015 Total nodes: 7 Total overflow nodes: 0 Fact tree depth: 2 By levels: level 0 Entities: 27 Entities(%)[summary]: 2.30[2.30] Nodes: 1 Overflow nodes: 0 level 1 Entities: 109 Entities(%)[summary]: 9.30[11.60] Nodes: 2 Overflow nodes: 0 level 2 Entities: 1036 Entities(%)[summary]: 88.40[100.00] Nodes: 4 Overflow nodes: 0 Nodes with population 27: 1 Nodes with population 40: 1 Nodes with population 69: 1 Nodes with population 243: 1 Nodes with population 246: 1 Nodes with population 271: 1 Nodes with population 276: 1

Картинки с разбиением прилагаю. regular.png на форум не влез, лежит тут https://imgur.com/a/YQ569