如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定两个凸多边形我们的目标是找出连接它们的下切线和上切线。如下图所示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 上的点向下移动。 }请注意上述代码仅计算了上切线。类似的方法也可用于求下切线。#include bits/stdc.husing namespace std;// Determines the quadrant of a point relative to originint quad(vectorint 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;}// Returns the orientation of ordered triplet (a, b, c)// 0 - Collinear, 1 - Clockwise, -1 - Counterclockwiseint orientation(vectorint a, vectorint b, vectorint c) {int res (b[1] - a[1]) * (c[0] - b[0]) -(c[1] - b[1]) * (b[0] - a[0]);if (res 0)return 0;if (res 0)return 1;return -1;}// Compare function to sort points counter-clockwise around centerbool compare(vectorint p1, vectorint q1, vectorint mid) {vectorint p {p1[0] - mid[0], p1[1] - mid[1]};vectorint q {q1[0] - mid[0], q1[1] - mid[1]};int one quad(p);int two quad(q);if (one ! two)return (one two);return (p[1] * q[0] q[1] * p[0]);}// Sorts the polygon points counter-clockwisevectorvectorint sortPoints(vectorvectorint polygon) {vectorint mid {0, 0};int n polygon.size();// Calculate center (centroid) of the polygonfor (int i 0; i n; i) {mid[0] polygon[i][0];mid[1] polygon[i][1];polygon[i][0] * n;polygon[i][1] * n;}// Sort points based on their angle from the centersort(polygon.begin(), polygon.end(),[mid](vectorint p1, vectorint p2) {return compare(p1, p2, mid);});// Divide back to original coordinatesfor (int i 0; i n; i) {polygon[i][0] / n;polygon[i][1] / n;}return polygon;}// Finds the upper tangent between two convex polygons a and b// Returns two points forming the upper tangentvectorvectorint findUpperTangent(vectorvectorint a,vectorvectorint b) {int n1 a.size(), n2 b.size();// Find the rightmost point of polygon a and leftmost point of polygon bint maxa INT_MIN;for (auto p : a)maxa max(maxa, p[0]);int minb INT_MAX;for (auto p : b)minb min(minb, p[0]);// Sort both polygons counter-clockwisea sortPoints(a);b sortPoints(b);// Ensure polygon a is to the left of polygon bif (minb maxa)swap(a, b);n1 a.size();n2 b.size();// Find the rightmost point in aint ia 0, ib 0;for (int i 1; i n1; i)if (a[i][0] a[ia][0])ia i;// Find the leftmost point in bfor (int i 1; i n2; i)if (b[i][0] b[ib][0])ib i;// Initialize starting pointsint inda ia, indb ib;bool done false;// Find upper tangent using orientation checkswhile (!done) {done true;// Move to next point in a if necessarywhile (orientation(b[indb], a[inda], a[(inda 1) % n1]) 0)inda (inda 1) % n1;// Move to previous point in b if necessarywhile (orientation(a[inda], b[indb],b[(n2 indb - 1) % n2]) 0) {indb (n2 indb - 1) % n2;done false;}}// Return the points forming the upper tangentreturn {a[inda], b[indb]};}// Main driver codeint main() {vectorvectorint a {{2, 2}, {3, 1}, {3, 3}, {5, 2}, {4, 0}};vectorvectorint b {{0, 1}, {1, 0}, {0, -2}, {-1, 0}};vectorvectorint tangent findUpperTangent(a, b);for(auto it:tangent){coutit[0] it[1]\n;}return 0;}输出上切线(upper tangent) (0,1) (3,3)时间复杂度O(n1 log (n1) n2 log(n2))辅助空间O(1)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。