JavaScript 两个凸多边形之间的切线(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 上的点向下移动。 }
请注意，上述代码仅计算了上切线。类似的方法也可用于求下切线。
// Determine the quadrant of a point
function quad(p) {
if (p[0] >= 0 && p[1] >= 0) return 1;
if (p[0] <= 0 && p[1] >= 0) return 2;
if (p[0] <= 0 && p[1] <= 0) return 3;
return 4;
}
// Find orientation of triplet (a, b, c)
function orientation(a, b, c) {
let 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;
}
// Compare two points based on mid
function compare(p1, p2, mid) {
let p = [p1[0] - mid[0], p1[1] - mid[1]];
let q = [p2[0] - mid[0], p2[1] - mid[1]];
let quadP = quad(p);
let quadQ = quad(q);
if (quadP !== quadQ)
return quadP - quadQ;
return (p[1] * q[0]) - (q[1] * p[0]);
}
// Sort polygon points counter-clockwise
function sortPoints(polygon) {
let n = polygon.length;
let mid = [0, 0];
for (let i = 0; i < n; i++) {
mid[0] += polygon[i][0];
mid[1] += polygon[i][1];
polygon[i][0] *= n;
polygon[i][1] *= n;
}
polygon.sort((p1, p2) => compare(p1, p2, mid));
for (let i = 0; i < n; i++) {
polygon[i][0] = Math.floor(polygon[i][0] / n);
polygon[i][1] = Math.floor(polygon[i][1] / n);
}
return polygon;
}
// Find upper tangent between two convex polygons
function findUpperTangent(a, b) {
let n1 = a.length;
let n2 = b.length;
let maxa = -Infinity;
for (let i = 0; i < n1; i++)
maxa = Math.max(maxa, a[i][0]);
let minb = Infinity;
for (let i = 0; i < n2; i++)
minb = Math.min(minb, b[i][0]);
a = sortPoints(a);
b = sortPoints(b);
if (minb < maxa) {
let temp = a;
a = b;
b = temp;
n1 = a.length;
n2 = b.length;
}
let ia = 0, ib = 0;
for (let i = 1; i < n1; i++)
if (a[i][0] > a[ia][0])
ia = i;
for (let i = 1; i < n2; i++)
if (b[i][0] < b[ib][0])
ib = i;
let inda = ia, indb = ib;
let done = false;
while (!done) {
done = true;
while (orientation(b[indb], a[inda], a[(inda + 1) % n1]) > 0)
inda = (inda + 1) % n1;
while (orientation(a[inda], b[indb], b[(n2 + indb - 1) % n2]) < 0) {
indb = (n2 + indb - 1) % n2;
done = false;
}
}
return [a[inda], b[indb]];
}
// Driver code
let a = [[2, 2],[3, 1],[3, 3],[5, 2],[4, 0]];
let b = [[0, 1],[1, 0],[0, -2],[-1, 0]];
let tangent = findUpperTangent(a, b);
for (let point of tangent) {
console.log(point[0] + " " + point[1]);
}
输出
上切线(upper tangent) (0,1) (3,3)
时间复杂度：O(n1 log (n1) + n2 log(n2))
辅助空间：O(1)
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。