SASGIS - SAS.Планета
View Issue Details
0001531SAS.Планета[All Projects] Хотелкаpublic29-08-2012 13:5203-12-2021 10:17
Tolik 
 
normalminoralways
confirmedopen 
Windows7Ultimate
120808 
29xxxx 
0001531: Исправить отображение количества тайлов в окне Операции с выделенной областью
Если выделение не прямоугольной формы, число тайлов отображается неверно: не точное число в выделенной области, а число в окружающем прямоугольнике.

(c) by Zed:
Почему - из соображений быстродействия. Решение - можно предложить вариант: если выделение сложное (скажем более 100 точек, цифру можно вынести в настройки), то выводить статистику для прямоугольника (как сейчас), но к количеству тайлов добавлять знак менее: "<7574". Ну или словом написать, что менее. Тогда не будет таких вот вопросов. А сейчас, действительно - дезинформация.
http://sasgis.org/forum/viewtopic.php?p=29814#p29814
No tags attached.
parent of 0002850resolved vdemidov Создать отдельную функцию вычисления количества тайлов в полигоне 
parent of 0003801resolved vdemidov Переделать алгоритм вычисления количества тайлов попадающих в полигон 
has duplicate 0002646closed zed Количества файлов в Операциях с выделенной областью считает по прямоугольнику, описанному вокруг полигона 
Issue History
29-08-2012 13:52TolikNew Issue
29-08-2012 14:14zedNote Added: 0008634
29-08-2012 15:03TolikNote Added: 0008635
29-08-2012 15:05TolikNote Edited: 0008635bug_revision_view_page.php?bugnote_id=8635#r4183
29-08-2012 15:10TolikNote Added: 0008636
29-08-2012 15:15zedNote Added: 0008637
29-08-2012 16:24Dima2000Note Added: 0008638
29-08-2012 19:03vdemidovStatusnew => confirmed
29-08-2012 19:07vdemidovTarget Version => 29xxxx
30-08-2012 07:20gufNote Added: 0008643
30-08-2012 09:51TolikNote Added: 0008646
30-08-2012 09:52TolikNote Edited: 0008646bug_revision_view_page.php?bugnote_id=8646#r4185
30-08-2012 12:46Dima2000Note Added: 0008647
30-08-2012 12:57zedNote Added: 0008648
10-03-2015 15:39rsuanNote Added: 0015355
10-03-2015 15:40rsuanNote Edited: 0015355bug_revision_view_page.php?bugnote_id=15355#r6439
10-03-2015 17:03zedRelationship addedhas duplicate 0002646
10-03-2015 17:41PapazolNote Added: 0015356
11-03-2015 05:29rsuanNote Edited: 0015355bug_revision_view_page.php?bugnote_id=15355#r6440
11-03-2015 05:56rsuanNote Added: 0015359
11-03-2015 06:03rsuanNote Edited: 0015359bug_revision_view_page.php?bugnote_id=15359#r6442
11-03-2015 08:01rsuanNote Edited: 0015359bug_revision_view_page.php?bugnote_id=15359#r6443
11-03-2015 18:29PapazolNote Added: 0015360
12-03-2015 01:58rsuanNote Added: 0015361
12-03-2015 05:10rsuanNote Edited: 0015361bug_revision_view_page.php?bugnote_id=15361#r6445
12-03-2015 10:21vdemidovNote Added: 0015372
12-03-2015 10:53rsuanNote Added: 0015374
12-03-2015 10:53PapazolNote Added: 0015375
12-03-2015 11:36rsuanNote Edited: 0015374bug_revision_view_page.php?bugnote_id=15374#r6447
12-03-2015 11:50rsuanNote Edited: 0015374bug_revision_view_page.php?bugnote_id=15374#r6448
12-03-2015 11:57zedNote Added: 0015377
12-03-2015 11:59rsuanNote Added: 0015378
12-03-2015 12:03zedNote Added: 0015379
12-03-2015 12:05rsuanNote Edited: 0015378bug_revision_view_page.php?bugnote_id=15378#r6450
12-03-2015 12:19rsuanNote Added: 0015383
12-03-2015 12:23zedNote Added: 0015385
12-03-2015 13:10vdemidovNote Added: 0015388
12-03-2015 16:52rsuanNote Added: 0015396
13-03-2015 12:21rsuanNote Edited: 0015396bug_revision_view_page.php?bugnote_id=15396#r6458
13-03-2015 15:34rsuanNote Edited: 0015378bug_revision_view_page.php?bugnote_id=15378#r6459
13-03-2015 15:36rsuanNote Edited: 0015378bug_revision_view_page.php?bugnote_id=15378#r6460
13-03-2015 15:36rsuanNote Edited: 0015378bug_revision_view_page.php?bugnote_id=15378#r6461
13-03-2015 15:42rsuanNote Edited: 0015396bug_revision_view_page.php?bugnote_id=15396#r6462
14-03-2015 17:03rsuanNote Added: 0015411
14-03-2015 17:07rsuanNote Edited: 0015411bug_revision_view_page.php?bugnote_id=15411#r6464
14-03-2015 17:48rsuanNote Edited: 0015411bug_revision_view_page.php?bugnote_id=15411#r6465
14-03-2015 18:19rsuanNote Edited: 0015411bug_revision_view_page.php?bugnote_id=15411#r6466
14-03-2015 19:30rsuanNote Edited: 0015411bug_revision_view_page.php?bugnote_id=15411#r6467
14-03-2015 19:45zedNote Added: 0015412
15-03-2015 09:37rsuanNote Added: 0015413
15-03-2015 09:54zedNote Added: 0015414
15-03-2015 10:17rsuanNote Edited: 0015413bug_revision_view_page.php?bugnote_id=15413#r6469
15-03-2015 10:31rsuanNote Added: 0015415
15-03-2015 10:35zedNote Added: 0015416
17-03-2015 09:43vdemidovNote Added: 0015421
17-03-2015 10:43zedNote Added: 0015422
17-03-2015 11:41vdemidovNote Added: 0015423
17-03-2015 12:40zedNote Added: 0015424
17-03-2015 13:24vdemidovNote Added: 0015425
17-03-2015 13:59zedNote Added: 0015426
17-03-2015 14:38vdemidovNote Added: 0015427
17-03-2015 14:39vdemidovNote Edited: 0015427bug_revision_view_page.php?bugnote_id=15427#r6471
17-03-2015 15:28zedNote Added: 0015428
17-03-2015 15:55vdemidovNote Added: 0015429
17-03-2015 16:16zedNote Added: 0015430
18-03-2015 05:35vasketsovNote Added: 0015431
18-03-2015 09:12rsuanNote Added: 0015432
24-03-2015 12:32rsuanNote Added: 0015477
24-03-2015 12:34rsuanNote Edited: 0015477bug_revision_view_page.php?bugnote_id=15477#r6483
24-03-2015 12:35rsuanNote Edited: 0015477bug_revision_view_page.php?bugnote_id=15477#r6484
09-10-2015 10:31vdemidovRelationship addedparent of 0002850
03-12-2021 09:42vdemidovNote Added: 0020230
03-12-2021 10:17vdemidovIssue cloned: 0003801
03-12-2021 10:17vdemidovRelationship addedparent of 0003801

Notes
(0008634)
zed   
29-08-2012 14:14   
Был не прав - количество точек в сложном выделении не влияет (или слабо влияет) на скорость подсчёта тайлов.
(0008635)
Tolik   
29-08-2012 15:03   
(edited on: 29-08-2012 15:05)
Зато влияет зум. В том примере со Швецией на зумах 11-14 у меня считает за <1 сек, на z15 - 2 с, z16 - 4 с, дальше вообще очень долго.
Наверно, можно сделать формулу, например, если X*Y <= 1 млн. тайлов, то выводить точное число.
И это число, конечно, в ini, а 0 - значит, считать точно всегда (только что-то придумать, чтоб не висло на время расчёта).

(0008636)
Tolik   
29-08-2012 15:10   
Или ещё лучше: во время расчёта показывать число X*Y со знаком "<", после расчёта заменять его на точное число (если, конечно, сам расчёт не отнимает слишком много ресурсов)
(0008637)
zed   
29-08-2012 15:15   
Можно и прямо во время расчёта циферку отматывать, чтобы было видно, что процесс подсчёта ещё не закончился.

И перед всём этим хозяйством писать: Полигон или Прямоугольник.
(0008638)
Dima2000   
29-08-2012 16:24   
Вот это более реально, да. Сначала вывести (<XXXXX) по ограничивающему прямоугольнику и потом в фоне плавно отматывать до точного количества. В конце знак '<' или убрать вообще, или сменить на '='. И подсчёт делать именно в фоне и с низким приоритетом, чтобы не мешало.
Можно даже сохранять точное количество в ini рядом с самим последним выделением (как его свойство). С указанием по какой карте/слою оно посчитано. И при смене карты/слоя пересчитывать.

Скорость проверки тайлов на принадлежность полигону от количества точек в полигоне очевидно зависит, но для полигонов до нескольких тысяч точек это несущественно. Потому что НАМНОГО тормознее простой перебор миллионов тайлов ограничивающего прямоугольника.
(0008643)
guf   
30-08-2012 07:20   
По поводу нагрузки хочу заметить, что при запуске закачки или открытии сохраненной сессии он пересчитывает многоугольник для каждой запущеной сессии. На закачку можно и 10 и 20 заданий параллельно поставить, а работать с выделением можно только в 1 экземпляре. Так имеет ли смысл при этом упрощать и облегчать расчет, при работе с выделением?
(0008646)
Tolik   
30-08-2012 09:51   
(edited on: 30-08-2012 09:52)
Имеет смысл облегчать, чтобы при выборе зума сразу появлялось какое-то число тайлов, пусть только верхний предел (по прямоугольнику). Иначе будут неприятные тормоза при работе гуи. А после того, как расчёт в фоновом режиме завершится, можно и точное число вывести.

Кстати, поэтому не стоит выводить бегущий счётчик, лучше "<",X*Y

(0008647)
Dima2000   
30-08-2012 12:46   
Я как подумаю что тут придётся создавать новый процесс с низким приоритетом, создавать в нём итератор (чтобы не дублировать конструктор итератора), ждать пока конструктор подсчитает количество тайлов, завершать процесс (да ещё и аккуратно при любых возможных действиях пользователя) - сомнение берёт что кто-то станет делать ...
Да, а без переписывания конструктора итератора (вернее без его дублирования) не сделать бегущий счётчик, конструктор вернёт лишь точное число тайлов, ну когда подсчитает, без всяких промежуточных результатов.

И потом, при запуске операции (закачки, экспорта, копирования, ...) всё повторится - снова конструктор итератора с паузой на расчёт ...
(0008648)
zed   
30-08-2012 12:57   
>придётся создавать новый процесс
Поток, а не процесс. Вернее, тут придётся сделать новый поточный итератор, с возможностью получения количества тайлов во время подсчёта.

Зато, его потом можно будет использовать везде для расчёта числа тайлов в фоне, а скажем, скачку начинать сразу же, без ожидания пока она там посчитает все эти тайлы.

>сомнение берёт что кто-то станет делать
Задача достаточно интересная, почему бы и не сделать? Да и сам итератор сейчас весьма примитивен - есть широкое поле для оптимизаций.
(0015355)
rsuan   
10-03-2015 15:39   
(edited on: 11-03-2015 05:29)
(...прошло два с половиной года :)
Подключаюсь к вам из дублирующей хотелки 2646. Подниму актуальность обсуждаемого вопроса.
Нынешний расчёт действительно сильно вводит в заблуждение. Я выделял путь между Читой и Иркутском, и, увидя невообразимое количество файлов, пару дней потратил в раздумиях, почему так странно, и что делать, какие зумы и карты тогда выбирать для скачки, пока не разобрался. Зная нынешний метод расчёта, я б не обращал на него внимания и уже давно скачал что нужно.
Как минимум нужно возле нынешнего расчёта дать знать, что он мягко говоря примерный.
По поводу расчёта действительного количества, предлагаю рядом с примерным расчётом написать "производится точный расчёт". Если чел. не дожидается и запускает скачку либо закрывает окно, то фоновый поток прекращается. Либо рядом с примерным расчётом сделать кнопочку точного расчёта и отсчёт процента выполнения.

(0015356)
Papazol   
10-03-2015 17:41   
Если не посчитать точное значение (прервать подсчёт), то нельзя будет нормально прорисовать прогресс, да и просто посчитать процент выполнения задачи. А это нужно. Если действительно так долго считается на больших зумах, надо предупреждающее что-то сделать, чтоб не пугать никого зависанием.

Но вроде на обычных полигонах считается правильно и не слишком долго, или я не замечаю чего?
(0015359)
rsuan   
11-03-2015 05:56   
(edited on: 11-03-2015 08:01)
Вы о прогрессе расчёта количества файлов в окне Операций или уже в окне Скачивания?
Вот сейчас расчёт реального количества файлов производится после нажатия кнопки скачивания, само скачивание начинается только после расчёта. И в указанном мною случае (путь Чита-Иркутск, извилистая узкая длинная полоса) даже при зуме 15 расчёт занял около 20 мин (Athlon64 X2 4800+). В это время я не мог понять, прога зависла или всё же что-то вычисляет, но посмотрел загрузка ядра процессора была полной. Так что минимум предупреждающее сообщение тут нужно.
Разъясните пожалуйста следующие моменты. Возможно ли выполнить предварительный расчёт, который бы позволил правильно отображать процент прогресса при непосредственно расчёте кол-ва файлов? Если не возможно, то я удивлюсь, ведь расчёт это наверное цикл от сих до сих. Если возможно, то значительный ли процент времени он занимает по сравнению с непосредственно расчётом кол-ва файлов?
Может быть сделать так?: появляется сообщение "идёт расчёт...", производится расчёт для прогресса, после чего сообщение приобретает вид "идёт расчёт...100%", начинается расчёт количества файлов, и процент уменьшается.

(0015360)
Papazol   
11-03-2015 18:29   
Я о прогрессе скачивания. Ведь знать, сколько скачалось и сколько осталось скачать, необходимо.
20 минут - это очень много. Но и путь у Вас зело длинён. На части разбить его не будет быстрее?
Точно не знаю, конечно, но представляю, что подсчёт количества тайлов, входящих в полигон, делается путём проверки их вхождения в полигон, начиная с самого верхнего левого и заканчивая самым нижним правым. Тогда предварительный расчёт - это как раз площадь прямоугольника, описывающего полигон.
(0015361)
rsuan   
12-03-2015 01:58   
(edited on: 12-03-2015 05:10)
Дык в окне прогресса скачивания, когда уже началось скачивание, прогресс показывается: количество файлов подлежащих обработке, сколько скачалось и сколько пропустилось! Проблема в том что в Окне операций показывается неправильное (для произвольного многоугольника) количество файлов. Об этом и хотелка! И "подпроблема" что при открытии окна скачивания с нулями, пока идёт расчёт реального количества, для пользователя не понятно, что происходит, почему скачивание не идёт.
На части разбить не будет быстрее, т.к. количество операций ручками увеличивается во столько раз, на сколько частей разбил. Ведь если сложить продолжительности расчётов каждой части, будет не меньше чем расчёт единого участка?
> предварительный расчёт - это как раз площадь прямоугольника, описывающего полигон.
Да, это я выяснил опытным путём после пары дней раздумий, почему такие цифры...

(0015372)
vdemidov   
12-03-2015 10:21   
Я кажется уже писал, что проверку попадания тайла в полигон и подсчет количества тайлов в полигоне можно сделать за логарифмическое время от сложности полигона, а не за линейное от площади, как это реализовано сейчас. У меня есть наработки, но они делались лет 5 назад и рассчитаны на полигоны в целых числах и строго квадратные тайлы. Если кто-то этим займется, то могу поделиться, но у меня руки до этого дойдут очень не скоро, так как существующее положение меня вполне устраивает и не доставляет ни малейших неудобств.
(0015374)
rsuan   
12-03-2015 10:53   
(edited on: 12-03-2015 11:50)
Поставил на скачку 16 зум. Думало больше часа. А ещё хотел скачать 17 и 18... Мне кажется, устраивать может тех, кто не собирается в дальние поездки на машине, либо у кого очень мощные компьютеры.
Где клич бросить можно разработчикам? :)

(0015375)
Papazol   
12-03-2015 10:53   
Недостаток линейного расчёта - сильная зависимость от "наклона" пути. Если путь горизонтален либо вертикален, площадь описывающего прямоугольника значительно сокращается, значит, и время расчёта тоже. Если путь разбить на части, приближающиеся к горизонтальным и вертикальным, то за счёт сокращения времени их обсчёта можно будет сделать дело быстрее. Естественно, все участки пути не смогут быть горизонтальными либо вертикальными, вот на эти наклонные и уйдёт львиная доля времени.
Для реализации оптимального алгоритма нужно знать Делфи, а это не всем дано, к сожалению.
(0015377)
zed   
12-03-2015 11:57   
> Для реализации оптимального алгоритма нужно знать Делфи

Прежде чем реализовывать алгоритм, его сперва нужно придумать (и желательно доказать, что он оптимальный). Алгоритм можно описать математически, блок-схемой, прозой и т.д. Реализация же алгоритма - вторичный, механический процесс.
(0015378)
rsuan   
12-03-2015 11:59   
(edited on: 13-03-2015 15:36)
Понял, что разделение пути на части может сократить время вычисления, но лениво добавлять себе работы руками.
Для начала хотя бы сделать запуск реального расчёта уже во время вывода окна Операций (с первоначальным отображением предварительного количества), показ прогресса подсчёта, передачу уже подсчитанной информации в окно Скачивания и продолжения процесса расчёта там.
А потом и об алгоритме расчёта подумать.

(0015379)
zed   
12-03-2015 12:03   
> А потом и об алгоритме расчёта подумать.

Ага, сделать ненужную работу, потом сесть, придумать алгоритм и переписать всё заново. Очень здорово получается.
(0015383)
rsuan   
12-03-2015 12:19   
Вам виднее, но я думал, процесс расчёта и вывод его результатов это как бы разделяемые вещи. Как изменение программного кода самого расчёта может сбить код вывода информации? Ведь объектное программирование это набор чёрных ящичков с вводами и выводами.
(0015385)
zed   
12-03-2015 12:23   
Так если расчёт обещает быть быстрым, то достаточно заменить алгоритм и не париться с дополнительным потоком и выводом промежуточных значений.
(0015388)
vdemidov   
12-03-2015 13:10   
Я наверное ошибся насчет логарифмической сложности от полигона, скорее логарифм от площади, но тут нужно думать. В любом случае на порядки быстрее текущего.
Ну идея алгоритма такая:
1. Получаем прямоугольник тайлов гарантированно покрывающий полигон.
2. Делим этот прямоугольник 4 части разделив примерно поровну по ширине и высоте.
3. Для каждого прямоугольника проверяем лежит ли он целиком внутри полигона, или снаружи, или пересекает.
4. Если полностью внутри, то просто добавляем нужное количество тайлов.
5. Если полностью снаружи, то забываем про него.
6. Если пересекает, то рекурсивно вызываем эту процедуру уже для этого прямоугольника.

Можно усложнить и для каждого прямоугольника передавать массив индексов ребер полигона, которые его пересекают, тогда уменьшится сложность проверки пересечения прямоугольником полигона.
(0015396)
rsuan   
12-03-2015 16:52   
(edited on: 13-03-2015 15:42)
> достаточно заменить алгоритм и не париться с дополнительным потоком и выводом промежуточных значений.<
Согласен, тогда действительно лучше заняться сразу алгоритмом расчёта. А вот его уже и предложили. Этот алгоритм позволит выбрасывать из подсчёта большие ненужные области. Теперь кто бы реализовал его )

> 20 минут - это очень много. Но и путь у Вас зело длинён.<
Долго думает видимо потому что путь, из которого получается полигон, нарисован не вручную, а автоматически кнопкой Проложить маршрут. Точки получаются очень частые => их очень много.

(0015411)
rsuan   
14-03-2015 17:03   
(edited on: 14-03-2015 19:30)
Придумал алгоритм, как по координатам отрезка сразу определить тайлы, которые он затрагивает, без перебора всех тайлов прямоугольника, диагональю которого является отрезок. Последовательным перебором сторон полигона можно отметить все тайлы по периметру полигона. Назовём это этап 1.
Теперь, чтобы получить координаты тайлов внутри полигона, предполагаю следующие действия (этап 2):
Производим перебор тайлов прямоугольника, описанного вокруг полигона. Только мы определяем не принадлежность тайлов полигону, а ищем тайлы, отмеченные на этапе 1. Найдя такой тайл, мы проверяем следующий уже на принадлежность полигону. Если он принадлежит, то отмечаем его как таковой, и проверяем следующий. И так до тайла, не принадлежающего полигону. Далее продолжаем перебирать на поиск найденных на первом этапе и при нахождении повторяем шаги этапа 2. Дойдя до конца прямоугольника, получим уже все тайлы полигона.
Опишу конкретнее по шагам:

10 Цикл Y от верхнего до нижнего ряда тайлов описанного прямоугольника
20 Цикл X от левого до правого столбца тайлов описанного прямоугольника
30 Если тайл(X,Y) не из найденных на этапе1, то Переход на 60
40 X=X+1 : Если X вышел за правую границу, то Переход на 70
50 Если тайл(X,Y) принадлежит полигону, то Отмечаем его (если он ранее уже был отмечен как тайл периметра, то ничего страшного что он ещё раз отметится) и Переход на 40
60 Следующий X
70 Следующий Y

Как я понимаю, в настоящее время реализованный в программе алгоритм перебирает все тайлы описанного прямоугольника на проверку принадлежности полигону (как это делается, я не знаю). В моём алгоритме тоже есть перебор всех тайлов прямоугольника, поэтому он сократит время по сравнению с существующим только если операция проверки тайла на отметку (строка 30: поиск тайла, отмеченного на этапе 1) существенно быстрее чем операция проверки тайла на принадлежность полигону. Если это так, то за счёт того, что количество тайлов, подлежащих проверке на принадлежность полигону, будет гораздо меньше - лишь не на много больше итогового количества тайлов полигона, сильно сократится время определения тайлов полигона. Прошу разработчиков ответить, так ли это. Если да, то могу огласить и алгоритм этапа 1.

Есть способ избежать прогона всех тайлов прямоугольника на этапе 2. Для этого в этапе 1 все тайлы периметра нужно помещать в отдельный массив. После этапа 1 нужно отсортировать их по порядку прогона тайлов в описанном прямоугольнике (справа налево сверху вниз). Получаем массив уже отсортированных тайлов периметра. Тогда в этапе 2 мы вместо прогона и проверки тайлов прямоугольника на отметку, сразу берём первый тайл этого массива, последовательно проверяем следующие тайлы описанного прямоугольника на принадлежность полигону, отмечаем их, пока не находим не принадлежащий полигону. Тогда мы ищем из массива тайл с координатами, который больше чем этот (не принадлежащий полигону) и повторяем процедуру этапа 2 уже для него.

Старался описать понятно. Если что, конкретизирую.

(0015412)
zed   
14-03-2015 19:45   
Ага, мне тоже на ум приходил алгоритм с периметром полигона. Причём, там вообще не нужно проверять попадание тайла в полигон и перебор по всем возможным X/Y не нужен. Т.е. достаточно пройтись по периметру и запомнить все тайлы, что в него попадают, а затем простейшей арифметикой вычислить число тайлов, пройдясь в цикле только по одной из сторон. Но этот алгоритм требует некоторых затрат памяти.
(0015413)
rsuan   
15-03-2015 09:37   
(edited on: 15-03-2015 10:17)
Я верил, что можно избежать тупого перебора всех тайлов большого прямоугольника :)
Скажите, верно ли моё предположение, что операция проверки тайла на отметку гораздо быстрее проверки на принадлежность полигону?

А пока - метод определения тайлов, на которых лежит отрезок, по координатам отрезка (этап 1).
Исхожу из того, что координатная сетка тайлов любого зума уже известна.
Отрезок делится на малые отрезки длиной, равной длине стороны тайла, т.е. вычисляются координаты точек деления. Искомыми тайлами являются:
- тайлы, на которые попадают точки деления;
- если точка деления попадает на границу между двумя тайлами, то берутся оба этих тайла;
- если точка деления попадает на перекрестие между четырьмя тайлами, то берутся все четыре тайла;
- если соседние точки деления располагаются на тайлах, размещающихся друг по отношению к другу по диагонали, то отрезочек, соединяющий эти точки деления, проходит через один из двух тайлов, соседствующих с теми двумя тайлами (до образования квадрата из четырёх тайлов). Для избежания вычисления, какой из них именно под отрезком, можно взять их оба. А можно и вычислить, какой именно.

(0015414)
zed   
15-03-2015 09:54   
> верно ли моё предположение
Да.

> Алгоритм определения тайлов
Первым делом переводим географические координаты точек полигона в тайловые. Затем, берём последовательно 2 точки полигона и строим функцию x = F(y) (это будет линейная функция, т.е. x = K*y), затем для всех Y из диапазона, ограниченного нашими двумя точками, вычисляем X - это и будут тайлы лежащие на границе нашего полигона (можно и наоборот, искать Y для известных X). Соответственно, повторив эту операцию для всех точек полигона, получим список всех тайлов, лежащих по периметру полигона.

> если точка деления попадает на границу
Такое в принципе невозможно. Если мы говорим о географических координатах, то точка однозначно попадает в один тайл. На границу оно попасть не может. В таких проверках географические координаты переводятся в пиксельные, а пиксель может принадлежать только одному из тайлов.
(0015415)
rsuan   
15-03-2015 10:31   
> Такое в принципе невозможно.
Действительно, чёт я пере(недо)мудрил :)
Ну всё, тайлы периметра определяются легко, методы определения тайлов внутри полигона тоже есть. "Реализация же алгоритма - вторичный, механический процесс" (с)zed ;-)
(0015416)
zed   
15-03-2015 10:35   
Ага, но никто не любит выполнять тупую механическую работу :)
(0015421)
vdemidov   
17-03-2015 09:43   
Любой алгоритм, который строит в памяти полный список тайлов на границе полигона обречен на падение по памяти. Очень легко сделать полигон, который на 24-м зуме будет пересекать миллиарды тайлов. Причем сам полигон будет состоять не больше чем из сотни точек.
(0015422)
zed   
17-03-2015 10:43   
Если полигон пересекает миллиарды тайлов, то покрывает он как минимум десятки миллиардов тайлов и загружать по таким полигонам реально никто не будет. Имхо, реальные цифры - несколько миллионов тайлов максимум, а в абсолютном большинстве - до миллиона. Сравнивать алгоритмы надо на реальных цифрах, а не взятых с потолка.
(0015423)
vdemidov   
17-03-2015 11:41   
А как ты будешь отличать эти случаи? Ну вот выделил человек какой-то полигон на весь мир. На 10-м зуме вполне реально скачать. И случайно выбрал в окне операций с выделенной областью 24-й, а программа взяла да и упала с нехваткой памяти? Или просто писать вместо количества тайлов, что мы такой полигон на таком зуме качать вообще не будем?
(0015424)
zed   
17-03-2015 12:40   
> А как ты будешь отличать эти случаи?

Можно грубо оценить количество тайлов по описывающему прямоугольнику и в зависимости от полученных цифр запускать тот или иной алгоритм.

Кстати, алгоритм с периметром хорош ещё тем, что помимо вычисления количества тайлов его результаты потом можно передать качалке и использовать в качестве итератора по тайлам и там уже никаких вычислений производить не нужно будет, а сразу пойдёт закачка.
(0015425)
vdemidov   
17-03-2015 13:24   
Ну, ждем реализации. Но я бы все-таки предложил реализовывать мой вариант с рекурсивным разбиением на прямоугольники. При желании, можно сохранять массив полностью входящих в полигон прямоугольников и потом использовать его в итераторе, что будет еще быстрее. И проблемы с памятью будут наступать только для очень сложных полигонов на очень больших зумах.
(0015426)
zed   
17-03-2015 13:59   
Могу предложить ещё один похожий алгоритм, оптимизированный по памяти:
- переводим географические координаты точек полигона в тайловые
- берём прямую, вдоль какой-либо оси координат, к примеру, вдоль X: (Xmin, Ymin);(Xmax, Ymin)
- находим точки пересечения линии с полигоном
- зная точки пересечения, можем легко подсчитать число тайлов лежащих на линии и принадлежащих полигону
- увеличиваем Y и повторяем процесс, пока Y не более Ymax

Тут мы так же итерируемся по одной из сторон, но ещё приходится использовать относительно медленную операцию поиска пересечения линии с полигоном. Зато не используем память для хранения периметра.
(0015427)
vdemidov   
17-03-2015 14:37   
(edited on: 17-03-2015 14:39)
Хороший вариант. Только нужно не забывать, что у нас линия тайлов это не отрезок, а прямоугольник. И еще есть вопрос, а будет ли это адекватно работать для неквадратных тайлов, если такие кодгда-то появятся. До сих пор я старался нигде не завязываться на размеры тайлов, более того сейчас большая часть кода допускает даже разные размеры тайлов в пределах одной проекции (Мне кажется, лучше все-таки работать с пиксельными координатами)

(0015428)
zed   
17-03-2015 15:28   
Глюков не будет, пока описывающий прямоугольник будет преобразовываться в прямоугольник тайлов, а не в какую-либо другую фигуру. Это легко проверяется на старте алгоритма.
(0015429)
vdemidov   
17-03-2015 15:55   
Я не про то. Я про то, что тайлы, которые попадают в полигон в пиксельных координатах, могут не попасть в полигон в тайловых координатах, или наоборот.
(0015430)
zed   
17-03-2015 16:16   
Да ну? Мне кажется, такого быть не должно. С пиксельными координатами эти алгоритмы работать не смогут.
(0015431)
vasketsov   
18-03-2015 05:35   
>Если полностью внутри, то просто добавляем нужное количество тайлов
Если бы алгоритм был бы записан на "языке" итератора, то было бы куда удобнее, КМК. Но идея в целом понятна, дочерний простой быстрый итератор по прямоугольнику тут решает.

>Придумал алгоритм, как по координатам отрезка сразу определить тайлы, которые он затрагивает, без перебора всех тайлов прямоугольника
Не очень понял, что Вы придумали, но есть алгоритм Брезенхема для построения наклонной псевдопрямой линии на двумерном растре (что пиксельном, что тайловом).

>я бы все-таки предложил реализовывать мой вариант с рекурсивным разбиением на прямоугольники
Мне представляется твой алгоритм двумерного половинного деления куда перспективнее периметрального. И с итераторами там в общем-то тоже особых проблем нет, так что и в качалку будет чего передать, чтобы не считать дважды.
(0015432)
rsuan   
18-03-2015 09:12   
> Не очень понял, что Вы придумали.
Хорошо, я подключился к информационному полю, сам не зная этого )

Рад что обсуждение вопроса продолжается.
(0015477)
rsuan   
24-03-2015 12:32   
(edited on: 24-03-2015 12:35)
Дальнейшие страдания. Всё тот же путь Чита-Красноярск. Зум до 17 (хотел до 18 но пришлось поуменьшить желания). Теперь произвожу операцию конвертации, копирования. Preparing tiles to export висит уже многие часы. Предстоит ещё несколько подобных операций над этим полигоном. Приходится признать что программа плохо оптимизирована для обработки полигонов, образованных по автоматически построенным путям большой протяжённости. Ведь это требуется для переезда между городами, помощь в чём является одной из задач программы.

(0020230)
vdemidov   
03-12-2021 09:42   
Эх. Не хотел я заниматься алгоритмом по нескольким соображениям: во-первых, меня это не напрягало, во-вторых, этот алгоритм локализован и идеально походит для начинающих вникать в код САС.Планеты, просто идеальная учебная задача. Но раз уж за 6 лет никто не занялся, да и я сам давно ничего для САС не кодил, то реализую рекурсиный алгоритм с делением прямоугольников пополам.