SASGIS

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


View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0001877SAS.Планета[All Projects] Хотелкаpublic07-04-2013 15:4415-08-2015 15:13
ReporterPapazol 
Assigned Tozed 
PrioritynormalSeverityminorReproducibilityhave not tried
StatusresolvedResolutionfixed 
PlatformWindowsOSXPOS VersionProfessional SP3
Product Version121010 
Target Version150915Fixed in Version150915 
Summary0001877: Логические функции при работе с полигонами
DescriptionХотелось бы иметь возможность создавать выделение на основе двух и более полигонов, применяя к ним логические функции И, ИЛИ, НЕ.
Применения.
1. Имеем полигон, очерчивающий нужную нам область. Имеем другой полигон, очерчивающий снимок, часть которого попадает в нужную нам область, а другая часть - в соседнюю. Мы не хотим скачивать соседнюю область. Применяя к указанным полигонам функцию И, получаем выделение, находящееся в нужной области.
2. Имеем несколько полигонов, очерчивающих снимки. Применяя к ним функцию ИЛИ, можно скачать их все в одной сессии.
3. Имеем полигон, очерчивающий снимок, который мы не хотим перезакачивать. А вокруг всё обновилось. Применяя функцию И-НЕ, можно исключить из выделения область, которую не следует заменять.
Соответствующее применённой функции выделение должно быть окрашено в какой-либо цвет для исключения ошибок при выборе функции.
Выбор полигонов может быть через Shift либо Ctrl.
TagsVIP
Attached Files

- Relationships
related to 0001834resolvedzed Объединять несколько полигонов в одну метку 
parent of 0002048resolvedvdemidov Дырки в полигонах 
parent of 0002701closedvdemidov Научить "Операции с выделенной областью" обрабатывать мультиполигоны 
parent of 0002702closedvdemidov Сделать "Последнее выделение" (ILastSelectionInfo) мультиполигонным 

-  Notes
(0011038)
zed (manager)
07-04-2013 15:56

Добавлю, что в сорцах САСа уже есть библиотека для логических операций над полигонами: gpc - сейчас она используется для разбиения полигонов на треугольники для корректного подсчёта площади полигонов. Так что, далеко ходить и что-то искать не нужно.
Поддерживает функции:
- Difference
- Intersection
- Exclusive OR
- Union

Домашняя страничка либы: http://www.cs.man.ac.uk/~toby/gpc/
(0011039)
vdemidov (manager)
07-04-2013 19:37

Я только не могу понять, как она может работать для полигонов на сфере, не говоря уже об эллипсоиде.
(0011040)
zed (manager)
07-04-2013 19:40

Она работает на плоскости.
(0011041)
vdemidov (manager)
07-04-2013 20:15

А у нас полигоны на эллипсоиде.
(0011042)
zed (manager)
07-04-2013 20:29

Ну, представь, что она работает с проекциями на плоскость этих полигонов. Насколько там точно получается, судить не возьмусь, но площадь полигонов считает достаточно хорошо. А уж для задачи, описанной в тикете, точности будет за глаза.
(0011043)
vasketsov (manager)
07-04-2013 21:14

Всё равно раньше чем появятся дырки, половина этих операций будет бессмысленна, так как сас не сможет корректно сохранить результат.
(0011065)
vdemidov (manager)
11-04-2013 11:34

Даже без дырок часто эти операции будут приносить определенную пользу.
(0015801)
vasketsov (manager)
01-05-2015 09:08

Поглядел я на эту Generic Polygon Clipper.
Ощущения двоякие.
С одной стороны - она похоже что работает.
С другой стороны - это:
а) legacy shit типа procedure gpc_read_polygon(var f : text; - хотя возможно было бы использовать для сериализации геометрии в стрим;
б) различие в структуре хранения мультиполигонов с сасом, что приведёт к тормозам при "переконвертации" обратно (схожее только Tgpc_vertex, и на том спасибо);
в) постоянные Malloc и CFree, из-за чего очевидным образом будут тормоза, по сравнению с возможной реализацией типа DoublePointsAggregator.

И если с а) в общем-то проблем нет, то по остальному пока непонятно.

Поэтому у меня будет одна просьба и два вопроса.

Просьба - прикрутить счётчики производительности для операций gpc.

Вопрос первый - по конвертации мультиполигонов. Перегнать IGeometry в Tgpc_polygon труда не составляет, особенно с учётом того, что если вытащить ссылку на массив lonlat, перегонять память вообще не придётся, только заполнить ссылки в Tgpc_polygon. То есть, если немного поступиться и дать доступ к внутренности IGeometry либе gpc, падения по скорости при конвертации "туда" можно избежать. Проблемы касаются конвертации "обратно". Либа при выполнении gpc_polygon_clip нагадит в result_polygon целый такой contour и hole к нему в придачу. Возможно ли будет сохранить их как есть, а выполнить CFree при смерти объекта геометрии? Или обязательно придётся копировать буфера в памяти и звать CFree тут же? Или может проще пописать Malloc и CFree?

Вопрос второй - известны ли аналоги gpc, если скорость будет низкая, а переписать то что надо, не получится (по любой причине)?
(0015802)
zed (manager)
01-05-2015 09:18
edited on: 01-05-2015 09:18

Я ещё смотрю в сторону либы Clipper.

По тестам она на голову быстрее gpc, но работает с интами и полигоны придётся жестоко конвертировать туда-сюда. Из-за чего, всё быстродействие может сойти на нет.

(0015803)
vasketsov (manager)
01-05-2015 11:52

>но работает с интами
Это вообще не проблема, это либо вопрос времени на переконвертацию, либо вопрос внутреннего хранения lonlatarray внутри саса. В частности, я ж bounds храню в интах, проблем нет, миллиметровая ошибка для экватора всего лишь (глобальный множитель равен maxint/180, соответственно, умножаешь и округляешь - вот ты уже и в int-ах, а если локально с переконвертацией, так вообще ещё больше можно точность повысить увеличением этого множителя до maxint div abs(maxx - minx)).
А про внутреннее хранение - я к тому, что геометрию тоже можно хранить в интах, и "множитель" для деления. Ещё и память наэкономится. С отрисовкой только наверное проблемы будут.

>придётся жестоко конвертировать туда-сюда
Собственно, всеми правдами и неправдами хочется этого избежать. С другой стороны, если эту либу юзать только для операций с полигонами, то есть, когда юзеру их приспичит пообъединять, или итератор по сложному полигону запустить, или ещё чего этакое, это предположительно будут редкие операции. Так что может и не стоит бояться редкой переконвертации полигонов.
(0015804)
zed (manager)
02-05-2015 09:22

Эта либа как-то странно использует инты, и по дефолту там юзается int64. А на int32 введено ограничение:

//use_int32: When enabled 32bit ints are used instead of 64bit ints. This
//improve performance but coordinate values are limited to the range +/- 46340
//{$DEFINE use_int32}
(0015805)
vasketsov (manager)
02-05-2015 11:37

Подумал тут ещё про инты.
Да и ты меня такой вот инфой про 46340 просто добил.
Мне интуиция подсказывает, что либы на интах будут давать огромную погрешность, если речь будет касаться не геометрии на плоскости, а на поверхности сферы или эллипсоида.

Дело в том, что int в общем случае никак не привязать к координатам, ну ведь не от 0 до 180 же они на вход его принимают. Соответственно, интовая либа скорее всего устроена так, что результат её работы (F(x,y)) коммутативен операции параллельного переноса (L: {x -> x+a; y -> y+b}) по x и y. То есть, L(F(x,y)) = F(L(x,y)). Либо я тогда не представляю, как именно либа привязывается к началу координат и учитывает кривизну поверхности. А поскольку на проекции сферы или эллипсоида равенство L(F(x,y)) = F(L(x,y)) неверно, то будет ошибка.

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

Либа на даблах может считать, что экватор и нулевой меридиан соответствуют нулям x и y соответственно, поэтому такой проблемы может и не быть.

В общем, проверять надо интовые либы, например, на расчёте площади делением на треугольники, если такая операция там есть. Либо я чего-то не догоняю.
(0015821)
zed (manager)
03-05-2015 10:42

Залил в репо первую часть, касающуюся гуя. Добрался до момента отрисовки результатов слияния на карте. И появилось несколько вопросов.

Насколько я понимаю, мне нужно сделать аналог u_GeometryLonLatPolygonChangeableByLastSelection и добавить слой на основе TMapLayerSinglePolygon который и будет рисоваться на карте?

Меня вот несколько смущает название класса, где явно прописано, что он SinglePolygon и аналога с приставкой Multi у нас нету. Оно действительно Single и всё плохо?
(0015822)
vasketsov (manager)
03-05-2015 10:46

>действительно Single
Сейчас редактировать мультиполигоны можно. Просто мышкой таская вершины.
Single - потому что он один, а не потому что не мульти.
(0015823)
zed (manager)
03-05-2015 10:54

Вопрос же не про редактирование. Тут, на сколько я понимаю, просто рисуется статический полигон.
(0015824)
vasketsov (manager)
03-05-2015 12:05

Ну так он же рисуется при редактировании? Или я чего не понимаю?
(0015825)
zed (manager)
03-05-2015 12:14

LastSelection рисуется по готовому полигону. Сам полигон может изменяться, но не путём перетаскивания его вершин, а постфактум. Вот и мне нужно по готовому мультиполигону нарисовать статическую картинку, без всякой возможности к редактированию. Чисто для превью.
(0015832)
zed (manager)
04-05-2015 17:05
edited on: 04-05-2015 17:06

Замерил скорость работы с либой clipper и, в общем-то, я доволен. Потеря времени на конвертировании в инты и обратно, по сравнению с процессом слияния полигонов, стремится к нулю, и либа работает весьма быстро.

По поводу погрешности: если точки полигонов расположены далеко (разнесены на пол-мира), то есть ожидаемое смещение. На близких точках проблем не замечено.

Ждём поддержки дырок и тикет можно закрывать. Пока что дырки игнорируются, хотя они и фигурируют в статистике, по завершении процесса объединения. Сейчас сообщения о дырках можно рассматривать как предупреждение, что результат не совсем тот, что ожидался.

(0015856)
vasketsov (manager)
05-05-2015 13:30

Я правильно понимаю, что результат выполнения операции объединения кучки полигонов сейчас зависит от порядка их объединения?
А если всегда выполнять только попарно, то есть, первые два, потом к результату ещё один, и т. д. - зависимость от порядка объединения останется?
Известно, с чем конкретно связана данная зависимость, хотя бы идеи есть?

Если честно, то я предполагаю, что подобные нетривиальные тонкие материи и артефакты будут напрягать.

С gpc пробовал, или только clipper? А предвдущие версии clipper? А то вдруг они там свежего накосячили...
(0015857)
zed (manager)
05-05-2015 15:36

Переделал логику объединения полигонов. Теперь предварительно все clip полигоны объединяются (OR) и только потом выполняется основная операция с subject. При таком раскладе косяков не наблюдается. И это я видимо сразу не правильно понял логику работы с clipper-ом.

С gpc не пробовал, но он позволяет объединять только один subj с одним clip, т.е. и там, clip надо предварительно объединять.
(0015860)
zed (manager)
05-05-2015 18:49
edited on: 05-05-2015 18:51

Похоже, и полигоны в мультиполигонах нужно так же объединять между собой через OR, а не как сейчас. Иначе вылезут проблемы, если они там будут перекрывать друг друга.

(0015861)
vasketsov (manager)
05-05-2015 20:12

Я бы так сказал, что куски мультиполигонов должны обрабатываться в рамках этой функциональности как независимые полигоны. Независимо от наличия или отсутствия дырок. Данная логика основывается на том, что либа без понятия о том, каким образом мы храним мультиполигоны, как два полигона или как один с двумя геометриями. То бишь, на вход алгоритму должно попадать множество простых полигонов с дырками.
(0016366)
zed (manager)
09-08-2015 18:33

Появилась поддержка дырок в логических операциях. На первый взгляд, работает нормально. Жду отзывов и закрываем тикет.
(0016368)
vdemidov (manager)
10-08-2015 07:39

Кстати, а есть сейчас какой-то готовый способ полигон с дырками ставший мультиполигоном снова сделать полигоном с дырками?
(0016369)
zed (manager)
10-08-2015 09:04

Нету.
(0016374)
Papazol (reporter)
15-08-2015 13:53

Судя по количеству отзывов, тему следует закрывать?
(0016375)
zed (manager)
15-08-2015 13:56

Ну, я ждал отзыва прежде всего от вас лично. Всё-таки вы эту фичу заказывали, вам и карты в руки. Если замечаний нет, то закрою.
(0016377)
Papazol (reporter)
15-08-2015 15:07

Да, конечно, закрывайте.

- Users who viewed this issue
User List Anonymous (3630x), zed (15x), hrucker (1x), Ivan_Zykov (1x), Alexander (1x), tds878 (1x), Papazol (5x), vasketsov (1x), vdemidov (6x)
Total Views 3661
Last View 27-01-2022 15:32

- Issue History
Date Modified Username Field Change
07-04-2013 15:44 Papazol New Issue
07-04-2013 15:56 zed Note Added: 0011038
07-04-2013 19:37 vdemidov Note Added: 0011039
07-04-2013 19:40 zed Note Added: 0011040
07-04-2013 20:15 vdemidov Note Added: 0011041
07-04-2013 20:29 zed Note Added: 0011042
07-04-2013 21:14 vasketsov Note Added: 0011043
11-04-2013 11:34 vdemidov Note Added: 0011065
11-04-2013 11:34 vdemidov Status new => confirmed
11-04-2013 11:36 vdemidov Product Version .Nightly => 121010
11-04-2013 11:36 vdemidov Target Version => 27xxxx
26-07-2013 07:40 vasketsov Relationship added related to 0002048
25-04-2015 11:12 zed Relationship added related to 0001834
25-04-2015 11:53 zed Relationship added parent of 0002701
25-04-2015 11:54 zed Relationship added parent of 0002702
25-04-2015 11:58 zed Relationship replaced parent of 0002048
01-05-2015 07:25 zed Assigned To => zed
01-05-2015 07:25 zed Status confirmed => assigned
01-05-2015 09:08 vasketsov Note Added: 0015801
01-05-2015 09:18 zed Note Added: 0015802
01-05-2015 09:18 zed Note Edited: 0015802 View Revisions
01-05-2015 11:52 vasketsov Note Added: 0015803
02-05-2015 09:22 zed Note Added: 0015804
02-05-2015 11:37 vasketsov Note Added: 0015805
03-05-2015 10:42 zed Note Added: 0015821
03-05-2015 10:46 vasketsov Note Added: 0015822
03-05-2015 10:54 zed Note Added: 0015823
03-05-2015 12:05 vasketsov Note Added: 0015824
03-05-2015 12:14 zed Note Added: 0015825
04-05-2015 17:05 zed Note Added: 0015832
04-05-2015 17:06 zed Note Edited: 0015832 View Revisions
05-05-2015 13:23 Papazol Note Added: 0015854
05-05-2015 13:30 vasketsov Note Added: 0015856
05-05-2015 15:36 zed Note Added: 0015857
05-05-2015 18:45 zed Note Deleted: 0015854
05-05-2015 18:49 zed Note Added: 0015860
05-05-2015 18:51 zed Note Edited: 0015860 View Revisions
05-05-2015 20:12 vasketsov Note Added: 0015861
15-05-2015 20:00 vdemidov Tag Attached: VIP
09-08-2015 18:33 zed Note Added: 0016366
09-08-2015 18:33 zed Status assigned => feedback
10-08-2015 07:39 vdemidov Note Added: 0016368
10-08-2015 09:04 zed Note Added: 0016369
15-08-2015 13:53 Papazol Note Added: 0016374
15-08-2015 13:53 Papazol Status feedback => assigned
15-08-2015 13:56 zed Note Added: 0016375
15-08-2015 15:07 Papazol Note Added: 0016377
15-08-2015 15:13 zed Status assigned => resolved
15-08-2015 15:13 zed Fixed in Version => 150915
15-08-2015 15:13 zed Resolution open => fixed
15-08-2015 15:13 zed Target Version 27xxxx => 150915



Copyright © 2007 - 2022 SAS.Planet Team