4

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.

1

1 Answer 1

10

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))

result1


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))

result2

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))

result3


References:

7
  • The result is always the bad polygon (self-intersected)
    – gene
    Feb 11 at 10:10
  • True, did I misunderstand the question?
    – Taras
    Feb 11 at 10:11
  • Yes, he wants the concave hull of the points (Alpha shape)
    – gene
    Feb 11 at 10:15
  • 1
    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 at 13:42
  • 1
    @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))`` from networkx 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 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.