Arrange line segments consecutively to make a polygon

Question

Im trying to arrange line segments to create a closed polygon with python. At the moment I've managed to solve it but is really slow when the number of segments increase (its like a bubble sort but for the end point of segments). I'm attaching a sample file of coordinates (the real ones are really complex but is useful for testing purposes). The file contains the coordinates for the segments of two separetes closed polygons. The image below is the result of the coordinates I've attached.

This is my code for joining the segments. The file 'Curve' is in the dropbox link above:

from ast import literal_eval as make_tuple
from random import shuffle
from Curve import Point, Curve, Segment

def loadFile():
    print 'Loading File'
    file = open('myFiles/coordinates.txt','r')
    for line in file:
        pairs.append(make_tuple(line))
    file.close()

def sortSegment(segPairs):
    polygons = []
    segments = segPairs

    while (len(segments) > 0):
        counter = 0
        closedCurve = Curve(Point(segments[0][0][0], segments[0][0][1]), Point(segments[0][1][0], segments[0][1][1]))
        segments.remove(segments[0])
        still = True

        while (still):
            startpnt = Point(segments[counter][0][0], segments[counter][0][1])
            endpnt = Point(segments[counter][1][0], segments[counter][1][1])
            seg = Segment(startpnt, endpnt)
            val= closedCurve.isAppendable(seg)

            if(closedCurve.isAppendable(seg)):

                if(closedCurve.isClosed(seg)):
                    still =False
                    polygons.append(closedCurve.vertex)
                    segments.remove(segments[counter])

                else:
                    closedCurve.appendSegment(Segment(Point(segments[counter][0][0], segments[counter][0][1]), Point(segments[counter][1][0], segments[counter][1][1])))
                    segments.remove(segments[counter])
                    counter = 0

            else:
                counter+=1
                if(len(segments)<=counter):
                    counter = 0

    return polygons

def toTupleList(list):
    curveList = []
    for curve in list:
        pointList = []
        for point in curve:
            pointList.append((point.x,point.y))
        curveList.append(pointList)

    return curveList

def convertPolyToPath(polyList):
    path = []
    for curves in polyList:
        curves.insert(1, 'L')
        curves.insert(0, 'M')
        curves.append('z')
        path = path + curves
    return path

if __name__ == '__main__':

    pairs =[]
    loadFile();


    polygons = sortSegment(pairs)
    polygons = toTupleList(polygons)
    polygons = convertPolyToPath(polygons)

Answer 1

Assuming that you are only looking for the approach and not the code, here is how I would attempt it.

While you read the segment coordinates from the file, keep adding the coordinates to a dictionary with one coordinate (string form) of the segment as the key and the other coordinate as the value. At the end, it should look like this:

{
    '5,-1': '5,-2',
    '4,-2': '4,-3',
    '5,-2': '4,-2',
    ...
}

Now pick any key-value pair from this dictionary. Next, pick the key-value pair from the dictionary where the key is same as the value in the previous key-value pair. So if first key-value pair is '5,-1': '5,-2', next look for the key '5,-2' and you will get '5,-2': '4,-2'. Next look for the key '4,-2' and so on.

Keep removing the key-value pairs from the dictionary so that once one polygon is complete, you can check if there are any elements left which means there might be more polygons.

Let me know if you need the code as well.

Answer 2

I had to do something similar. I needed to turn coastline segments (that were not ordered properly) into polygons. I used NetworkX to arrange the segments into connected components and order them using this function.

It turns out that my code will work for this example as well. I use geopandas to display the results, but that dependency is optional for the original question here. I also use shapely to turn the lists of segments into polygons, but you could just use CoastLine.rings to get the lists of segments.

I plan to include this code in the next version of PyRiv.

from shapely.geometry import Polygon
import geopandas as gpd
import networkx as nx

class CoastLine(nx.Graph):
    def __init__(self, *args, **kwargs):
        """
        Build a CoastLine object.

        Parameters
        ----------

        Returns
        -------
          A CoastLine object
        """
        self = super(CoastLine, self).__init__(*args, **kwargs)

    @classmethod
    def read_shp(cls, shp_fn):
        """
        Construct a CoastLine object from a shapefile.
        """
        dig = nx.read_shp(shp_fn, simplify=False)
        return cls(dig)

    def connected_subgraphs(self):
        """
        Get the connected component subgraphs. See the NetworkX
        documentation for `connected_component_subgraphs` for more
        information.
        """
        return nx.connected_component_subgraphs(self)

    def rings(self):
        """
        Return a list of rings. Each ring is a list of nodes. Each
        node is a coordinate pair.
        """
        rings = [list(nx.dfs_preorder_nodes(sg)) for sg in self.connected_subgraphs()]
        return rings

    def polygons(self):
        """
        Return a list of `shapely.Polygon`s representing each ring.
        """
        return [Polygon(r) for r in self.rings()]

    def poly_geodataframe(self):
        """
        Return a `geopandas.GeoDataFrame` of polygons.
        """
        return gpd.GeoDataFrame({'geometry': self.polygons()})

With this class, the original question can be solved:

edge_list = [
    ((5, -1), (5, -2)),
    ((6, -1), (5, -1)),
    ((1, 0), (1, 1)),
    ((4, -3), (2, -3)),
    ((2, -2), (1, -2)),
    ((9, 0), (9, 1)),
    ((2, 1), (2, 2)),
    ((0, -1), (0, 0)),
    ((5, 0), (6, 0)),
    ((2, -3), (2, -2)),
    ((6, 0), (6, -1)),
    ((4, 1), (5, 1)),
    ((10, -1), (8, -1)),
    ((10, 1), (10, -1)),
    ((2, 2), (4, 2)),
    ((5, 1), (5, 0)),
    ((8, -1), (8, 0)),
    ((9, 1), (10, 1)),
    ((8, 0), (9, 0)),
    ((1, -2), (1, -1)),
    ((1, 1), (2, 1)),
    ((5, -2), (4, -2)),
    ((4, 2), (4, 1)),
    ((4, -2), (4, -3)),
    ((1, -1), (0, -1)),
    ((0, 0), (1, 0)) ]

eG = CoastLine()

for e in edge_list:
    eG.add_edge(*e)

eG.poly_geodataframe().plot()

This will be the result: