算法练习05 判断两个矩形是否重叠

题目（2018-11-20）

用一个对象的数据来表示一个矩形的位置和大小：

{
  x: 100,
  y: 100,
  width: 150,
  height: 250
}

它表示一个宽为150高为250的矩形在页面上的(100, 100)的位置。

请你完成一个函数isOverlap可以接受两个矩形作为参数，判断这两个矩形在页面上是否重叠。例如：

const rect1 = { x: 100, y: 100, width: 100, height: 100 }
const rect2 = { x: 150, y: 150, width: 100, height: 100 }
isOverlap(rect1, rect2) // => true

实现

一开始的思路是，如果两个矩形重叠，那么必然有一个矩形的任意一个顶点在第一个矩形中，实现之后发现并不是的，这样没有考虑一个矩形完全包围另外一个矩形的情形，这种情况下需要先判断哪一个是比较小的矩形，小矩形的顶点一定在大矩形里面

尝试后发现，下面这种情形也没有考虑进去：

image

这种情况下，利用顶点来判断重叠就不靠谱了，索性取一个矩形的所有点进行遍历，只要有一个点在内部就立刻退出遍历，然后返回true

const isOverlap = (rect1, rect2) = > {
  if (rect1.width <= rect2.width) {
    [rect1, rect2] = [rect2, rect1]
  }
  const startX = rect1.x,
  startY = rect1.y,
  endX = startX + rect1.width,
  endY = startY + rect1.height;

  console.log(startX, 'startX');
  console.log(startY, 'startY');
  console.log(endX, 'endX');
  console.log(endY, 'endY');

  for (let x = rect2.x; x <= rect2.x + rect2.width; x++) {
    for (let y = rect2.y; y <= rect2.y + rect2.height; y++) {
      if (x >= startX && x <= endX && y >= startY && y <= endY) {
        return true
      }
    }
  }
  return false;
};

这样原则上应该是可以的，但是实在是有点蠢，重叠的情况要判断的情形比较多，那么反过来考虑，去判断不重叠的情况下，这样就比较简单了，只有四种情况：

image

这四种情况的判断：

endY2 < startY1 || endY1 < startY2 || startX1 > endX2 || startX2 > endX1

这就比较简单了

const isOverlap = (rect1, rect2) = > {
  const startX1 = rect1.x,
  startY1 = rect1.y,
  endX1 = startX1 + rect1.width,
  endY1 = startY1 + rect1.height;

  const startX2 = rect2.x,
  startY2 = rect2.y,
  endX2 = startX2 + rect2.width,
  endY2 = startY2 + rect2.height;

  return !(endY2 < startY1 || endY1 < startY2 || startX1 > endX2 || startX2 > endX1)
};

看着挺简单，其实真正思考起来发现，我还是挺蠢的

参考

• ScriptOJ - #98 判断两个矩形是否重叠