2D Geometric Algorithms

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(s1, s2) #Test if s1 is a subset of s2.

2. match_vertices(v1, v2) #Orient vertex v1 and its respective shape so that v1 and one of v1‘s line segments coincide with v2 and one of v2‘s line segments.

3. subtract_shape(s1, s2) #Subtract s1 from s2 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(2n2) 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 n2 running time. Thus the total running time is O(n4<). In non pathological cases where |segments1| = 2 and |segments2| = 2, the running time is O(n2).

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(n4) 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(n3) running time.