Это простой и довольно распространенный вопрос, который уже задавался для разных целей (см. , Например, эту ссылку и это тоже ), но здесь мы ищем не программный пакет, а алгоритмы, которые мы могли бы попытаться реализовать, скажем, в Python .
Итак, как показано ниже, набор линий отображается (они уже обрезаны, кстати).
Алгоритмы / идеи для генерации полигонов (как показано красным) ?
algorithm
polygonize
geometry-conversion
разработчик
источник
источник
Ответы:
Ну, мы поместили здесь ответ, который не является полным ответом на наш вопрос, то есть вопрос останется « открытым для ответа ». Это, однако, решение проблемы в вопросе. Вот трюк, который мы использовали:
Сначала давайте посмотрим результаты :
Таким образом, данные линии в
leftпостроенных полигонах показаны вmiddle. Они настоящие многоугольники, как показано вright;)Для приведенного ниже алгоритма мы использовали
Shapelyпакет в Python .MultiLineString{:: M}buffer, скажем,eps{:: MB}Polygon{:: P} (регион здесь квадрат)P.difference(MB){получившиеся полигоны}Обратите внимание, что он работает тихо и быстро. Однако упущение заключается в том, что алгоритм не является оригинальным методом построения многоугольника из линий . Тем не менее, это отлично сработало для проблемы, которую мы имели в наших руках.
источник
JTS Topology Suite имеет класс Polygonizer, который в значительной степени делает это.
Вы можете взглянуть на исходный код, доступный здесь , и преобразовать его в Python.
источник
Вы можете взглянуть на пакет Python Shapely, в частности, polygonize ()
источник
from shapely.ops import polygonize) использует GEOS.Polygonize из GEOS . Так что это ссылка, где есть ссылка на ссылку ...: |polygonizeне увенчались успехом. Однако спасибо, что напомнили нам,Shapelyс помощью которого мы могли бы найти решение (трюк, на самом деле) в виде ответа.Вот еще одно решение, которое мы могли бы найти.
Для Python есть пакет {здесь} . Это крошечная реализация с некоторыми ошибками. Тем не менее, с некоторыми усилиями он может быть использован для этой проблемы. Также обратите внимание на следующие этапы:
Этап предварительной обработки, с помощью которого обнаруживаются все пересечения между линиями. Тогда соответственно все линии разбиваются на отрезки в точках взаимодействия. Список точек пересечения и список связанных ребер необходимы для DCEL.
источник
differenceоперация.