Combine nearby polygons

Question

I have a pair of (closed) polygons, each defined as a sequence of points (the vertices). The polygons each represent a plot of land, separated by a small river, so the stream forms a narrow gap between the two polygons.

I'm looking for an algorithm to identify and remove the gap, by joining the two polygons into one connected polygon.

The figure below shows an example, where the original polygons are the green and the red, and the resulting polygon is shown in yellow.

So far, I have been able to do the following:

• For each edge in polygon-A, find the nearest vertex in polygon-B.
• Find all vertices of polygon-B that are within a certain distance of polygon-A.

But I'm not really sure what I need to do now.

Answer 1

Just for completeness, I wanted to share my solution, as a python implementation. This is based on the accepted answer by Retsam, and the idea presented by David Eisenstat in the comments to that answer, which is to replace edges on the convex hull that connect to vertices on the same original polygon, with the intervening vertices from that polygon.

def joinPolygons(polya, polyb):
    """
    Generate and return a single connected polygon which includes the two given
    polygons. The connection between the two polygons is based on the convex hull
    of the composite polygon. All polygons are sequences of two-tuples giving the
    vertices of the polygon as (x, y), in order. That means vertices that are adjacent
    in the sequence are adjacent in the polygon (connected by an edge). The first and
    last vertices in the sequence are also connected by any edge (implicitly closed, do
    not duplicate the first point at the end of the sequence to close it).

    Only simple polygons are supported (no self-intersection).
    """

    #Just to make it easier to identify and access by index.
    polygons = [polya, polyb]

    #Create a single list of points to create the convex hull for (each
    # point is a vertex of one of the polygons).
    #Additionally, each point includes some additional "cargo", indicating which
    # polygon it's from, and it's index into that polygon
    # This assumes the implementation of convexHull simply ignores everything
    # beyond the first two elements of each vertex.
    composite = []
    for i in range(len(polygons)):
        points = polygons[i]
        composite += [(points[j][0], points[j][1], j, i) for j in xrange(len(points))]

    #Get the convex hull of the two polygons together.
    ch = convexHull(composite)

    #Now we're going to walk along the convex hull and find edges that connect two vertices
    # from the same source polygon. We then replace that edge with all the intervening edges
    # from that source polygon.

    #Start with the first vertex in the CH.
    x, y, last_vnum, last_pnum = ch[0]

    #Here is where we will collect the vertices for our resulting polygon, starting with the
    # first vertex on the CH (all the vertices on the CH will end up in the result, plus some
    # additional vertices from the original polygons).
    results = [(x, y)]

    #The vertices of the convex hull will always walk in a particular direction around each
    # polygon (i.e., forwards in the sequence of vertices, or backwards). We will use this
    # to keep track of which way they go.
    directions = [None for poly in polygons]

    #Iterate over all the remaining points in the CH, and then back to the first point to
    # close it.
    for x, y, vnum, pnum in list(ch[1:]) + [ch[0]]:

        #If this vertex came from the same original polygon as the last one, we need to
        # replace the edge between them with all the intervening edges from that polygon.
        if pnum == last_pnum:

            #Number of vertices in the polygon
            vcount = len(polygons[pnum])

            #If an edge of the convex hull connects the first and last vertex of the polygon,
            # then the CH edge must also be an edge of the polygon, because the two vertices are
            # adjacent in the original polygon. Therefore, if the convex
            # hull goes from the first vertex to the last in a single edge, then it's walking
            # backwards around the polygon. Likewise, if it goes from the last to the first in 
            # a single edge, it's walking forwards.
            if directions[pnum] is None:
                if last_vnum < vnum:
                    if last_vnum == 0 and vnum == vcount - 1:
                        direction = -1
                    else:
                        direction = 1
                else:
                    if last_vnum == vcount - 1 and vnum == 0:
                        direction = 1
                    else:
                        direction = -1
                directions[pnum] = direction
            else:
                direction = directions[pnum]

            #Now walk from the previous vertex to the current one on the source
            # polygon, and add all the intevening vertices (as well as the current one
            # from the CH) onto the result.
            v = last_vnum
            while v != vnum:
                v += direction
                if v >= vcount:
                    v = 0
                elif v == -1:
                    v = vcount - 1
                results.append(polygons[pnum][v])

        #This vertex on the CH is from a different polygon originally than the previous
        # vertex, so we just leave them connected.
        else:
            results.append((x, y))

        #Remember this vertex for next time.
        last_vnum = vnum
        last_pnum = pnum

    return results



def convexHull(points, leftMostVert=None):
    """
    Returns a new polygon which is the convex hull of the given polygon.

    :param: leftMostVert    The index into points of the left most vertex in the polygon.
                            If you don't know what it is, pass None and we will figure it
                            out ourselves.
    """
    point_count = len(points)

    #This is implemented using the simple Jarvis march "gift wrapping" algorithm.
    # Generically, to find the next point on the convex hull, we find the point
    # which has the smallest clockwise-angle from the previous edge, around the
    # last point. We start with the left-most point and a virtual vertical edge
    # leading to it.

    #If the left-most vertex wasn't specified, find it ourselves.
    if leftMostVert is None:
        minx = points[0][0]
        leftMostVert = 0
        for i in xrange(1, point_count):
            x = points[i][0]
            if x < minx:
                minx = x
                leftMostVert = i

    #This is where we will build up the vertices we want to include in the hull.
    # They are stored as indices into the sequence `points`.
    sel_verts = [leftMostVert]

    #This is information we need about the "last point" and "last edge" in order to find
    # the next point. We start with the left-most point and a pretend vertical edge.

    #The index into `points` of the last point.
    sidx = leftMostVert

    #The actual coordinates (x,y) of the last point.
    spt = points[sidx]

    #The vector of the previous edge.
    # Vectors are joined tail to tail to measure angle, so it
    # starts at the last point and points towards the previous point.
    last_vect = (0, -1, 0)
    last_mag = 1.0

    #Constant
    twopi = 2.0*math.pi

    #A range object to iterate over the vertex numbers.
    vert_nums = range(point_count)

    #A list of indices of points which have been determined to be colinear with
    # another point and a selected vertex on the CH, and which are not endpoints
    # of the line segment. These points are necessarily not vertices of the convex
    # hull: at best they are internal to one of its edges.
    colinear = []

    #Keep going till we come back around to the first (left-most) point.
    while True:
        #Try all other end points, find the one with the smallest CW angle.
        min_angle = None
        for i in vert_nums:

            #Skip the following points:
            # -The last vertex (sidx)
            # -The second to last vertex (sel_verts[-2]), that would just backtrack along
            #  the edge we just created.
            # -Any points which are determined to be colinear and internal (indices in `colinear`).
            if i == sidx or (len(sel_verts) > 1 and i == sel_verts[-2]) or i in colinear:
                continue

            #The point to test (x,y)
            pt = points[i]

            #vector from current point to test point.
            vect = (pt[0] - spt[0], pt[1] - spt[1], 0)
            mag = math.sqrt(vect[0]*vect[0] + vect[1]*vect[1])

            #Now find clockwise angle between the two vectors. Start by
            # finding the smallest angle between them, using the dot product.
            # Then use cross product and right-hand rule to determine if that
            # angle is clockwise or counter-clockwise, and adjust accordingly.

            #dot product of the two vectors.
            dp = last_vect[0]*vect[0] + last_vect[1]*vect[1]
            cos_theta = dp / (last_mag * mag)

            #Ensure fp erros don't become domain errors.
            if cos_theta > 1.0:
                cos_theta = 1.0
            elif cos_theta < -1.0:
                cos_theta = -1.0

            #Smaller of the two angles between them.
            theta = math.acos(cos_theta)

            #Take cross product of last vector by test vector.
            # Except we know that Z components in both input vectors are 0,
            # So the X and Y components of the resulting vector will be 0. Plus,
            # we only care aboue the Z component of the result.
            cpz = last_vect[0]*vect[1] - last_vect[1]*vect[0]

            #Assume initially that angle between the vectors is clock-wise.
            cwangle = theta
            #If the cross product points up out of the plane (positive Z),
            # then the angle is actually counter-clockwise.
            if cpz > 0:
                cwangle = twopi - theta

            #If this point has a smaller angle than the others we've considered,
            # choose it as the new candidate.
            if min_angle is None or cwangle < min_angle:
                min_angle = cwangle
                next_vert = i
                next_mvect = vect
                next_mag = mag
                next_pt = pt

            #If the angles are the same, then they are colinear with the last vertex. We want
            # to pick the one which is furthest from the vertex, and put all other colinear points
            # into the list so we can skip them in the future (this isn't just an optimization, it
            # appears to be necessary, otherwise we will pick one of the other colinear points as
            # the next vertex, which is incorrect).
            #Note: This is fine even if this turns out to be the next edge of the CH (i.e., we find
            # a point with a smaller angle): any point with is internal-colinear will not be a vertex
            # of the CH.
            elif cwangle == min_angle:
                if mag > next_mag:
                    #This one is further from the last vertex, so keep it as the candidate, and put the
                    # other colinear point in the list.
                    colinear.append(next_vert)
                    min_angle = cwangle
                    next_vert = i
                    next_mvect = vect
                    next_mag = mag
                    next_pt = pt
                else:
                    #This one is closer to the last vertex than the current candidate, so just keep that
                    # as the candidate, and put this in the list.
                    colinear.append(i)

        #We've found the next vertex on the CH.
        # If it's the first vertex again, then we're done.
        if next_vert == leftMostVert:
            break
        else:
            #Otherwise, add it to the list of vertices, and mark it as the
            # last vertex.
            sel_verts.append(next_vert)
            sidx = next_vert
            spt = next_pt
            last_vect = (-next_mvect[0], -next_mvect[1])
            last_mag = next_mag

    #Now we have a list of vertices into points, but we really want a list of points, so
    # create that and return it.
    return tuple(points[i] for i in sel_verts)