|
Notes |
|
|
|
|
У каждого полигона в мультиполигоне есть ограничивающий его прямоугольник. Для наиболее массового случая, когда эти прямоугольники не пересекаются, вполне можно итерировать по каждому из полигонов отдельно. |
|
|
|
|
Собственно об этом второй параграф и повествует ))
Реализация очевидна: берём полигоны по одному, и проверяем: либо очередной ни с кем не пересекается (и обрабатывается отдельно и просто), либо он пересекается хотя бы с одним другим, и тогда его откладываем в кучку к пересекаемому. После первого этапа получим обработанные все отдельные полигоны + отдельные множества из 2-х и более полигонов каждое. И кодится это чуть более просто, чем тривиально.
Самое интересное потом: как быстро оставшиеся множества обойти, и чтобы все тайлы в списке не хранить для сверки, а то и по скорости и по памяти это будет убийственным. Если например некто выделит отдельно европу и отдельно азию, и перекроет полигоны хотя бы на один тайл, на приличных зумах будет сильно больно. Надо как-то анализировать характер пересечения множеств. Даже выполнение их сложения (и работа с суммой множеств после этого) может как ускорить весь процесс, так и замедлить. |
|
|
|
|
А мое замечание о том, что можно сделать простую оптимизацию, которая покроет наиболее частые случаи. А сложный анализ пересечений оставить на потом. :)
То есть, берём полигоны по одному, и проверяем: либо очередной ни с кем не пересекается (и обрабатывается отдельно и просто), либо он пересекается хотя бы с одним другим, и тогда его откладываем в кучку к пересекаемому.
Потом обрабатываем те что были отложены как пересекающиеся. Первый обрабатываем просто так. А при обработке всех остальных проверяем, что бы тайл не попадал в уже обработанные пересекающиеся. Это конечно чуток замедлит, но в 95% реальных задач будет работать быстро и эффективно. Даже случай Европы с Азией обработается ИМХО достаточно быстро. |
|