如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定两个凸多边形我们的目标是找出连接它们的下切线和上切线。如下图所示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 上的点向下移动。 }请注意上述代码仅计算了上切线。类似的方法也可用于求下切线。import java.util.*;class GfG {// Determines the quadrant of a pointstatic int quad(int[] 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;}// Checks whether the line is crossing the polygonstatic 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;if (res 0)return 1;return -1;}// Compare function for sortingstatic class PointComparator implements Comparatorint[] {int[] mid;public PointComparator(int[] mid) {this.mid mid;}public int compare(int[] p1, int[] p2) {int[] p { p1[0] - mid[0], p1[1] - mid[1] };int[] q { p2[0] - mid[0], p2[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];}}// Finds upper tangent of two polygons a and b// represented as 2D arrays and stores the resultstatic int[][] findUpperTangent(int[][] a, int[][] b) {// n1 - number of points in polygon a// n2 - number of points in polygon bint n1 a.length, n2 b.length;int[] mid { 0, 0 };int maxa Integer.MIN_VALUE;// Calculate centroid for polygon a and adjust points for scalingfor (int i 0; i n1; i) {maxa Math.max(maxa, a[i][0]);mid[0] a[i][0];mid[1] a[i][1];a[i][0] * n1;a[i][1] * n1;}// Sorting the points in counter-clockwise order for polygon aArrays.sort(a, new PointComparator(mid));for (int i 0; i n1; i) {a[i][0] / n1;a[i][1] / n1;}mid[0] 0;mid[1] 0;int minb Integer.MAX_VALUE;// Calculate centroid for polygon b and adjust points for scalingfor (int i 0; i n2; i) {mid[0] b[i][0];mid[1] b[i][1];minb Math.min(minb, b[i][0]);b[i][0] * n2;b[i][1] * n2;}// Sorting the points in counter-clockwise order for polygon bArrays.sort(b, new PointComparator(mid));for (int i 0; i n2; i) {b[i][0] / n2;b[i][1] / n2;}// If a is to the right of b, swap a and bif (minb maxa) {int[][] temp a;a b;b temp;n1 a.length;n2 b.length;}// ia - rightmost point of aint ia 0, ib 0;for (int i 1; i n1; i) {if (a[i][0] a[ia][0])ia i;}// ib - leftmost point of bfor (int i 1; i n2; i) {if (b[i][0] b[ib][0])ib i;}// Finding the upper tangentint inda ia, indb ib;boolean 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;}}// Returning the upper tangent as a 2D arrayreturn new int[][] {{ a[inda][0], a[inda][1] },{ b[indb][0], b[indb][1] }};}// Driver codepublic static void main(String[] args) {int[][] a {{2, 2},{3, 1},{3, 3},{5, 2},{4, 0}};int[][] b {{0, 1},{1, 0},{0, -2},{-1, 0}};// Get the upper tangent as a 2D arrayint[][] upperTangent findUpperTangent(a, b);// Store or use the resultSystem.out.println(upperTangent[0][0] upperTangent[0][1]);System.out.println(upperTangent[1][0] upperTangent[1][1]);}}输出上切线(upper tangent) (0,1) (3,3)时间复杂度O(n1 log (n1) n2 log(n2))辅助空间O(1)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。
Java 两个凸多边形之间的切线(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 上的点向下移动。 }请注意上述代码仅计算了上切线。类似的方法也可用于求下切线。import java.util.*;class GfG {// Determines the quadrant of a pointstatic int quad(int[] 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;}// Checks whether the line is crossing the polygonstatic 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;if (res 0)return 1;return -1;}// Compare function for sortingstatic class PointComparator implements Comparatorint[] {int[] mid;public PointComparator(int[] mid) {this.mid mid;}public int compare(int[] p1, int[] p2) {int[] p { p1[0] - mid[0], p1[1] - mid[1] };int[] q { p2[0] - mid[0], p2[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];}}// Finds upper tangent of two polygons a and b// represented as 2D arrays and stores the resultstatic int[][] findUpperTangent(int[][] a, int[][] b) {// n1 - number of points in polygon a// n2 - number of points in polygon bint n1 a.length, n2 b.length;int[] mid { 0, 0 };int maxa Integer.MIN_VALUE;// Calculate centroid for polygon a and adjust points for scalingfor (int i 0; i n1; i) {maxa Math.max(maxa, a[i][0]);mid[0] a[i][0];mid[1] a[i][1];a[i][0] * n1;a[i][1] * n1;}// Sorting the points in counter-clockwise order for polygon aArrays.sort(a, new PointComparator(mid));for (int i 0; i n1; i) {a[i][0] / n1;a[i][1] / n1;}mid[0] 0;mid[1] 0;int minb Integer.MAX_VALUE;// Calculate centroid for polygon b and adjust points for scalingfor (int i 0; i n2; i) {mid[0] b[i][0];mid[1] b[i][1];minb Math.min(minb, b[i][0]);b[i][0] * n2;b[i][1] * n2;}// Sorting the points in counter-clockwise order for polygon bArrays.sort(b, new PointComparator(mid));for (int i 0; i n2; i) {b[i][0] / n2;b[i][1] / n2;}// If a is to the right of b, swap a and bif (minb maxa) {int[][] temp a;a b;b temp;n1 a.length;n2 b.length;}// ia - rightmost point of aint ia 0, ib 0;for (int i 1; i n1; i) {if (a[i][0] a[ia][0])ia i;}// ib - leftmost point of bfor (int i 1; i n2; i) {if (b[i][0] b[ib][0])ib i;}// Finding the upper tangentint inda ia, indb ib;boolean 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;}}// Returning the upper tangent as a 2D arrayreturn new int[][] {{ a[inda][0], a[inda][1] },{ b[indb][0], b[indb][1] }};}// Driver codepublic static void main(String[] args) {int[][] a {{2, 2},{3, 1},{3, 3},{5, 2},{4, 0}};int[][] b {{0, 1},{1, 0},{0, -2},{-1, 0}};// Get the upper tangent as a 2D arrayint[][] upperTangent findUpperTangent(a, b);// Store or use the resultSystem.out.println(upperTangent[0][0] upperTangent[0][1]);System.out.println(upperTangent[1][0] upperTangent[1][1]);}}输出上切线(upper tangent) (0,1) (3,3)时间复杂度O(n1 log (n1) n2 log(n2))辅助空间O(1)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。
