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 ← L'：b 上的点向下移动。当（L 穿过 a）时 L ← L'：a 上的点向下移动。 }
请注意，上述代码仅计算了上切线。类似的方法也可用于求下切线。
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)
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。