SASGIS - SAS.Планета
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0002463SAS.ПланетаРефакторингpublic16-07-2014 18:3314-06-2015 11:14
Reporterzed 
Assigned To 
PrioritynormalSeverityminorReproducibilityhave not tried
StatusconfirmedResolutionopen 
PlatformOSOS Version
Product Version140505 
Target Version24xxxxFixed in Version 
Summary0002463: В подсистеме sml меток оптимизировать поиск вхождения элементов в прямоугольник
DescriptionСейчас производится полный перебор всех меток и сравнивается входит метка в заданный прямоугольник или нет TMarkDbSml._AddMarksToListByRect. Для такого рода операций поиска, придуман R-tree индекс. Нужно использовать его или что-то похожее.
Steps To Reproduce
Additional InformationРеализация на Delphi есть вот тут: R*-tree или индексация геопространственных данных, правда, там нету метода удаления элементов из индекса. Возможно, можно доработать.

Есть крохотная сишная библиотека: R-Tree Library (но с год не обновлялась и вроде как beta).

Так же, этот индекс есть в SQLite (внезапно). Чтобы не зависеть от наличия/отсутствия либы, можно воспользоваться компонентом Synopse, где есть готовые *.obj и соответствующие высокоуровнивые обёртки:
TSQLRecordRTree to implement R-Tree virtual tables.
TagsNo tags attached.
Relationships
related to 0002462confirmed  В подсистеме sml меток оптимизировать чтение геометрии 
Attached Files
Issue History
Date ModifiedUsernameFieldChange
16-07-2014 18:33zedNew Issue
16-07-2014 18:33zedAdditional Information Updatedbug_revision_view_page.php?rev_id=6165#r6165
16-07-2014 18:40zedNote Added: 0014434
16-07-2014 18:40zedRelationship addedrelated to 0002462
16-07-2014 19:04zedNote Added: 0014437
24-10-2014 14:29vdemidovStatusnew => confirmed
24-10-2014 14:29vdemidovTarget Version => 24xxxx
07-05-2015 18:41vasketsovNote Added: 0015862
07-05-2015 18:53zedNote Added: 0015863
07-05-2015 18:54zedNote Edited: 0015863bug_revision_view_page.php?bugnote_id=15863#r6582
07-05-2015 18:54zedNote Edited: 0015863bug_revision_view_page.php?bugnote_id=15863#r6583
14-06-2015 11:08vasketsovNote Added: 0016014
14-06-2015 11:14zedNote Added: 0016015

Notes
(0014434)
zed   
16-07-2014 18:40   
Замечу, что для операции поиска меток, нам нужен только ограничивающий прямоугольник, а не целиком вся геометрия метки. Чисто случайно, этот прямоугольник у нас хранится в sml отдельно от геометрии, так что эта оптимизация не нарушит другую: 0002462. Ну, т.е. надо делать так, чтобы не нарушила. Эти две оптимизации можно применить одновременно.
(0014437)
zed   
16-07-2014 19:04   
Пример использования Synopse: TTestMemoryBased._RTree.
(0015862)
vasketsov   
07-05-2015 18:41   
>этот индекс есть в SQLite (внезапно)
http://sqlite.org/rtree.html
The source code to the SQLite R*Tree module is included as part of the amalgamation but is disabled by default. To enable the R*Tree module, simply compile with the SQLITE_ENABLE_RTREE C-preprocessor macro defined. With many compilers, this is accomplished by adding the option "-DSQLITE_ENABLE_RTREE=1" to the compiler command-line.

Так что собирать надо SQLite3 для R-tree руками.
(0015863)
zed   
07-05-2015 18:53   
(edited on: 07-05-2015 18:54)
Вообще, да, но можно взять готовый obj из фреймворка mORMot:
http://synopse.info/files/sqlite3obj.7z (постоянная ссылка, сам obj регулярно обновляется до текущей актуальной версии).

Из архива брать файлик sqlite3fts3.obj (включены FTS3 и RTree) и обёртку SynSQLite3Static.pas из репо. Оно, конечно, потянет ещё чутка юнитов из фреймворка, зато "из коропки" будут нужные фичи и статическая линковка.
(0016014)
vasketsov   
14-06-2015 11:08   
>Вообще, да, но можно взять готовый
>sqlite3fts3.obj (включены FTS3 и RTree)
Я несколько удивлён, но проверил на всех последних официальных билдах - там это есть "из коропки":
SQLite version 3.8.10.2 2015-05-20 18:17:19
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> PRAGMA compile_options;
ENABLE_FTS3
ENABLE_RTREE
SYSTEM_MALLOC
THREADSAFE=0
sqlite>
(0016015)
zed   
14-06-2015 11:14   
О, вообще круто. Но в случае в прилинкованным объктником можно быть на 100% увернным, что эти опции доступны. А в dll сегодня есть, а завтра нет. Ну или внимательно проверять перед каждым обновлением либы, что там всё включено.