0001894: Оптимизация итератора тайлов для мультиполигонов

Notes
(0011317) vdemidov (manager) 07-05-2013 07:24	У каждого полигона в мультиполигоне есть ограничивающий его прямоугольник. Для наиболее массового случая, когда эти прямоугольники не пересекаются, вполне можно итерировать по каждому из полигонов отдельно.

(0011318) vasketsov (manager) 07-05-2013 07:36	Собственно об этом второй параграф и повествует )) Реализация очевидна: берём полигоны по одному, и проверяем: либо очередной ни с кем не пересекается (и обрабатывается отдельно и просто), либо он пересекается хотя бы с одним другим, и тогда его откладываем в кучку к пересекаемому. После первого этапа получим обработанные все отдельные полигоны + отдельные множества из 2-х и более полигонов каждое. И кодится это чуть более просто, чем тривиально. Самое интересное потом: как быстро оставшиеся множества обойти, и чтобы все тайлы в списке не хранить для сверки, а то и по скорости и по памяти это будет убийственным. Если например некто выделит отдельно европу и отдельно азию, и перекроет полигоны хотя бы на один тайл, на приличных зумах будет сильно больно. Надо как-то анализировать характер пересечения множеств. Даже выполнение их сложения (и работа с суммой множеств после этого) может как ускорить весь процесс, так и замедлить.

(0011320) vdemidov (manager) 07-05-2013 07:47	А мое замечание о том, что можно сделать простую оптимизацию, которая покроет наиболее частые случаи. А сложный анализ пересечений оставить на потом. :) То есть, берём полигоны по одному, и проверяем: либо очередной ни с кем не пересекается (и обрабатывается отдельно и просто), либо он пересекается хотя бы с одним другим, и тогда его откладываем в кучку к пересекаемому. Потом обрабатываем те что были отложены как пересекающиеся. Первый обрабатываем просто так. А при обработке всех остальных проверяем, что бы тайл не попадал в уже обработанные пересекающиеся. Это конечно чуток замедлит, но в 95% реальных задач будет работать быстро и эффективно. Даже случай Европы с Азией обработается ИМХО достаточно быстро.

Users who viewed this issue
User List	Anonymous (2410x), vdemidov (5x)
Total Views	2415
Last View	21-11-2024 13:32

Issue History
Date Modified	Username	Field	Change
24-04-2013 18:08	vasketsov	New Issue
07-05-2013 07:24	vdemidov	Note Added: 0011317
07-05-2013 07:25	vdemidov	Status	new => confirmed
07-05-2013 07:25	vdemidov	Product Version	=> 121010
07-05-2013 07:25	vdemidov	Target Version	=> 26xxxx
07-05-2013 07:36	vasketsov	Note Added: 0011318
07-05-2013 07:47	vdemidov	Note Added: 0011320
25-04-2015 13:14	vasketsov	Relationship added	related to 0002701

SASGIS