为了完整性,我想分享我的解决方案,这是一个基于Retsam的被接受的答案和David Eisenstat在评论中提出的想法的python实现。该方法是将凸包上连接到原多边形上相同顶点的边替换为来自该多边形的中间顶点。
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).
"""
polygons = [polya, polyb]
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))]
ch = convexHull(composite)
x, y, last_vnum, last_pnum = ch[0]
results = [(x, y)]
directions = [None for poly in polygons]
for x, y, vnum, pnum in list(ch[1:]) + [ch[0]]:
if pnum == last_pnum:
vcount = len(polygons[pnum])
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]
v = last_vnum
while v != vnum:
v += direction
if v >= vcount:
v = 0
elif v == -1:
v = vcount - 1
results.append(polygons[pnum][v])
else:
results.append((x, y))
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)
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
sel_verts = [leftMostVert]
sidx = leftMostVert
spt = points[sidx]
last_vect = (0, -1, 0)
last_mag = 1.0
twopi = 2.0*math.pi
vert_nums = range(point_count)
colinear = []
while True:
min_angle = None
for i in vert_nums:
if i == sidx or (len(sel_verts) > 1 and i == sel_verts[-2]) or i in colinear:
continue
pt = points[i]
vect = (pt[0] - spt[0], pt[1] - spt[1], 0)
mag = math.sqrt(vect[0]*vect[0] + vect[1]*vect[1])
dp = last_vect[0]*vect[0] + last_vect[1]*vect[1]
cos_theta = dp / (last_mag * mag)
if cos_theta > 1.0:
cos_theta = 1.0
elif cos_theta < -1.0:
cos_theta = -1.0
theta = math.acos(cos_theta)
cpz = last_vect[0]*vect[1] - last_vect[1]*vect[0]
cwangle = theta
if cpz > 0:
cwangle = twopi - theta
if min_angle is None or cwangle < min_angle:
min_angle = cwangle
next_vert = i
next_mvect = vect
next_mag = mag
next_pt = pt
elif cwangle == min_angle:
if mag > next_mag:
colinear.append(next_vert)
min_angle = cwangle
next_vert = i
next_mvect = vect
next_mag = mag
next_pt = pt
else:
colinear.append(i)
if next_vert == leftMostVert:
break
else:
sel_verts.append(next_vert)
sidx = next_vert
spt = next_pt
last_vect = (-next_mvect[0], -next_mvect[1])
last_mag = next_mag
return tuple(points[i] for i in sel_verts)