|
Notes |
|
|
|
Маленькая демонстрация проблемы алгоритма. Допустим на зуме 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 часов. |
|
|
|
|
Реальные данные
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 |
|
|
|
|
|
Алгоритм с делением прямоугольника пополам должен иметь сложность o(2^Zoom), то есть время работы с увеличением на 1 зум должно увеличиваться в 2 раза. |
|
|
|
|
Реальные данные:
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 |
|
|
|
|
|
Все еще могут быть проблемы на очень сложных полигонах на больших зумах, но уже гораздо лучше. |
|
|
|
|
|
Очень сильно будет зависеть от полигона. Но на разумных вменяемых полигонах должно занимать время не больше пары секунд. |
|
|
|
|
|
Итого меньше 50 строчек на весь алгоритм. |
|
|
|
|
|
Отдельно хочется заметить насколько удобно что-то переделывать и оптимизировать, когда есть юнит тесты и тесты производительности :) |
|
|
|
(0020303)
|
|
zed
|
|
13-04-2022 13:02
|
|
Если на z13 выделить полигон по размеру экрана и включить загрузку z1-z2 то алгоритм выдаст, что для загрузки ничего нет - 0 тайлов. Старый алгоритм выдавал для загрузки по одному тайлу на зум. Начиная с z3, алгоритм работает аналогично старому.
Баг? |
|