Сообщество программистов Autodesk в СНГ

ADN Club => AutoCAD .NET API => Тема начата: Алексей (IdeaSoft) от 01-07-2016, 16:40:56

Название: Поиск объектов на плоскости
Отправлено: Алексей (IdeaSoft) от 01-07-2016, 16:40:56

Есть большое количество примитивов (к примеру 2 000 000 шт.)
Нужно быстро найти любой примитив AutoCAD по вводным координатам X,Y.
Если точнее, выбрать объекты пересекающиеся с квадратом со стороной A где X,Y - середина квадрата.

Простым перебором таблицы примитивов думаю будет долго.

Думаю, решать эту задачу путем индексирования координат объектов
на плоскости и так сказать создать 2d-индекс.

Может кто подскажет как лучше решить задачу?

Вот эту статью я читал https://msdn.microsoft.com/ru-ru/library/bb964712(v=sql.105).aspx
Но это с поддержкой SQL Server.
А нужно сделать алгоритм без всякого SQL Server.

Название: Re: Поиск объектов на плоскости
Отправлено: Александр Ривилис от 01-07-2016, 16:51:15

Это должно помочь:
http://adn-cis.org/forum/index.php?topic=2826.0 (http://adn-cis.org/forum/index.php?topic=2826.0)
http://adn-cis.org/forum/index.php?topic=4254.0

Читай про R-деревья (https://ru.wikipedia.org/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)).

Название: Re: Поиск объектов на плоскости
Отправлено: Алексей (IdeaSoft) от 01-07-2016, 17:30:33

Цитата: Александр Ривилис от 01-07-2016, 16:51:15

Читай про R-деревья.

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

 

Название: Re: Поиск объектов на плоскости
Отправлено: Александр Ривилис от 01-07-2016, 19:08:25

Цитата: Алексей (IdeaSoft) от 01-07-2016, 17:30:33

1) Пройтись по базе примитивов и получить набор прямоугольников

Это всё что нужно, для использования алгоритма. Всё остальное есть по ссылкам, которые я дал.

Название: Re: Поиск объектов на плоскости
Отправлено: trir от 04-07-2016, 20:52:45

https://habrahabr.ru/post/278765/

Название: Re: Поиск объектов на плоскости
Отправлено: Алексей Терно от 05-07-2016, 10:34:26

А почему не воспользоваться методом editor.SelectCrossingPolygon?

Название: Re: Поиск объектов на плоскости
Отправлено: trir от 05-07-2016, 12:49:29

он медленный

Название: Re: Поиск объектов на плоскости
Отправлено: Алексей Терно от 05-07-2016, 12:53:58

по сравнению с чем?

Название: Re: Поиск объектов на плоскости
Отправлено: trir от 05-07-2016, 20:15:18

editor.SelectCrossingPolygon работает через GUI и если нужно делать много запросов к большому набору данных, то вообще не вариант

Название: Re: Поиск объектов на плоскости
Отправлено: Дмитрий Загорулькин от 11-07-2016, 12:43:47

Цитата: Алексей Терно от 05-07-2016, 10:34:26

А почему не воспользоваться методом editor.SelectCrossingPolygon?

http://adn-cis.org/forum/index.php?topic=4254
http://adn-cis.org/forum/index.php?topic=809.0