Hatch an arbitrary polygon

hatchPolygon.js

/*

Arguments:
Points is an ordered array of polygon points, each as an object with {x,y}
Hatching angle is in radians
Spacing is the space between each hatching line

Returns an array of lines objects in the shape [{start: {x,y}, end: {x,y}}]

*/

const HatchPolygon = (points, hatchingAngle, spacing) => {
  if (spacing == 0) return;
  const { centerX, centerY } = getPolygonBounds(points);
  let rotatedPoints = rotatePoints(points, -hatchingAngle, centerX, centerY);

  // Make a hatching lines that contain the complete polygon
  const { minX, minY, maxX, maxY } = getPolygonBounds(rotatedPoints);
  let hatchingLines = makeHorizontalHatchingLines(
    minX,
    minY,
    maxX - minX,
    maxY - minY,
    spacing
  );

  // Create all polygon lines and figure out intersections
  const polygonLines = rotatedPoints.map((point, i) => {
    const nextPoint =
      i == rotatedPoints.length - 1 ? rotatedPoints[0] : rotatedPoints[i + 1];
    return { start: point, end: nextPoint };
  });

  let intersections = [];

  hatchingLines.forEach((hatch) => {
    let lineIntersections = [];
    polygonLines.forEach((line) => {
      let intersects = linesIntersect(
        hatch.start.x,
        hatch.start.y,
        hatch.end.x,
        hatch.end.y,
        line.start.x,
        line.start.y,
        line.end.x,
        line.end.y
      );
      if (intersects) lineIntersections.push(intersects);
    });

    // We need the collisions sorted to work out the even-odd fill rule
    lineIntersections = lineIntersections.sort((a, b) => a.x - b.x);
    let p = 0;

    while (p < lineIntersections.length - 1) {
      intersections.push(lineIntersections[p], lineIntersections[p + 1]);
      p += 2;
    }
  });

  let rotatedIntersections = rotatePoints(
    intersections,
    hatchingAngle,
    centerX,
    centerY
  );

  let lines = [],
    p = 0;
  while (p < rotatedIntersections.length - 1) {
    lines.push({
      start: rotatedIntersections[p],
      end: rotatedIntersections[p + 1],
    });
    p += 2;
  }

  return lines;
};

const makeHorizontalHatchingLines = (x, y, width, height, spacing = 1) => {
  let lines = [];
  for (let yOffset = 0; yOffset < height; yOffset += spacing) {
    lines.push({
      start: { x, y: y + yOffset },
      end: { x: x + width, y: y + yOffset },
    });
  }
  return lines;
};

const rotatePoints = (points, angle, centerX = false, centerY = false) => {
  if (!centerX) {
    const bounds = getPolygonBounds(points);
    centerX = bounds.centerX;
    centerY = bounds.centerY;
  }
  const cos = Math.cos(angle);
  const sin = Math.sin(angle);

  let rotate = ({ x, y }) => {
    const deltaX = x - centerX;
    const deltaY = y - centerY;
    const result = {
      x: cos * deltaX + sin * deltaY + centerX,
      y: cos * deltaY - sin * deltaX + centerY,
    };
    return result;
  };

  return points.map(rotate);
};

const getPolygonBounds = (points) => {
  let minX = points[0].x,
    maxX = points[0].x,
    minY = points[0].y,
    maxY = points[0].y;

  points.forEach((point) => {
    if (point.x < minX) minX = point.x;
    if (point.x > maxX) maxX = point.x;
    if (point.y < minY) minY = point.y;
    if (point.y > maxY) maxY = point.y;
  });

  let centerX = minX + (maxX - minX) / 2;
  let centerY = minY + (maxY - minY) / 2;

  return {
    minX,
    maxX,
    minY,
    maxY,
    centerX,
    centerY,
  };
};

// line intercept math by Paul Bourke http://paulbourke.net/geometry/pointlineplane/
// Determine the intersection point of two line segments, false if no intersection

const linesIntersect = (x1, y1, x2, y2, x3, y3, x4, y4) => {
  // Check if none of the lines are of length 0
  if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {
    return false;
  }

  let denominator = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);

  // Lines are parallel
  if (denominator === 0) {
    return false;
  }

  let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator;
  let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator;

  // is the intersection along the segments
  if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {
    return false;
  }

  // Return a object with the x and y coordinates of the intersection
  let x = x1 + ua * (x2 - x1);
  let y = y1 + ua * (y2 - y1);

  return { x, y };
};

export default HatchPolygon;