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.

Answer 1

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:

• Real Python | Lists and Tuples in Python
• Creating single polygon from GPS coordinates and finding its area with Python