SASGIS

Веб-картография и навигация
All Projects | SAS.Планета | Домен, сайт, форум, багтрекер | Доработка карты (ZMP) | Переводы и локализации | Прочее

My View | View Issues | Change Log | Roadmap | Search
  

View Issue Details [ Jump to Notes ] [ Issue History ] [ Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0003801SAS.Планета[All Projects] Хотелкаpublic03-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 раза
TagsNo tags attached.
Attached Files

- Relationships
child of 0001531confirmed Исправить отображение количества тайлов в окне Операции с выделенной областью 

-  Notes
(0020231)
vdemidov (manager)
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 (manager)
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 (manager)
03-12-2021 10:34

 Алгоритм с делением прямоугольника пополам должен иметь сложность o(2^Zoom), то есть время работы с увеличением на 1 зум должно увеличиваться в 2 раза.
(0020234)
vdemidov (manager)
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 (manager)
03-12-2021 10:37

 Все еще могут быть проблемы на очень сложных полигонах на больших зумах, но уже гораздо лучше.
(0020236)
vdemidov (manager)
03-12-2021 10:39

 Очень сильно будет зависеть от полигона. Но на разумных вменяемых полигонах должно занимать время не больше пары секунд.
(0020237)
vdemidov (manager)
03-12-2021 10:50

 Итого меньше 50 строчек на весь алгоритм.
(0020238)
vdemidov (manager)
03-12-2021 10:56

 Отдельно хочется заметить насколько удобно что-то переделывать и оптимизировать, когда есть юнит тесты и тесты производительности :)
(0020303)
zed (manager)
13-04-2022 13:02

 Если на z13 выделить полигон по размеру экрана и включить загрузку z1-z2 то алгоритм выдаст, что для загрузки ничего нет - 0 тайлов. Старый алгоритм выдавал для загрузки по одному тайлу на зум. Начиная с z3, алгоритм работает аналогично старому.

Баг?

- Users who viewed this issue
User List Anonymous (954x), yaushev (2x), vdemidov (27x), ingener (2x), zed (8x)
Total Views 993
Last View 21-11-2024 09:52

- Issue History
Date Modified Username Field Change
03-12-2021 10:17 vdemidov New Issue
03-12-2021 10:17 vdemidov Status new => assigned
03-12-2021 10:17 vdemidov Assigned To => vdemidov
03-12-2021 10:17 vdemidov Issue generated from: 0001531
03-12-2021 10:17 vdemidov Relationship added child of 0001531
03-12-2021 10:18 vdemidov Description Updated View Revisions
03-12-2021 10:25 vdemidov Note Added: 0020231
03-12-2021 10:30 vdemidov Note Added: 0020232
03-12-2021 10:34 vdemidov Note Added: 0020233
03-12-2021 10:35 zed Description Updated View Revisions
03-12-2021 10:36 vdemidov Note Added: 0020234
03-12-2021 10:37 vdemidov Note Added: 0020235
03-12-2021 10:39 vdemidov Note Added: 0020236
03-12-2021 10:50 vdemidov Note Added: 0020237
03-12-2021 10:56 vdemidov Note Added: 0020238
03-12-2021 11:00 vdemidov Status assigned => resolved
03-12-2021 11:00 vdemidov Fixed in Version => .Nightly
03-12-2021 11:00 vdemidov Resolution open => fixed
10-12-2021 17:49 zed Fixed in Version .Nightly => 211230
13-04-2022 13:02 zed Note Added: 0020303

My View | View Issues | Change Log | Roadmap | Search
  

Copyright © 2007 - 2024 SAS.Planet Team