View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0001894 | SAS.Планета | Хотелка / Feature request | public | 24-04-2013 18:08 | 07-05-2013 07:47 |
| Reporter | vasketsov | Assigned To | |||
| Priority | normal | Severity | major | Reproducibility | N/A |
| Status | confirmed | Resolution | open | ||
| Platform | Windows | OS | Vista | OS Version | Ultimate |
| Product Version | 121010 | ||||
| Target Version | 42xxxx | ||||
| Summary | 0001894: Оптимизация итератора тайлов для мультиполигонов | ||||
| Description | Поскольку элементарные полигоны в мультиполигоне могут пересекаться, нельзя просто так взять и пройти по каждому из них, в этом случае некоторые тайлы могут быть перечислены дважды и более. Поэтому пока что анализируется общий полигон, ограничивающий все полигончики. Судя по всему, оптимальнее всего будет разбить полигоны внутри мультиполигона на максимальный набор множеств полигонов так, чтобы пересекались только полигоны внутри одного множества. Соответственно если полигон ни с кем не пересекается, то он в своём множестве будет один. А потом запустить итератор по каждому множеству по отдельности. А там где более одного - ходить по Bounds отдельных полигонов + строить массив обработанных XY и проверкой по нему исключать повторы в пересечениях. Думается, что искать "честное" объединение полигонов (через gpc или как там либа зовётся) будет более долго. А то может вообще подумать на тему того, чтобы сразу при хранении мультиполигонов в памяти внутри ужЕ иметь информацию о делении полигонов на непересекающиеся подмножества. | ||||
| Tags | No tags attached. | ||||
|
|
У каждого полигона в мультиполигоне есть ограничивающий его прямоугольник. Для наиболее массового случая, когда эти прямоугольники не пересекаются, вполне можно итерировать по каждому из полигонов отдельно. |
|
|
Собственно об этом второй параграф и повествует )) Реализация очевидна: берём полигоны по одному, и проверяем: либо очередной ни с кем не пересекается (и обрабатывается отдельно и просто), либо он пересекается хотя бы с одним другим, и тогда его откладываем в кучку к пересекаемому. После первого этапа получим обработанные все отдельные полигоны + отдельные множества из 2-х и более полигонов каждое. И кодится это чуть более просто, чем тривиально. Самое интересное потом: как быстро оставшиеся множества обойти, и чтобы все тайлы в списке не хранить для сверки, а то и по скорости и по памяти это будет убийственным. Если например некто выделит отдельно европу и отдельно азию, и перекроет полигоны хотя бы на один тайл, на приличных зумах будет сильно больно. Надо как-то анализировать характер пересечения множеств. Даже выполнение их сложения (и работа с суммой множеств после этого) может как ускорить весь процесс, так и замедлить. |
|
|
А мое замечание о том, что можно сделать простую оптимизацию, которая покроет наиболее частые случаи. А сложный анализ пересечений оставить на потом. :) То есть, берём полигоны по одному, и проверяем: либо очередной ни с кем не пересекается (и обрабатывается отдельно и просто), либо он пересекается хотя бы с одним другим, и тогда его откладываем в кучку к пересекаемому. Потом обрабатываем те что были отложены как пересекающиеся. Первый обрабатываем просто так. А при обработке всех остальных проверяем, что бы тайл не попадал в уже обработанные пересекающиеся. Это конечно чуток замедлит, но в 95% реальных задач будет работать быстро и эффективно. Даже случай Европы с Азией обработается ИМХО достаточно быстро. |
| 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 | => 42xxxx |
| 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 |
| 08-08-2025 13:24 | zed | Category | Хотелка => Хотелка / Feature request |