如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定两个凸多边形我们的目标是找出连接它们的下切线和上切线。如下图所示TRL和TLR分别代表上切线和下切线。例如输入第一个多边形[[2, 2], [3, 3], [5, 2], [4, 0], [3, 1]]第二个多边形[[-1, 0], [0, 1], [1, 0], [0, -2]]。输出上切线 - 连接点 (0,1) 和 (3,3) 的直线下切线 - 连接点 (0,-2) 和 (4,0) 的直线说明图像清晰地显示了两个多边形的结构以及连接它们的切线。方法为了找到上切线我们首先选择两个点多边形a的最右点和多边形b的最左点。连接这两个点的直线标记为直线 1。由于这条直线穿过多边形b 即它没有完全位于多边形 b 的上方我们沿b逆时针方向移动到下一个点形成直线2。这条直线现在位于多边形b 的上方这很好。但是它穿过多边形a 因此我们沿a顺时针方向移动到下一个点形成直线 3。直线3仍然穿过多边形a因此我们继续移动到直线 4。然而直线 4穿过多边形b因此我们继续移动到直线 5。最后直线 5不穿过任何一个多边形因此它是给定多边形的正确上切线。为了找到下切线我们需要反向穿过多边形即如果直线穿过多边形 b则接下来顺时针移动如果直线穿过多边形 a则接下来逆时针移动。上切线算法L ←连接多边形 a 的最右点和 b 的最左点的线段。当 L 穿过任意多边形时当 L 穿过多边形 b 时L ← L多边形 b 上的点向上移动。当 L 穿过多边形 a 时L ← L多边形 a 上的点向上移动。下切线算法L ←连接多边形 a 的最右点和 b 的最左点的线段。当L 穿过任意多边形时 { 当L 穿过 b时 L ← Lb 上的点向下移动。当L 穿过 a时 L ← La 上的点向下移动。 }请注意上述代码仅计算了上切线。类似的方法也可用于求下切线。from functools import cmp_to_keydef quad(p):if p[0] 0 and p[1] 0:return 1if p[0] 0 and p[1] 0:return 2if p[0] 0 and p[1] 0:return 3return 4def orientation(a, b, c):res (b[1] - a[1]) * (c[0] - b[0]) - (c[1] - b[1]) * (b[0] - a[0])if res 0:return 0if res 0:return 1return -1def compare(mid):def cmp(p1, q1):p [p1[0] - mid[0], p1[1] - mid[1]]q [q1[0] - mid[0], q1[1] - mid[1]]one quad(p)two quad(q)if one ! two:return one - twoif p[1] * q[0] q[1] * p[0]:return -1return 1return cmpdef findUpperTangent(a, b):n1, n2 len(a), len(b)mid_a [0, 0]maxa float(-inf)for i in range(n1):maxa max(maxa, a[i][0])mid_a[0] a[i][0]mid_a[1] a[i][1]a sorted(a, keycmp_to_key(compare(mid_a)))mid_b [0, 0]minb float(inf)for i in range(n2):minb min(minb, b[i][0])mid_b[0] b[i][0]mid_b[1] b[i][1]b sorted(b, keycmp_to_key(compare(mid_b)))if minb maxa:a, b b, an1, n2 n2, n1ia 0for i in range(1, n1):if a[i][0] a[ia][0]:ia iib 0for i in range(1, n2):if b[i][0] b[ib][0]:ib iinda, indb ia, ibdone Falsewhile not done:done Truewhile orientation(b[indb], a[inda], a[(inda 1) % n1]) 0:inda (inda 1) % n1while orientation(a[inda], b[indb], b[(n2 indb - 1) % n2]) 0:indb (n2 indb - 1) % n2done False# return integer coordinatesreturn [[int(a[inda][0]), int(a[inda][1])],[int(b[indb][0]), int(b[indb][1])]]# Driver Codeif __name__ __main__:a [[2, 2],[3, 1],[3, 3],[5, 2],[4, 0]]b [[0, 1],[1, 0],[0, -2],[-1, 0]]upperTangent findUpperTangent(a, b)for point in upperTangent:print(f{point[0]} {point[1]})输出上切线(upper tangent) (0,1) (3,3)时间复杂度O(n1 log (n1) n2 log(n2))辅助空间O(1)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。