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.

Pingback: BryanBell » Blog Archive » Vert-Solve Running Time