|
||
| Правила | Регистрация | Пользователи | Сообщения за день | | Поиск | | Справка по форуму | Файлообменник | |
|
Поиск в этой теме |
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Понятно, а какие нибудь подробности о типе индекса известны или "черный ящик"? Если распологаешь свободным временем, сделай пожалуйста тоже для nonregular и nonregular2 - очень интересует сравнение результатов для легко и трудноиндексируемых данных
|
|||
|
||||
Регистрация: 18.12.2010
Сообщений: 5,057
|
|
|||
|
||||
Есть ли у нас шанс увидеть цифры для создания пересечений с использованием этого способа?
|
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
trir
Переодически подумываю переделать бинарное дерево в R, но чето напрягает то что объемы могут пересекаться - неоднозначно както - будут трудности с быстрой перестройкой при изменении части чертежа. В бинарном все просто - примитив сдвинули, вышел за пределы объема - переношу его на уровень выше и так пока не окажется в объеме. Если какаято нода оказывается переполненной, то перестройка касается только ее и дочерние ноды. В R всё сложнее - всё перестраивать придется чаще чем бинарное. АлексЮстасу В продолжение темы. Я для наглядности чуток переделал процедуру постройки дерева, чтоб выудить побольше информации о структуре Резльтаты для regular.dxf с пояснениями: Код:
Код:
|
|||
|
||||
Цитата:
И еще немного все-таки вопросов от малопосвещенного и неопытного: 1. Вхождение примитивов в объем или пересечение с режущими плоскостями рассматривается по всем вершинам примитивов или по их габаритам? 2. Как хранятся описания самих узлов (объемов)? 3. Один и тот же примитив может входить во множество объемов разного уровня? 4. В первом, верхнем узле хранятся все элементы? 5. На нижнем уровне каждый примитив входит только в один узел? (Пересекаемые плоскостями не в счет). 6. Пересекаемые плоскостями примитивы описываются только один раз - в том узле, в котором они первый раз были пересечены? |
||||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
>>Интересно, сколько времени занимает получение списка примитивов?
Максимально быстрое, т.к. внутри программы имеется прямой доступ ко всем структурам данных по указателям (а не по идентификаторам как в примере hwd). в том числе к спискам примитивов и самим примитивам - это положительно сказывается на скорости, но требует аккуратности - чуть что не так - вылет 1. На этапе аостройки "дерева" работа осуществляется только с габаритами примитивов, что из себя представляет примитив - безразницы 2. AABB описаны в виде 2х точек - левая-нижняя-ближняя и правая-верхняя-дальняя - диагональные точки ограничивающего объема 3. Примитив может находится только в одной "ноде" 4. Нет только те объем которых пересекся плоскостью и соответсвенно их невышло "разбить двльше" 5. "Пересекаемые плоскостями не в счет" я неверно сразу выразился - пересекаемый - значит он остается в этой нооде. и соответственно "список пересекаемых" это и есть примитивы лежащие в этой ноде 6. да. см п.3 и п.5 update: Сейчас глянул исходники, у меня там еще некоторые "оптимизации" присутствуют: - точка по по которой объем рассекается полскостью - выбирается как центр габаритов всех примитивов - проводится расчет для всех 3 возможных плоскостей и выбирается оптимальная - (меньше всего примитивов в ноде и примерно равное разбиение для списков "слева" и "справа") На эти процедуры тратится значительное время (т.к. требуется перебор всех примитивов), а толку от них не много - разбиение почти не отличается от простого рассекания пополам длинной стороты объема Если придумаете какойнить легкий способ выбора оптимальной плоскости - дайте знать Последний раз редактировалось zamtmn, 22.09.2013 в 21:04. |
|||
|
||||
Т.е., чтобы найти все ближайшие примитивы рядом с какой-нибудь точкой, нужно найти соответствующий узел (или узлы) нижнего уровня, примитивы в нем, а потом все примитивы, пересеченные плоскостями всех соответствующих старших узлов?
|
||||
|
||||
В теме написано аж на пять страниц, а сухой остаток что-то жидковат
1. Узнали, что пространственные базы данных (не Автокад) используют оптимизацию. Даже узнали, что в каком-то случае это R-дерево. И получили рекомендацию использовать k-d tree. 2. Узнали, что можно очень эффективно оптимизировать считывание, просмотр огромного числа примитивов. С помощью .NET (реализовано), и, возможно, ARX (не испробовано). 3. Узнали, что в самодельном CAD, работающем с dxf-файлами, можно писать на Паскале чрезвычайно эффективные программы обработки данных. В том числе мы узнали подробности реализованного для этого CAD оригинального алгоритма оптимизации деревом собственной конструкции. 4. Узнали, что имеющиеся программы (создания пересечений) под Автокад могут вообще не обрабатывать тяжелые файлы. Не узнали ни об одной реализации под Автокад оптимизации обработки геометрических отношений данных. Не произошло обсуждения предложенных алгоритмов обработки геометрических отношений данных. Если не считать моих глупых вопросов и законного ответа zamtmn, что древовидные структуры - признанный метод оптимизации. Итого: исходный вопрос об оптимизации обработки геометрических отношений элементов файлов в Автокаде фактически не обсуждался. Все-таки что-нибудь скажете про мой алгоритм оптимизации регулярным разделением файла? Цитата:
Цитата:
2. Регулярное разбиение обладает возможностями дерева, т.к. в любой момент для любой точки можно рассматривать прямоугольник (объем) любой суммы смежных ячеек. Причем, поскольку все ячейки равноценны, в рассмотрение не попадет сильно избыточное число примитивов, как было бы в дереве, если нужный объем захватывает соседние "ветви". 3. Доступ к нужным площадям (объемам) при регулярном разбиении много проще - не нужно просматривать списки габаритов узлов (нод). Сам индекс ячейки указывает на определенную часть пространства. Т.е. никакого "разбиения", определения, описания ячеек не производится - определяется только попадание габаритов примитивов в ячейки как проверка на > < координат, кратных размерам ячеек. Нет необходимости и хранить описания самих ячеек. Достаточно хранить только не пустые списки элементов ячеек в порядке возрастания индекса. 4. При этом, регулярное разбиение позволяет считать пространство разбиения бесконечным и в +, и в -. Если принять за начало 0,0,0, и допустить индексы не только положительные, но и отрицательные. Т.е. изменение габаритов файлов не требует перестроения разбиения в целом. 5. Регулярное разбиение безусловно - проверка идет только на пересечение габаритов примитивов с ячейкой, т.е. не тратится время на анализ и принятие решений о том, в какой узел что помещать, как элементы относятся к другим элементам. Т.е. задачи стараться "вписать" примитивы нет, и "другие примитивы" не будут ничего "портить". Главное - подобрать оптимальный размер ячеек разбиения. Резервы: 1. Уже писал, что можно попробовать уточнять положение примитивов в ячейках за счет проверки попадания в них габаритов сегментов примитивов. Причем, делать это можно не сразу, не для всех примитивов, а по мере их обработки. 2. Можно попробовать хранить списки не только примитивов в ячейках, но и списки ячеек, в которые попадают примитивы. Возможно, что это еще упростило бы обработку. Т.е., рассматривая любой примитив, можно было бы сразу знать о других примитивах, находящихся в "его" ячейках. Причем, "его" ячейки в общем случае не образуют прямоугольник, т.е. не захватятся избыточные примитивы. |
||||
|
||||
Регистрация: 18.12.2010
Сообщений: 5,057
|
Пурга, читай книжки ISBN: 978-5-8459-1744-7 (рус.)
Update: 1. Сложность поиска в списке O(n) - где n - количество элементов. Сложность поиска в дереве O(h) - где h - высота дерева. Смотри у zamtmn Цитата:
Цитата:
Последний раз редактировалось trir, 23.09.2013 в 21:52. |
|||
|
||||
КИПиА Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
|
Имхо регулярное разбиение имеет приемущество только для постоянно меняющихся данных (желательно специально подготовленных) за счет возможно более быстрого "построения", ито это нужно провеить экспериментально или почитать книжки
>>а сухой остаток что-то жидковат Нифигасебе)) показано и как просто примитивы перебирать, и умные ссылки даны на всякие пространственные хитрости, и есть пример не очень умной реализации - всё разжевано, что еще надо то? Осталось только уволить програмиста и самому за реализацию взяться)) 1 - это главный минус - размер ячейки фиксирован - мелкие детализованные учстки чертежа окажутся в 1-2-3-4 "ячейках". Т.е. повышение детализации фрагмента чертежа не вызывает повышение детализации сетки. В случае даже самого простого бинарного дерева разбиение автоматически повышает детализацию на насыщенных участках чертежа. 2 - достоинство дерева при отбраковке вышестоящей ноды автоматом отбраковываются все нижестоящие. т.е. если мы ткнули мимо чертежа, тест корневой ноды сразу нам об этом скажет, а в сетке что об этом скажет? перебор всех ячеек? 3 - этот момент полностью аналогичен и в дереве и в сетке, т.к. разбивка хочешь нехочешь строится в габаритах чертежа, а не в абсолютных координатах в "бесконечном" пространстве 4 - нет, иначе придется хранить бесконечное количество пустых ячеек, для сохранения доступа к ним по индексу, см. п.3 5 - непонял. имхо все также как и с деревом, идеально выбрать сетку не выйдет и будет куча примитивов которые сидят в куче ячеек trir >>Сложность поиска в списке O(n) - где n - количество элементов. Сложность поиска в дереве O(h) - где h - высота дерева. Смотри у zamtmn Насколько я понимаю АлексЮстасу хочет сказать что в его сетке сложность будет O(1), но это действительно пурга, т.к. идеально разбить не подготовленные специально данные не получится. Последний раз редактировалось zamtmn, 23.09.2013 в 22:40. |
|||
|
||||
Продуман Регистрация: 22.02.2007
Питер
Сообщений: 2,840
|
Цитата:
Цитата:
__________________
Когда в руках молоток все вокруг кажется гвоздями. |
|||
|
||||
Цитата:
Цитата:
Но совершенно непонятно, что из этого практически применимо, эффективно для специфики Автокада, при программировании под Автокад, для нашего вида данных? Какой из видов деревьев для автокадовских данных эффективнее, в каких случаях, какие из деревьев, как лучше реализовать на том-другом языке, какой это может дать, дало реальный результат? zamtmn, результаты Вашей оптимизации впечатляют, бьют наповал, но что из этого выйдет в Автокаде? Впечатляет фантастическая скорость просмотра примитивов hwd, но неясно, как это помогает анализу геометрических отношений примитивов? Кроме этих двух реальных, реализованных примеров (не в Автокаде, не для анализа геометрии), получается, ничего не абстрактно-теоретичекого нет или великая тайна. Ну, значит, так. |
||||
|
||||
Продуман Регистрация: 22.02.2007
Питер
Сообщений: 2,840
|
Вы уверены, что понимаете о чем Вам пишут, а где и для чего по Вашему?? Если Вам этого мало - то просто не пытайтесь этим заниматься - это, так сказать, не Ваше...
__________________
Когда в руках молоток все вокруг кажется гвоздями. |
|||
|
||||
regular.dxf я до сих пор не проверял:
- Autocad Map 3D - Drawing cleanup - Break intersections сделало на средней машине за примерно 3.5 секунды! - Лисп BreakObjects - на двадцатой, примерно, минуте я остановил процесс. Получается, что Autocad Map 3D для своих действий оптимизацию очень даже применяет. И про FlashPolygons от Delicad - сделал из всех пересечений элементов в меньшем nonregular2.dxf полигоны за 30 секунд. Цитата:
Как бы сделать создание новых примитивов из пересечений, чтобы и ресурсов хватало, и скорость была высокой? Общие подходы можете посоветовать? |
||||
|
||||
Инженер САПР Регистрация: 12.11.2004
Тюмень
Сообщений: 36
|
Извиняюсь, что встреваю в мудрые разговоры.
Раз дело касается AutoCAD, то и используйте его возможности. Как, например, здесь: объединение большого количества отрезков. Волшебная функция (ssget "_C" p1 p2) наверняка уже тыщу раз оптимизирована разработчиками, берите и используйте - тогда даже на обыкновенном autolisp все шустро просчитывается. Если непонятно: берете примитив, получаете его bounding box, по ним ssget - получаете (обычно) небольшой набор, по нему уже тупо перебором проверили реальные пересечения. И не надо никакой мороки со всякими индексами, ибо индексы уже есть в самом автокаде. |
|||
|
||||
Регистрация: 16.08.2006
Санкт-Петербург
Сообщений: 508
|
Поправьте меня, если я ошибаюсь: эта волшебная функция требует, что бы данный прямоугольник был на экране. Т.е. либо скакать по всему чертежу, либо масштабировать, что бы весь чертёж сразу был на экране.
При самостоятельной обработке я могу работать даже без открытия чертежа (открывая только базу данных), что гораздо быстрее при пакетной обработке, скажем. Да и в целях тестируемости лучше изолировать код, работающий непосредственно с автокадом как можно дальше (т.е. выделить зависимости от автокада в как можно меньшее кол-во классов, и только изредка их использовать) Так что оба метода имеют право на жизнь, у каждого своё предназначение. Аналог ssget в .net данном случае будет метод Editor.SelectCrossingPolygon
__________________
Алексей |
|||
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Документация Проектировщику на Torrents | DEM | Разное | 262 | 24.02.2024 17:19 |
Жилые и общественные здания: краткий справочник инженера-конструктора. Под ред. Ю.А. Дыховичного и В.И. Колчунова. 2011 (Впечатления и отзывы). | Armin | Поиск литературы, чертежей, моделей и прочих материалов | 19 | 22.03.2018 15:41 |
Порекомендуйте литературу для повышения квалификации(грунты, геотехника) | acid | Поиск литературы, чертежей, моделей и прочих материалов | 6 | 13.05.2015 22:14 |
Случайный эксцентриситет | p_sh | Прочее. Архитектура и строительство | 14 | 22.07.2009 11:32 |
Защита от распространения большого числа dwg | E.D. | AutoCAD | 24 | 21.11.2008 09:02 |