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.

Disconnected Polygon

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.

Advertisements

One thought on “2D Geometric Algorithms

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s