Split up a polygon

[Pomax]

Paste the following code into the editor over on https://pomax.github.io/custom-graphics-element/edit, then click the graphics element on the right to place polygon points. Any point you place can be moved by click/touch-dragging.

const points = [];
const colors = [`#ae40bf`, `#bf4a40`, `#99bf40`, `#40bf82`,];
const cm = 0.0000001;

function setup() {
  setSize(600, 400);
  setBorder(1, `black`);
  noGrid();
}

function draw() {
  setCursor(`none`);
  clear(`white`);

  // show the lines we'll use for splitting:
  const w = width / 2;
  const h = height / 2;
  setColor(`black`);
  line(w, 0, w, height);
  line(0, h, width, h);

  // Draw a split set of polygons, if we have any
  const set = split(points, w, h);
  set.forEach((points, i) => {
    try {
      // no need to be clever: it'd be roughly the same amount of code.
      if (i === 0) translate(10, -10)
      if (i === 1) translate(10, 10)
      if (i === 2) translate(-10, 10)
      if (i === 3) translate(-10, -10)
      setColor(colors[i]);
      plotData(points, `x`, `y`);
    } catch (e) { /* this prevents crashes when a segment crosses the origin */ }
    resetTransform();
  });

  // and draw our "real" polygon on top.
  if (points.length) {
    noFill();
    setStroke(`grey`)
    plotData([...points, points[0]], `x`, `y`);
    setStroke(`black`)
    points.forEach(p => point(p.x, p.y));
  }
}

function pointerUp(x, y) {
  // don't place points if the cursor's close enough to
  // another point already (so we don't place new points
  // when we let go of a point we're dragging/moving)
  if (currentPoint) return;

  points.push({ x, y });
  clearMovable();
  setMovable(points);
  redraw();
}

function split(coords, X, Y) {
  if (coords.length < 3) return [coords];
  coords = [...coords, coords[0]];

  const [left, right] = splitAlong(coords, `x`, X);
  const [tl, bl] = splitAlong(left, `y`, Y);
  const [tr, br] = splitAlong(right, `y`, Y);
  return [tr, br, bl, tl];
}

function splitAlong(coords, dim, threshold) {
  const lt = [], ge = [];

  for (let i = 1, e = coords.length, a = coords[0], b; i < e; i++) {
    b = coords[i];

    // prep: find the transitional value on the boundary
    const r = (threshold - a[dim]) / (b[dim] - a[dim]);
    const x = (dim === `x`) ? threshold : (1 - r) * a.x + r * b.x
    const y = (dim === `y`) ? threshold : (1 - r) * a.y + r * b.y
    const p = { x, y };

    // is there a less-than/greater-or-equal transition?
    if (a[dim] < threshold && b[dim] >= threshold) {
      lt.push(a);
      lt.push({ x: p.x - cm, y: p.y });
      ge.push(p);
    }
    else if (b[dim] < threshold && a[dim] >= threshold) {
      ge.push(a);
      ge.push(p);
      lt.push({ x: p.x - cm, y: p.y });
    }

    // if not, which bin do we put "a" in?
    else if (a[dim] < threshold) {
      lt.push(a);
    } else {
      ge.push(a);
    }

    // setup for next pair
    a = b;
  }

  // make sure to close our polygons
  lt.push(lt[0]);
  ge.push(ge[0]);

  return [lt, ge];
}

[Pomax]

Of course, this can be improved by not running splitAlong three times, but instead running it once with four quadrant arrays that we bin into based on both x and y thresholds, but then the challenge is figuring out whether to inject additional corner points.