|
Notes |
|
|
(0011038)
|
|
zed
|
|
07-04-2013 15:56
|
|
Добавлю, что в сорцах САСа уже есть библиотека для логических операций над полигонами: gpc - сейчас она используется для разбиения полигонов на треугольники для корректного подсчёта площади полигонов. Так что, далеко ходить и что-то искать не нужно.
Поддерживает функции:
- Difference
- Intersection
- Exclusive OR
- Union
Домашняя страничка либы: http://www.cs.man.ac.uk/~toby/gpc/ |
|
|
|
|
|
Я только не могу понять, как она может работать для полигонов на сфере, не говоря уже об эллипсоиде. |
|
|
|
(0011040)
|
|
zed
|
|
07-04-2013 19:40
|
|
|
Она работает на плоскости. |
|
|
|
|
|
А у нас полигоны на эллипсоиде. |
|
|
|
(0011042)
|
|
zed
|
|
07-04-2013 20:29
|
|
|
Ну, представь, что она работает с проекциями на плоскость этих полигонов. Насколько там точно получается, судить не возьмусь, но площадь полигонов считает достаточно хорошо. А уж для задачи, описанной в тикете, точности будет за глаза. |
|
|
|
|
|
Всё равно раньше чем появятся дырки, половина этих операций будет бессмысленна, так как сас не сможет корректно сохранить результат. |
|
|
|
|
|
Даже без дырок часто эти операции будут приносить определенную пользу. |
|
|
|
|
Поглядел я на эту 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
|
|
01-05-2015 09:18
|
|
Я ещё смотрю в сторону либы Clipper.
По тестам она на голову быстрее gpc, но работает с интами и полигоны придётся жестоко конвертировать туда-сюда. Из-за чего, всё быстродействие может сойти на нет.
|
|
|
|
|
>но работает с интами
Это вообще не проблема, это либо вопрос времени на переконвертацию, либо вопрос внутреннего хранения lonlatarray внутри саса. В частности, я ж bounds храню в интах, проблем нет, миллиметровая ошибка для экватора всего лишь (глобальный множитель равен maxint/180, соответственно, умножаешь и округляешь - вот ты уже и в int-ах, а если локально с переконвертацией, так вообще ещё больше можно точность повысить увеличением этого множителя до maxint div abs(maxx - minx)).
А про внутреннее хранение - я к тому, что геометрию тоже можно хранить в интах, и "множитель" для деления. Ещё и память наэкономится. С отрисовкой только наверное проблемы будут.
>придётся жестоко конвертировать туда-сюда
Собственно, всеми правдами и неправдами хочется этого избежать. С другой стороны, если эту либу юзать только для операций с полигонами, то есть, когда юзеру их приспичит пообъединять, или итератор по сложному полигону запустить, или ещё чего этакое, это предположительно будут редкие операции. Так что может и не стоит бояться редкой переконвертации полигонов. |
|
|
|
(0015804)
|
|
zed
|
|
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} |
|
|
|
|
Подумал тут ещё про инты.
Да и ты меня такой вот инфой про 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
|
|
03-05-2015 10:42
|
|
Залил в репо первую часть, касающуюся гуя. Добрался до момента отрисовки результатов слияния на карте. И появилось несколько вопросов.
Насколько я понимаю, мне нужно сделать аналог u_GeometryLonLatPolygonChangeableByLastSelection и добавить слой на основе TMapLayerSinglePolygon который и будет рисоваться на карте?
Меня вот несколько смущает название класса, где явно прописано, что он SinglePolygon и аналога с приставкой Multi у нас нету. Оно действительно Single и всё плохо? |
|
|
|
|
>действительно Single
Сейчас редактировать мультиполигоны можно. Просто мышкой таская вершины.
Single - потому что он один, а не потому что не мульти. |
|
|
|
(0015823)
|
|
zed
|
|
03-05-2015 10:54
|
|
|
Вопрос же не про редактирование. Тут, на сколько я понимаю, просто рисуется статический полигон. |
|
|
|
|
|
Ну так он же рисуется при редактировании? Или я чего не понимаю? |
|
|
|
(0015825)
|
|
zed
|
|
03-05-2015 12:14
|
|
|
LastSelection рисуется по готовому полигону. Сам полигон может изменяться, но не путём перетаскивания его вершин, а постфактум. Вот и мне нужно по готовому мультиполигону нарисовать статическую картинку, без всякой возможности к редактированию. Чисто для превью. |
|
|
|
(0015832)
|
|
zed
|
04-05-2015 17:05
(edited on: 04-05-2015 17:06) |
|
Замерил скорость работы с либой clipper и, в общем-то, я доволен. Потеря времени на конвертировании в инты и обратно, по сравнению с процессом слияния полигонов, стремится к нулю, и либа работает весьма быстро.
По поводу погрешности: если точки полигонов расположены далеко (разнесены на пол-мира), то есть ожидаемое смещение. На близких точках проблем не замечено.
Ждём поддержки дырок и тикет можно закрывать. Пока что дырки игнорируются, хотя они и фигурируют в статистике, по завершении процесса объединения. Сейчас сообщения о дырках можно рассматривать как предупреждение, что результат не совсем тот, что ожидался.
|
|
|
|
|
Я правильно понимаю, что результат выполнения операции объединения кучки полигонов сейчас зависит от порядка их объединения?
А если всегда выполнять только попарно, то есть, первые два, потом к результату ещё один, и т. д. - зависимость от порядка объединения останется?
Известно, с чем конкретно связана данная зависимость, хотя бы идеи есть?
Если честно, то я предполагаю, что подобные нетривиальные тонкие материи и артефакты будут напрягать.
С gpc пробовал, или только clipper? А предвдущие версии clipper? А то вдруг они там свежего накосячили... |
|
|
|
(0015857)
|
|
zed
|
|
05-05-2015 15:36
|
|
Переделал логику объединения полигонов. Теперь предварительно все clip полигоны объединяются (OR) и только потом выполняется основная операция с subject. При таком раскладе косяков не наблюдается. И это я видимо сразу не правильно понял логику работы с clipper-ом.
С gpc не пробовал, но он позволяет объединять только один subj с одним clip, т.е. и там, clip надо предварительно объединять. |
|
|
|
(0015860)
|
|
zed
|
05-05-2015 18:49
(edited on: 05-05-2015 18:51) |
|
Похоже, и полигоны в мультиполигонах нужно так же объединять между собой через OR, а не как сейчас. Иначе вылезут проблемы, если они там будут перекрывать друг друга.
|
|
|
|
|
|
Я бы так сказал, что куски мультиполигонов должны обрабатываться в рамках этой функциональности как независимые полигоны. Независимо от наличия или отсутствия дырок. Данная логика основывается на том, что либа без понятия о том, каким образом мы храним мультиполигоны, как два полигона или как один с двумя геометриями. То бишь, на вход алгоритму должно попадать множество простых полигонов с дырками. |
|
|
|
(0016366)
|
|
zed
|
|
09-08-2015 18:33
|
|
|
Появилась поддержка дырок в логических операциях. На первый взгляд, работает нормально. Жду отзывов и закрываем тикет. |
|
|
|
|
|
Кстати, а есть сейчас какой-то готовый способ полигон с дырками ставший мультиполигоном снова сделать полигоном с дырками? |
|
|
|
(0016369)
|
|
zed
|
|
10-08-2015 09:04
|
|
|
|
|
|
|
Судя по количеству отзывов, тему следует закрывать? |
|
|
|
(0016375)
|
|
zed
|
|
15-08-2015 13:56
|
|
|
Ну, я ждал отзыва прежде всего от вас лично. Всё-таки вы эту фичу заказывали, вам и карты в руки. Если замечаний нет, то закрою. |
|
|
|
|
|