面试题16.03.交点

链接：面试题16.03.交点
难度：Hard
标签：几何、数学
简介：给定两条线段（表示为起点 start = {X1, Y1}和终点 end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。

题解 1 - javascript

• 编辑时间：2020-04-12
• 执行用时：72ms
• 内存消耗：33.7MB
• 编程语言：javascript
• 解法介绍：先判断两条线是否有交点，在判断线段是否有交点，难点在判断各种极端情况。

/**
 * @param {number[]} start1
 * @param {number[]} end1
 * @param {number[]} start2
 * @param {number[]} end2
 * @return {number[]}
 */
var intersection = function (start1, end1, start2, end2) {
  function include(num, num1, num2) {
    if (num1 > num2) [num1, num2] = [num2, num1];
    return num >= num1 && num <= num2;
  }
  if (start1[0] > end1[0]) [start1, end1] = [end1, start1];
  if (start2[0] > end2[0]) [start2, end2] = [end2, start2];
  // console.log(start1, end1, start2, end2);
  let intersectionX, intersectionY;
  const k1 = (end1[1] - start1[1]) / (end1[0] - start1[0]);
  const k2 = (end2[1] - start2[1]) / (end2[0] - start2[0]);
  const b1 = start1[1] - k1 * start1[0];
  const b2 = start2[1] - k2 * start2[0];
  if (!Number.isFinite(k1) && !Number.isFinite(k2)) {
    if (start1[0] !== start2[0]) return [];
    else if (include(start1[1], start2[1], end2[1])) return start1;
    else if (include(end1[1], start2[1], end2[1])) return end1;
    else return [];
  } else if (!Number.isFinite(k1) && Number.isFinite(k2)) {
    intersectionX = start1[0];
    intersectionY = k2 * start1[0] + b2;
  } else if (Number.isFinite(k1) && !Number.isFinite(k2)) {
    intersectionX = start2[0];
    intersectionY = k1 * start2[0] + b1;
  } else {
    if (k1 === k2) {
      if (b1 === b2) {
        if (include(start2[0], start1[0], end1[0])) return start2;
        if (include(start1[0], start2[0], end2[0])) return start1;
        else return [];
      } else if (b1 !== b2) return [];
    }
    intersectionX = (b1 - b2) / (k2 - k1);
    intersectionY = k1 * intersectionX + b1;
  }
  // console.log(`line1:y=${k1}x${b1 < 0 ? "" : "+"}${b1}`);
  // console.log(`line2:y=${k2}x${b2 < 0 ? "" : "+"}${b2}`);
  // console.log(`intersection:(${intersectionX},${intersectionY})`);
  if (
    include(intersectionX, start1[0], end1[0]) &&
    include(intersectionX, start2[0], end2[0]) &&
    include(intersectionY, start1[1], end1[1]) &&
    include(intersectionY, start2[1], end2[1])
  )
    return [intersectionX, intersectionY];
  else return [];
};