SASGIS - SAS.Планета
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0003801SAS.Планета[All Projects] Хотелка / Feature requestpublic03-12-2021 10:1713-04-2022 13:02
Reportervdemidov 
Assigned Tovdemidov 
PrioritynormalSeverityminorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformWindowsOS7OS VersionUltimate
Product Version201212 
Target Version211230Fixed in Version211230 
Summary0003801: Переделать алгоритм вычисления количества тайлов попадающих в полигон
DescriptionСейчас при вычислении количества тайлов попадающих в полигон используется очень тупой алгоритм. Мы перебираем все тайлы в прямоугольнике покрывающем полигон и для каждого проверяем попадает ли этот тайл в полигон.
Грубая оценка сложности O(4^Zoom), то есть c увеличением на 1 зум время вычисления увеличивается в 4 раза
Steps To Reproduce
Additional Information
TagsNo tags attached.
Relationships
child of 0001531confirmed  Исправить отображение количества тайлов в окне Операции с выделенной областью 
Attached Files
Issue History
Date ModifiedUsernameFieldChange
03-12-2021 10:17vdemidovNew Issue
03-12-2021 10:17vdemidovStatusnew => assigned
03-12-2021 10:17vdemidovAssigned To => vdemidov
03-12-2021 10:17vdemidovIssue generated from: 0001531
03-12-2021 10:17vdemidovRelationship addedchild of 0001531
03-12-2021 10:18vdemidovDescription Updatedbug_revision_view_page.php?rev_id=7785#r7785
03-12-2021 10:25vdemidovNote Added: 0020231
03-12-2021 10:30vdemidovNote Added: 0020232
03-12-2021 10:34vdemidovNote Added: 0020233
03-12-2021 10:35zedDescription Updatedbug_revision_view_page.php?rev_id=7786#r7786
03-12-2021 10:36vdemidovNote Added: 0020234
03-12-2021 10:37vdemidovNote Added: 0020235
03-12-2021 10:39vdemidovNote Added: 0020236
03-12-2021 10:50vdemidovNote Added: 0020237
03-12-2021 10:56vdemidovNote Added: 0020238
03-12-2021 11:00vdemidovStatusassigned => resolved
03-12-2021 11:00vdemidovFixed in Version => .Nightly
03-12-2021 11:00vdemidovResolutionopen => fixed
10-12-2021 17:49zedFixed in Version.Nightly => 211230
13-04-2022 13:02zedNote Added: 0020303
08-08-2025 13:24zedCategoryХотелка => Хотелка / Feature request

Notes
(0020231)
vdemidov   
03-12-2021 10:25   
Маленькая демонстрация проблемы алгоритма. Допустим на зуме 1 подсчет количества тайлов у нас занимает 1 миллисекунду, токгда с ростом зума будет вот такая последовательность:
1 0.000001
2 0.000004
3 0.000016
4 0.000064
5 0.000256
6 0.001024
7 0.004096
8 0.016384
9 0.065536
10 0.262144
11 1.048576
12 4.194304
13 16.777216
14 67.108864
15 268.435456
16 1073.741824
17 4294.967296
18 17179.869184
19 68719.476736
20 274877.906944

То есть уже на 14-м зуме больше минуты, а на двадцатом 76 часов.
(0020232)
vdemidov   
03-12-2021 10:30   
Реальные данные
1 0.000116
2 0.000474
3 0.001913
4 0.007649
5 0.030184
6 0.120781
7 0.482643
8 1.937707
9 7.870721
10 31.529141
(0020233)
vdemidov   
03-12-2021 10:34   
Алгоритм с делением прямоугольника пополам должен иметь сложность o(2^Zoom), то есть время работы с увеличением на 1 зум должно увеличиваться в 2 раза.
(0020234)
vdemidov   
03-12-2021 10:36   
Реальные данные:
1 0.000105
2 0.000290
3 0.000692
4 0.001465
5 0.003159
6 0.006561
7 0.013396
8 0.027085
9 0.060304
10 0.114417
11 0.224926
12 0.435376
13 0.848580
14 1.700241
15 3.395835
(0020235)
vdemidov   
03-12-2021 10:37   
Все еще могут быть проблемы на очень сложных полигонах на больших зумах, но уже гораздо лучше.
(0020236)
vdemidov   
03-12-2021 10:39   
Очень сильно будет зависеть от полигона. Но на разумных вменяемых полигонах должно занимать время не больше пары секунд.
(0020237)
vdemidov   
03-12-2021 10:50   
Итого меньше 50 строчек на весь алгоритм.
(0020238)
vdemidov   
03-12-2021 10:56   
Отдельно хочется заметить насколько удобно что-то переделывать и оптимизировать, когда есть юнит тесты и тесты производительности :)
(0020303)
zed   
13-04-2022 13:02   
Если на z13 выделить полигон по размеру экрана и включить загрузку z1-z2 то алгоритм выдаст, что для загрузки ничего нет - 0 тайлов. Старый алгоритм выдавал для загрузки по одному тайлу на зум. Начиная с z3, алгоритм работает аналогично старому.

Баг?