For implementing Vert-Solve or Poly-Solve several lower level algorithms are needed. In particular I want to describe the most important ones which are:

**1.** subset(s_{1}, s_{2}) #Test if s_{1} is a subset of s_{2}.

**2.** match_vertices(v_{1}, v_{2}) #Orient vertex v_{1} and its respective shape so that v_{1} and one of v_{1}‘s line segments coincide with v_{2} and one of v_{2}‘s line segments.

**3.** subtract_shape(s_{1}, s_{2}) #Subtract s_{1} from s_{2} and return the new shape.

All three algorithms make use of more basic algorithms such as line intersection.

**1.** The following python code implements *subset*. I note that shape.nodes is a list of points defining shape (i.e. the list of vertices). The function *segment_contained_in* tests if the line segment (node1, node2) is a subset of shape2), it will return true if (node1, node2) are part of shape2’s boundary. The function *inside_shape* test if (r, c) is strickly inside shape2 that is if (r,c) is on the boundary of shape2, then *inside_shape*((r, c), shape2) returns false.

def subset(shape1, shape2):
"""returns true if shape1 is a subset of shape2, returns false otherwise"""
for (r,c) in shape1.nodes:
if not inside_shape((r,c),shape2) and not on_boundary((r,c),shape2):
return False
for (node1,node2) in shape1.line_segments:
if not segment_contained_in((node1,node2), shape2):
return False
return True

Let n = *max*(|shape1.line_segments|, |shape2.line_segments|), where || denotes set size. The number of vertices in shape1 or shape2 is strickly less than n. The running time of *inside_shape* and *on_boundary* is linear in n; *segment_contained_in* also has linear running time in n. Thus *subset* has O(2n^{2}) running time.

**2.** I use the following code for matching vertices. It makes use of python generators.

def match_vertices(i, j, shape1, shape2):
vertex1 = shape1.vertices[i]
vertex2 = shape2.vertices[j]
(point1,segments1) = vertex1
(point2,segments2) = vertex2
#translate vertex1 ontop of vertex2
shape1.translate((point2[0] - point1[0], point2[1] - point1[1]))
#for each segment1 in vertex1 and for each segment2, make segment1 parallel to segment2. This way we
#try all orientations that can make shape1 contained inside of p_shape_to_fit.
for segment1 in segments1:
for segment2 in segments2:
#translate so point2 is the origin
tsegment1 = translate(segment1, (-point2[0], -point2[1]))
tsegment2 = translate(segment2, (-point2[0], -point2[1]))
vec1 = tsegment1[0]
if(points_equal(tsegment1[0], [0, 0])): vec1 = tsegment1[1]
vec2 = tsegment2[0]
if(points_equal(tsegment2[0], [0, 0])): vec2 = tsegment2[1]
#theta1 is the angle that segment1 makes with the positive x-axis.
#0 <= theta1 < 2pi
theta1 = angle(vec1)
#theta2 is the angle that segment2 makes with the positive x-axis
#0 <= theta2 < 2pi
theta2 = angle(vec2)
rotation_angle = theta2 - theta1
p1 = rotate2d(vec1, rotation_angle)
p1 = (p1[0] + point2[0], p1[1] + point2[1])
if not inside_shape(p1, shape2) and not on_boundary(p1, shape2):
continue
nodes = shape1.nodes[:]
line_segments = shape1.line_segments[:]
verts = shape1.vertices[:]
#rotate segment1 into segment2
shape1.rotate(point2, rotation_angle)
if subset(shape1, shape2):
yield True
shape1.nodes = nodes
shape1.line_segments = line_segments
shape1.vertices = verts
yield False

Let n = *max*(|shape1.line_segments|, |shape2.line_segments|).

The number of line segments attached to vertex1 is at most n. It appears that there should only be two line segments attached to vertex1 but consider the case of a disconnected shape. In the shape below one of the vertices has 4 line segments attached to it.

The only important call for running time analysis inside the inner loop is *subset*(shape1, shape2), which as I’ve shown in **1.** has **n**^{2} running time. Thus the total running time is O(n^{4}<). In non pathological cases where |segments1| = 2 and |segments2| = 2, the running time is O(n^{2}).

The above gives the total running time of the generator but I’m also interested in the running time for one iteration of match_vertices. That is what is running time for one iteration of match_vertices. For this we need to find the running time between *yield* statements. The worst case scenario is that there are no matches, that is the the first call to match_vertices returns false. In which case the call takes O(n^{4}) time.

The running time for getting the next iteration given by generator

**3.** The following is the python code for *subtract_shape*

def subtract_shape(p_shape1, p_shape2):
new_line_segments = []
if not subset(p_shape1, p_shape2): return None
for line_segment1 in p_shape1.line_segments:
split_seg = split_segment(line_segment1, p_shape2)
#the part of the line segment that is outside p_shape2
outside_part = split_seg['outside']
#None of the line segment should be outside of p_shape2 since p_shape1 is a subset of p_shape2
assert(outside_part == [])
#the boundary part of a line segment does not form part of the boundary for the new shape, so we can ignore this part of the line segment
boundary_part = split_seg['boundary']
#this is the part of the line segment that will be included in the boundary of the new shape
inside_part = split_seg['inside']
new_line_segments.extend(inside_part)
for line_segment2 in p_shape2.line_segments:
split_seg = split_segment(line_segment2, p_shape1)
#the part of the line segment that is outside p_shape1
outside_part = split_seg['outside']
new_line_segments.extend(outside_part)
#the boundary part of a line segment does not form part of the boundary for the new shape, so we can ignore this part of the line segment
boundary_part = split_seg['boundary']
#this is the part of the line segment that will be included in the boundary of the new shape
inside_part = split_seg['inside']
#none of the line segments in p_shape2 should be in p_shape1 since p_shape1 is a subset of p_shape2
#remove zero length line segments
#the zero length line segments are a result of the floating point errors.
for seg in new_line_segments:
if(nodes_equal(seg[0], seg[1])):
new_line_segments.remove(seg)
return shape('', '', new_line_segments)

I believe *split_segment* runs in quadratic time with respect to |p_shape2.line_segments|. In which case *subtract_shape* has O(n^{3}) running time.