Coding Challenge: Intersecting rectangles

coding-challenge-intersecting-rectangles.js

/**
 * Coding Challenge: Intersecting rectangles
 * 
 * Write a function calculateRectanglesIntersection that accepts two rectangles
 * (in string format like "(0,0),(0,4),(6,4),(0,6)") and returns the value of
 * the intersection area
 */

const getRectangleCoordinates = (coordsInput) => {
  let temp = coordsInput.slice(1, coordsInput.length - 1);
  return temp.split('),(').map(coords => coords.split(',').map(parseFloat));
};

const calculateDistance = (p1, p2) => {
  const [x1, y1] = p1;
  const [x2, y2] = p2;
  return Math.abs(x1 === x2 ? y2 - y1 : x2 - x1);
};

// Accepts 3 or 4 points
const calculateRectangleArea = (rect) => {
  const [a, b, c] = rect.slice(0, 3);
  const ab = calculateDistance(a, b);
  const bc = calculateDistance(b, c);
  return ab * bc;
};

const isSegmentVertical = (segment) => {
  const [p1, p2] = segment;
  return p1[0] === p2[0];
};

const getSegmentsIntersection = (segment1, segment2) => {
  const isSegment1Vertical = isSegmentVertical(segment1);
  const isSegment2Vertical = isSegmentVertical(segment2);

  if (isSegment1Vertical === isSegment2Vertical) {
    return null;
  }

  const [horizontal, vertical] = isSegment1Vertical
    ? [segment2, segment1]
    : [segment1, segment2];

  const [verticalStart, verticalFinish] = vertical;
  const [horizontalStart, horizontalFinish] = horizontal;

  const x = verticalStart[0];
  const y = horizontalStart[1];

  // These read "horizontal segment is * compared to vertical segment"
  // Ex.: "horizontal segment is tooHigh compared to vertical segment"
  const tooHigh = y > verticalStart[1] && y > verticalFinish[1];
  const tooRight = x < horizontalStart[0] && x < horizontalFinish[0];
  const tooLow = y < verticalStart[1] && y < verticalFinish[1];
  const tooLeft = x > horizontalStart[0] && x > horizontalFinish[0];

  if (tooHigh || tooRight || tooLow || tooLeft) {
    return null;
  }

  return [x, y];
};

const isPointInRectangle = (p, rect) => {
  const [a, b, c] = rect.slice(0, 3);
  const [ax, ay] = a;
  let [xMin, xMax, yMin, yMax] = [ax, ax, ay, ay];
  for (const i of [b, c]) {
    const [ix, iy] = i;
    if (ix < xMin) xMin = ix;
    if (ix > xMax) xMax = ix;
    if (iy < yMin) yMin = iy;
    if (iy > yMax) yMax = iy;
  }
  const [px, py] = p;
  return px >= xMin && px <= xMax && py >= yMin && py <= yMax;
};

const getSegmentsFromRectangle = (rect) => {
  const [a, b, c, d] = rect;
  return [
    [a, b],
    [b, c],
    [c, d],
    [d, a],
  ];
};

// Simplification: rectangles are always parallel/orthogonal with x and y axes
const calculateRectanglesIntersection = (r1Input, r2Input) => {
  const r1 = getRectangleCoordinates(r1Input);
  const r2 = getRectangleCoordinates(r2Input);

  const intersectionRect = [];

  for (const p of r2) {
    if (isPointInRectangle(p, r1)) {
      intersectionRect.push(p);
    }
  }

  for (const p of r1) {
    if (isPointInRectangle(p, r2)) {
      intersectionRect.push(p);
    }
  }

  if (!intersectionRect.length) {
    return 0;
  }

  // Three vertices of a rectangle are enough to calculate its area
  if (intersectionRect.length >= 3) {
    return calculateRectangleArea(intersectionRect);
  }

  for (const r1Segment of getSegmentsFromRectangle(r1)) {
    for (const r2Segment of getSegmentsFromRectangle(r2)) {
      const intersection = getSegmentsIntersection(r1Segment, r2Segment);
      if (intersection === null) continue;
      if (!isPointInRectangle(intersection, r1)) continue;
      intersectionRect.push(intersection);
    }
  }

  return calculateRectangleArea(intersectionRect);
};

// Tests ----------------------------------------------------------------------
const tests = [
  [
    '(0,0),(0,4),(4,4),(4,0)',
    '(2,2),(2,6),(6,6),(6,2)',
  ],
  [
    '(0,0),(0,4),(6,4),(0,6)',
    '(2,2),(11,2),(11,5),(2,5)',
  ],
  [
    '(0,0),(0,10),(10,10),(0,10)',
    '(0,0),(0,5),(5,5),(0,5)',
  ],
];

for (const test of tests) {
  const [r1, r2] = test;
  const result = calculateRectanglesIntersection(r1, r2);
  console.log(result);
}

// Results --------------------------------------------------------------------
// 4
// 16
// 25