SASGIS

Веб-картография и навигация


View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0001894SAS.Планета[All Projects] Хотелкаpublic24-04-2013 18:0807-05-2013 07:47
Reportervasketsov 
Assigned To 
PrioritynormalSeveritymajorReproducibilityN/A
StatusconfirmedResolutionopen 
PlatformWindowsOSVistaOS VersionUltimate
Product Version121010 
Target Version26xxxxFixed in Version 
Summary0001894: Оптимизация итератора тайлов для мультиполигонов
DescriptionПоскольку элементарные полигоны в мультиполигоне могут пересекаться, нельзя просто так взять и пройти по каждому из них, в этом случае некоторые тайлы могут быть перечислены дважды и более. Поэтому пока что анализируется общий полигон, ограничивающий все полигончики.

Судя по всему, оптимальнее всего будет разбить полигоны внутри мультиполигона на максимальный набор множеств полигонов так, чтобы пересекались только полигоны внутри одного множества. Соответственно если полигон ни с кем не пересекается, то он в своём множестве будет один. А потом запустить итератор по каждому множеству по отдельности. А там где более одного - ходить по Bounds отдельных полигонов + строить массив обработанных XY и проверкой по нему исключать повторы в пересечениях.

Думается, что искать "честное" объединение полигонов (через gpc или как там либа зовётся) будет более долго.

А то может вообще подумать на тему того, чтобы сразу при хранении мультиполигонов в памяти внутри ужЕ иметь информацию о делении полигонов на непересекающиеся подмножества.
TagsNo tags attached.
Attached Files

- Relationships
related to 0002701closedvdemidov Научить "Операции с выделенной областью" обрабатывать мультиполигоны 

-  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 (2081x), vdemidov (5x)
Total Views 2086
Last View 28-03-2024 11:02

- 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



Copyright © 2007 - 2024 SAS.Planet Team