Creating a progressive list iteration in Python

Question

I have a list containing lines(geometry). Those lines make up multiple shapes(square, rectangle etc). However, they are exploded and i am trying to think of a way to group them together into separate lists by shape they make. For example if my lists contains 8 lines and i know there are two rectangular shapes that they make i want to create two groups of four lines each. Now, i can query each line for StartPoint() and EndPoint(). I was thinking about setting up a loop that will cycle through the list. Pick first line on the list. Get its end point and then check if its equal to any of the start points of the rest of lines in the list. if it is then add that line to the list with the first one. then take that second line and do the same thing until line's start point is equal to last lines end point and first lines start point is equal to its end point. How would i do it?

lines = [line1, line2, line3, line4, line5, line6, line7] #that means i have a square and a triangle
for i in lines:
    shape1.append(lines[0])
    sPoint = lines[0].StartPoint()
    ePoint = lines[0].EndPoint()
    if i.StartPoint() == ePoint:
        shape1.append(i)

I am not sure how to automate the creation of "shape" lists and how to break the loop so that i dont run in circles.

Any help will be appreciated. Thank you,

Answer 1

As with @ChristophHegemann's idea, just imagine that numbers are actually just a representation for points, so Line(1,4) or Edge(1,4) in my case is just a line between point 1 and point 4.

from pprint import pprint

class Edge(object):
    def __init__(self,a,b):
        self.a        = a
        self.b        = b
        self.previous = None
        self.next     = None

    def __repr__(self):
        return "<Edge(%s,%s)>" % (self.a,self.b)

def find_shapes(lines):
    # builds the graph
    lines  = link_lines(lines)
    # explores the graph
    shapes = extract_shapes(lines)
    return shapes    

def link_lines(lines):
    # keep a safe copy of the list of lines. The original list will be tampered with.
    lines_copy = list(lines)

    for L in lines_copy:
        lines.remove(L)
        for line in lines:
            # if current line's end is other line's start
            if L.b == line.a:
                L.next        = line
                line.previous = L

            # if current line's start is other line's end
            elif L.a == line.b:
                L.previous = line
                line.next  = L

            # if we found both the previous and the next edge then we're done for this edge.
            # (edge has at most 1 previous and 1 next edge in a given shape).
            # this of course supposes that any single edge is present in at most one shape.

            if L.previous and L.next :
                break

        #put L back in
        lines.append(L)

    # return newly linked lines (graph)
    return lines

def extract_shapes(lines):
    lines_copy = list(lines)
    shapes     = []
    while lines_copy : 
        L         = lines_copy.pop()
        shape     = [L]
        next_edge = L.next
        # unlike @ChristophHegemann I work with edges, but the algorithm seems 
        # to be the same whether you work with edges or vertices
        while next_edge != L:
            shape.append(next_edge)
            lines_copy.remove(next_edge)            
            next_edge = next_edge.next

        shapes.append(shape)
    return shapes

# list of lines
# let's pretend shapes are : L1,L10,L2,L4 and L5,L3,L7,L11 and L6,L9,L8,L12

L1  = Edge(1,2)
L10 = Edge(2,3)
L2  = Edge(3,4)
L4  = Edge(4,1)

L5  = Edge(5,6)
L3  = Edge(6,7)
L7  = Edge(7,8)
L11 = Edge(8,5)

L6  = Edge(9,10)
L9  = Edge(10,11)
L8  = Edge(11,12)
L12 = Edge(12,9)

# random order of lines 
lines = [L1,L2,L3,L4,L5,L6,L7,L8,L9,L10,L11,L12]

pprint(find_shapes(lines))

# chaouche@karabeela ~/CODE/TEST/PYTHON/SO $ python lines.py
# [[<Edge(12,9)>, <Edge(9,10)>, <Edge(10,11)>, <Edge(11,12)>],
#  [<Edge(8,5)>, <Edge(5,6)>, <Edge(6,7)>, <Edge(7,8)>],
#  [<Edge(2,3)>, <Edge(3,4)>, <Edge(4,1)>, <Edge(1,2)>]]
# chaouche@karabeela ~/CODE/TEST/PYTHON/SO $

Answer 2

Preliminaries

First, let's define a line class, which contains the coordinates of 2 points:

import itertools
import random

class line(object) :
    """
    A line has 2 ends.
    """
    def __init__(self, tup0, tup1 ) :
        self.tup0 = tup0
        self.tup1 = tup1

    def __repr__( self ) :
        return "line[{0}, {1}]".format( self.tup0, self.tup1 )

    def StartPoint(self) :
        return self.tup0

    def EndPoint(self):
        return self.tup1

    def reverseLine(self) :
        return line( self.tup1, self.tup0 )

Solution

I simply enumerate all possible shapes (valid or not) until I find 2 closed shapes:

• I enumerate all possible 2-way partitions of the list of lines
• each cluster of a given partition is a possible shape. To actually verify that, I enumerate all possible permutations of the order of lines in the cluster (as well as all possible orderings of the ending points of each line)
• once I have found a partition which verifies our criteria (i.e., each cluster is a closed shape), I print the solution and stop

Here are the helpers:

def is_closed( lines ) :
    """
    Return True if lines represents a closed shape (i.e., order matters)
    """
    are0ToNConnected = all( l.tup1 == lines[i+1].tup0 for i,l in enumerate( lines[:-1] ) ) 
    areFirstAndLastConnected = ( lines[-1].tup1 == lines[0].tup0 )
    return are0ToNConnected and areFirstAndLastConnected

def is_any_closed( lines ) :
    """
    Return True if at least one re-ordering of lines represents a closed shape (i.e., order doesnt matter)
    """
    return any( is_closed(newLines) 
               for permutedLines in itertools.permutations( lines ) 
               for newLines in itertools.product( * [ ( l, l.reverseLine() ) for l in permutedLines ] ) )

def k_way_partition( A, k ) :
    """
    Generator for all k-way partitions of A
    """
    if k == 1 :
        yield [ A ]
    elif len(A) == k :
        yield [ [ a ] for a in A ]
    else :
        for partition in k_way_partition( A[1:], k ) : # add new element to one of the current clusters
            for i, cluster in enumerate( partition ) :
                yield partition[:i] + [ cluster + [ A[0] ] ] + partition[i+1:]
        for partition in k_way_partition( A[1:], k-1 ) : # add new element to a new cluster
            yield [ [ A[0] ] ] + partition

And this is the main function:

def find_shapes( lines, k ) :
    """
    Looks for a partition of lines into k shapes, and print the solution if there is one.
    """
    for partition in k_way_partition( lines, k ) :
        if all( is_any_closed(cluster) for cluster in partition ) : # we found a solution
            for j, cj in enumerate( partition ) :
                print "shape {}: {}".format(j, cj )
            break

Example

Let's generate random data and try the solution:

# square
lines = [ line( (0,0), (0,1) ) ]
lines.append( line( (0,1), (1,1) ) )
lines.append( line( (1,1), (1,0) ) )
lines.append( line( (1,0), (0,0) ) )
# triangle
lines.append( line( (2,2), (2,3) ) )
lines.append( line( (2,3), (3,2) ) )
lines.append( line( (3,2), (2,2) ) )
lines

random.shuffle( lines )  # randomize the order of lines
for i, l in enumerate( lines ) :
    if random.random() < 0.5 :
        lines[i] = l.reverseLine()  # randomize order of coordinates
lines

Out[8]:

[line[(0, 1), (1, 1)],
 line[(1, 1), (1, 0)],
 line[(2, 2), (2, 3)],
 line[(0, 0), (1, 0)],
 line[(3, 2), (2, 2)],
 line[(3, 2), (2, 3)],
 line[(0, 0), (0, 1)]]

Now let's run our solution on the random data:

find_shapes( lines, 2 )
shape 0: [line[(3, 2), (2, 3)], line[(3, 2), (2, 2)], line[(2, 2), (2, 3)]]
shape 1: [line[(0, 0), (0, 1)], line[(0, 0), (1, 0)], line[(1, 1), (1, 0)], line[(0, 1), (1, 1)]]

It works!

Answer 3

If you take some time and abstract your problem you will see that you're really just doing Graphs.

Graphs consist of Vertices and Edges. Where Vertices are your starting and endpoints.

I wrote a piece of Code that should help you solve your Problem once you understand how to convert your Data into the suggested format.

Annotation:

I suggest you read up on the builtin type set() while reading my Code.

vertices = set(['A', 'C', 'B', 'E', 'D', 'G', 'F'])

#think of this as Line1.StartPoint()='A' Line1.EndPoint()='B' ... 
edges = {'A': 'B',
         'B': 'C',
         'C': 'D',
         'D': 'A',
         'E': 'F',
         'F': 'G',
         'G': 'E'}

shapes = set()

#Check if we tested all edges
while len(vertices) is not 0:
    next = vertices.pop()
    shape = set()
    while next not in shape:
        shape.add(next)
        next = edges[next]
    shapes.add(frozenset(shape))

print shapes

results in:

>>set([frozenset(['A', 'C', 'B', 'D']), frozenset(['E', 'G', 'F'])])

Edit: Major speedups are possible but for the sake of simplicity left out.

Answer 4

Not really the best algorithm, but I'm sleepy, and this should get you started:

lines = [line1, line2, line3, line4, line5, line6, line7]
shapes = []

while lines:
    shape = [lines[0]]
    i=1
    while i < len(lines):
        line1 = lines[i]
        for line2 in lines[i+1:]:
            if line2.start == line1.end or line2.end == line1.start or \
               line2.start == line1.start or line2.end == line1.end:

                shape.append(line2)
                lines.pop(i)
                i -= 1
                if line2.end == shape[0].start or line2.start == shape[0].end or \
                   line2.end == shape[0].end or line2.start == shape[0].start:

                    shapes.append(shape)
                    shape = []
        i += 1

To improve upon this, try sorting the lines by start and end points, and do a binary search for connecting lines