LeetCode 面试题 16.03. 交点

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 面试题 16.03. 交点

题目

给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。

要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

示例 1：

输入：
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
输出： {0.5, 0}

示例 2：

输入：
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
输出： {1, 1}

示例 3：

输入：
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
输出： {}，两条线段没有交点

提示：

• 坐标绝对值不会超过 2^7
• 输入的坐标均是有效的二维坐标

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

既然是求两条__线段__是否有交点并返回交点，最直接的想法就是计算线段所在直线方程并解决就行了；

思路1-求直线方程再分情况处理

首先，需要明确两条线段的各自最小及最大x和y，便于后续计算判断，然后再分情况判断：
步骤：

• 计算各自的斜截式方程的k和b;（因为可能不存在k，k需要给一个防御值，不影响后面使用）
• 先判断不相交的情况，即判断线段的边界情况，这里的逻辑跟LeetCode 836 矩形重叠一致；
• 若斜率均不存在，那么x已确定，y是二者最小y中的最大者；
• 若其中之一不存在斜率，则x已确定，根据斜截式求y并验证y是否在前者的y之间；
• 若都存在斜率，直接求交点并校验是否在二者的区间内；
  图解：
  

算法复杂度:

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

算法源码示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年4月12日 下午10:26:53 
 * @Description: 面试题 16.03. 交点
 *	
 */
public class LeetCode_Offer_16_03 {
	public double[] intersection_1(int[] start1, int[] end1, int[] start2, int[] end2) {
		// 两线段的x和y的最值
		int minX1 = Math.min(start1[0], end1[0]);
		int minX2 = Math.min(start2[0], end2[0]);
		int minY1 = Math.min(start1[1], end1[1]);
		int minY2 = Math.min(start2[1], end2[1]);

		int maxX1 = Math.max(start1[0], end1[0]);
		int maxX2 = Math.max(start2[0], end2[0]);
		int maxY1 = Math.max(start1[1], end1[1]);
		int maxY2 = Math.max(start2[1], end2[1]);
		// 对于x和y，若其中一条线段的最小值大于另一条的最大值，则它们必不相交
		if (minX1 > maxX2 || minX2 > maxX1 || minY1 > maxY2 || minY2 > maxY1) {
			return new double[0];
		}
		// 计算y=kx+b的斜率k和截距b 以防斜率不存在计算k时使用三目运算给防御值0
		double k1 = minX1 == maxX1 ? 0 : (start1[1] - end1[1]) * 1.0 / (start1[0] - end1[0]);
		double k2 = minX2 == maxX2 ? 0 : (start2[1] - end2[1]) * 1.0 / (start2[0] - end2[0]);
		double b1 = start1[1] - k1 * start1[0];
		double b2 = start2[1] - k2 * start2[0];
		// 若均不存在斜率，那么x值已确定，y只需要取二者最小中的最大值即可
		if (minX1 == maxX1 && minX2 == maxX2 && minX1 == maxX2) {
			return new double[] { minX1, Math.max(minY1, minY2) };
			// 若其中之一无斜率，则x可确定，直接求y值，并判断y是否在无斜率的y区间内即可
		} else if (start1[0] == end1[0]) {
			double y = k2 * minX1 + b2;
			if (y >= minY1 && y <= maxY1) {
				return new double[] { minX1, y };
			} else {
				return new double[0];
			}
		} else if (start2[0] == end2[0]) {
			double y = k1 * minX2 + b1;
			if (y >= minY2 && y <= maxY2) {
				return new double[] { minX2, y };
			} else {
				return new double[0];
			}
		} else {
			// 若斜率相等，则b不等比不想交，b相等时需要再分别判断重叠部分的情况
			if (k1 == k2) {
				if (b1 != b2) {
					return new double[0];
				}
				boolean f = minX1 == minX2;
				boolean f1 = minX1 > minX2;
				boolean f2 = maxX1 < maxX2;
				// 最小x不等，则直接取最小x中的最大x对应点返回，若相等，则反向判断最大x时的类似情况即可
				if (f1 || (f && f2)) {
					if (start1[0] < end1[0]) {
						return new double[] { start1[0], start1[1] };
					} else {
						return new double[] { end1[0], end1[1] };
					}
				} else {
					if (start2[0] < end2[0]) {
						return new double[] { start2[0], start2[1] };
					} else {
						return new double[] { end2[0], end2[1] };
					}
				}
			} else {
				// 斜率都存在且不等，直接求节点，并判断区间即可
				double x = (b2 - b1) / (k1 - k2);
				double y = k1 * x + b1;

				boolean f1 = x >= minX1 && x <= maxX1 && x >= minX2 && x <= maxX2;
				boolean f2 = y >= minY1 && y <= maxY1 && y >= minY2 && y <= maxY2;

				if (f1 && f2) {
					return new double[] { x, y };
				} else {
					return new double[0];
				}
			}
		}
	}
}

原文链接:https://www.cnblogs.com/izhoujie/p/12707111.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有