Converting lines (edges) to polygons with Python

Question

Is there any working function to convert lines (edges) to polygons with Python or I need to implement it myself?

I have pairs of points - edges:

[[10464, 27071],
 [22358, 15839],
 [10464, 24781],
 [24781, 22358],
 [19888, 27071],
 [30361, 19784],
 [19784, 19888],
 [30361, 15839]]

which definitely are in a looping manner - they have their coordinates.

Placing them on paper a polygon is visible, because each point have some pair in the set, but couldn't find any algorithm to draw proper shape. This is not ambiguous. Shapely for example forces me to use convex or concave but I don't need to use it, because the shape is already determined with this lines. Networkx didn't solve topological order of neighboring nodes as well.

This code:

poly = geometry.Polygon([[p[0], p[1]] for p in cxy])
x,y = poly.exterior.xy
plt.plot(x,y)

draws bad polygon (self-intersected) because the order of points is not right, but labels are straightly saying what it should be.

Please, do not forget about "What should I do when someone answers my question?" — Taras, Apr 06 '22 at 06:14

Taras · Answer 1 · 2022-02-24T10:19:35.060

I will firstly start with your code. There is no need to manipulate the list with lists of coordinates, as you did it with geometry.Polygon([[p[0], p[1]] for p in cxy]). The class Polygon(shell[, holes=None]) can accept it straight, as mentioned in the documentation:

The Polygon constructor takes two positional parameters. The first is an ordered sequence of (x, y[, z]) point tuples and is treated exactly as in the LinearRing case. The second is an optional unordered sequence of ring-like sequences specifying the interior boundaries or “holes” of the feature.

So, you can do the following:

from shapely.geometry import Polygon
list_with_coords = 

    [[10464, 27071],
    [22358, 15839],
    [10464, 24781],
    [24781, 22358],
    [19888, 27071],
    [30361, 19784],
    [19784, 19888],
    [30361, 15839]]
p = Polygon(list_with_coords)
print(p)

which results in:

POLYGON ((10464 27071, 22358 15839, 10464 24781, 24781 22358, 19888 27071, 30361 19784, 19784 19888, 30361 15839, 10464 27071))

Secondly to achieve the desired output, one can start with inspecting the Alpha Shape Toolbox package and considering one of these approaches.

Approach 1 : A Convex Hull

The convex hull, a shape resembling what you would see if you wrapped a rubber band around pegs at all the data points, is an alpha shape where the alpha parameter is equal to zero.

import alphashape
list_with_coords = 

    [[10464, 27071],
    [22358, 15839],
    [10464, 24781],
    [24781, 22358],
    [19888, 27071],
    [30361, 19784],
    [19784, 19888],
    [30361, 15839]]
alpha_shape = alphashape.alphashape(list_with_coords, alpha=0)
print(alpha_shape)

which results in the :

POLYGON ((22358 15839, 10464 24781, 10464 27071, 19888 27071, 30361 19784, 30361 15839, 22358 15839))

Approach 2 : An Alpha shape a.k.a. A Concave Hull

Also as was mentioned by @gene to find an optimal Alpha Value

The alpha parameter can be solved for if it is not provided as an argument, but with large datasets, this can take a long time to calculate.

import alphashape
list_with_coords = 

    [[10464, 27071],
    [22358, 15839],
    [10464, 24781],
    [24781, 22358],
    [19888, 27071],
    [30361, 19784],
    [19784, 19888],
    [30361, 15839]]
alpha_shape = alphashape.alphashape(list_with_coords)
print(alpha_shape)

which results in:

POLYGON ((10464 27071, 19888 27071, 24781 22358, 30361 19784, 30361 15839, 22358 15839, 19784 19888, 10464 24781, 10464 27071))

References:

Your result is the simple convex hull of the points, you need to modify the alpha value to get a concave hull — gene, Feb 11 '22 at 12:49
True! With this parameter alpha=0.5 currently getting this : C:\TempDaten\...\lib\site-packages\shapely\ops.py:42: ShapelyDeprecationWarning: Iteration over multi-part geometries is deprecated and will be removed in Shapely 2.0. Use the geoms property to access the constituent parts of a multi-part geometry. source = iter(source) GEOMETRYCOLLECTION EMPTY issue — Taras, Feb 11 '22 at 12:51
Use alphashape.alphashape(list_with_coords) ('the alpha parameter can be solved for if it is not provided as an argument' In Pypi:alphashape ) — gene, Feb 11 '22 at 13:42
@Taras Generally your solution leads to right answer(s). But there's no need to treat it that way, because edges are just ready to bring together - just they need to be sorted like domino. With some help from other guy I found this is an Euler path. Resolved this with list(nx.eulerian_circuit(G))`` fromnetworkx` package. I was asking whether or not there's some package to just load these edges to be resolved automatically this way. It seems I guess, the concave solution makes the same thing. — Peter.k, Feb 11 '22 at 16:58

Converting lines (edges) to polygons with Python

1 Answers1

Approach 1 : A Convex Hull

Approach 2 : An Alpha shape a.k.a. A Concave Hull

Linked