C# 两个凸多边形之间的切线(Tangents between two Convex Polygons)

如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定两个凸多边形我们的目标是找出连接它们的下切线和上切线。如下图所示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 上的点向下移动。 }请注意上述代码仅计算了上切线。类似的方法也可用于求下切线。using System;public class UpperTangentFinder{static int Quad(int x, int y){if (x 0 y 0) return 1;if (x 0 y 0) return 2;if (x 0 y 0) return 3;return 4;}static int Orientation(int[] a, int[] b, int[] c){int res (b[1] - a[1]) * (c[0] - b[0]) -(c[1] - b[1]) * (b[0] - a[0]);if (res 0) return 0;return res 0 ? 1 : -1;}static bool Compare(int[] p1, int[] p2, int[] mid){int[] p { p1[0] - mid[0], p1[1] - mid[1] };int[] q { p2[0] - mid[0], p2[1] - mid[1] };int quadP Quad(p[0], p[1]);int quadQ Quad(q[0], q[1]);if (quadP ! quadQ)return quadP quadQ;return (p[1] * q[0]) (q[1] * p[0]);}static int[,] SortPoints(int[,] polygon){int n polygon.GetLength(0);int[] mid { 0, 0 };for (int i 0; i n; i){mid[0] polygon[i, 0];mid[1] polygon[i, 1];polygon[i, 0] * n;polygon[i, 1] * n;}for (int i 0; i n - 1; i){for (int j i 1; j n; j){int[] p1 { polygon[i, 0], polygon[i, 1] };int[] p2 { polygon[j, 0], polygon[j, 1] };if (!Compare(p1, p2, mid)){int tempX polygon[i, 0], tempY polygon[i, 1];polygon[i, 0] polygon[j, 0];polygon[i, 1] polygon[j, 1];polygon[j, 0] tempX;polygon[j, 1] tempY;}}}for (int i 0; i n; i){polygon[i, 0] / n;polygon[i, 1] / n;}return polygon;}static int[,] FindUpperTangent(int[,] a, int[,] b){int n1 a.GetLength(0);int n2 b.GetLength(0);int maxa int.MinValue;for (int i 0; i n1; i)maxa Math.Max(maxa, a[i, 0]);int minb int.MaxValue;for (int i 0; i n2; i)minb Math.Min(minb, b[i, 0]);a SortPoints(a);b SortPoints(b);if (minb maxa){int[,] temp a;a b;b temp;n1 a.GetLength(0);n2 b.GetLength(0);}int ia 0, ib 0;for (int i 1; i n1; i)if (a[i, 0] a[ia, 0])ia i;for (int i 1; i n2; i)if (b[i, 0] b[ib, 0])ib i;int inda ia, indb ib;bool done false;while (!done){done true;while (Orientation(new int[] { b[indb, 0], b[indb, 1] },new int[] { a[inda, 0], a[inda, 1] },new int[] { a[(inda 1) % n1, 0],a[(inda 1) % n1, 1] }) 0){inda (inda 1) % n1;}while (Orientation(new int[] { a[inda, 0], a[inda, 1] },new int[] { b[indb, 0], b[indb, 1] },new int[] { b[(n2 indb - 1) % n2, 0],b[(n2 indb - 1) % n2, 1] }) 0){indb (n2 indb - 1) % n2;done false;}}int[,] result new int[2, 2];result[0, 0] a[inda, 0];result[0, 1] a[inda, 1];result[1, 0] b[indb, 0];result[1, 1] b[indb, 1];return result;}public static void Main(string[] args){int[,] a new int[,] {{2, 2},{3, 1},{3, 3},{5, 2},{4, 0}};int[,] b new int[,] {{0, 1},{1, 0},{0, -2},{-1, 0}};int[,] tangent FindUpperTangent(a, b);for (int i 0; i 2; i){Console.WriteLine(tangent[i, 0] tangent[i, 1]);}}}输出上切线(upper tangent) (0,1) (3,3)时间复杂度O(n1 log (n1) n2 log(n2))辅助空间O(1)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。