0001877: Логические функции при работе с полигонами

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 (4555x), zed (15x), hrucker (1x), Ivan_Zykov (1x), Alexander (1x), tds878 (1x), Papazol (5x), vasketsov (1x), vdemidov (6x)
Total Views	4586
Last View	21-11-2024 18:10

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

SASGIS