Iterating a Progressive List in Python
I have a list that contains strings (geometry). These lines make up several shapes (square, rectangle, etc.). However, they are blown up and I am trying to come up with a way to group them together into separate lists according to the shape they do. For example, if my lists contain 8 lines and I know there are two rectangular shapes they do, I want to create two groups of four lines. Now I can query each line for StartPoint () and EndPoint (). I was thinking about setting up a loop that will loop through the list. Select the first line in the list. Get your ending point, then check if it matches any of the starting points of the rest of the lines in the list. if it then adds that line to the list from the first. then take the second line and do the same untiluntil the start point of the line is equal to the end point of the last line, and the start point of the first line is equal to its end point. How should 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'm not sure how to automate the creation of curly lists and how to break the loop so that I don't work in circles.
Any help would be appreciated. Thank,
source to share
If you take some time and distract your problem, you will see that you are really just making graphs.
Graphs are made up of vertices and edges. Where vertices are your starting and ending points.
I wrote a piece of code to help you solve your problem once you figure out how to convert your data to the suggested format.
Annotation:
I suggest you read the built-in typeset () while reading the 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
leads to:
→ set ([frozenset (['A', 'C', 'B', 'D']), frozenset (['E', 'G', 'F'])])
Edit: Major speedups are possible, but left out for simplicity.
source to share
Not 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 this, try sorting the strings by start and end points and do a binary search to concatenate the strings
source to share
Qualifying
First, let's define a class line
that contains the coordinates of two 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 )
Decision
I just list all the possible forms (valid or not) until I find 2 closed forms:
- I am listing all the possible two-way sections of a string list
- each cluster in a given section is a possible shape. To verify this, I list all the possible permutations of the row ordering in the cluster (as well as all the possible endpoint orderings of each row)
- Once I found the section that checks our criteria (i.e. each cluster is a closed form), 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 some 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
From [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 run our solution on 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!
source to share
I'm not sure how to automate the creation of "form" lists and how to break the loop so that I don't work in circles.
One form at a time :-). Your current code goes through all lines and checks if each line starts where the first line ends. It doesn't match any string other than the first.
For testing purposes, I created a Line class.
class Line(object):
def __init__(self, Start, End):
self.Start = Start
self.End = End
def StartPoint(self):
return self.Start
def EndPoint(self):
return self.End
And some dummy data:
# Rectangle
line1 = Line((0,0),(0,2))
line2 = Line((0,2),(5,2))
line3 = Line((5,0),(5,2))
line4 = Line((0,0),(5,0))
# Triangle
line5 = Line((10,10),(7,10))
line6 = Line((7,6),(7,10))
line7 = Line((10,10),(7,6))
lines = set((line1, line2, line3, line4, line5, line6, line7))
Here's my approach:
- Select a string from the set to start with, place it in our queue
- Remove the line from the queue and find all the lines that share the endpoint with our line, placing them in the queue to go to later
- Remove the lines we put in our queue from the lineset
- If there are still things in the queue, go back to step 2.
- If the queue is empty, we have the full shape in the shape list and go to step 1
...
def Group_Lines(Line_List):
'''
Returns a list of lists, each sub list contains all lines connected at
vertices
'''
Grouped_Lines = []
Queue = set()
while Line_List:
Shape = []
Queue.add(Line_List.pop()) # Move a line from the Line_List to our queue
while Queue:
Current_Line = Queue.pop()
Shape.append(Current_Line)
for Potential_Match in Line_List:
Points = (Potential_Match.StartPoint(),
Potential_Match.EndPoint())
if Current_Line.StartPoint() in Points or \
Current_Line.EndPoint() in Points:
Queue.add(Potential_Match)
Line_List -= Queue # Take the matches we just found out of the list
Grouped_Lines.append(Shape)
return Grouped_Lines
source to share
As with @ChristophHegemann's idea, just imagine the numbers are actually just representations 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 end is other line start
if L.b == line.a:
L.next = line
line.previous = L
# if current line start is other line 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 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 $
source to share