Cut polygons in 2D

Polygons are shapes made up of points and lines that connects them, thats simple enough but how would we cut one of them to fit a mask or hide stuff thats outside the render screen, we will cover that here. Firstly we will go into the basics and move to the more advanced later on.

How can we cut a polygon

We will start out by using the Sutherland Hodgman algorithm and then later move onto writing our own algorithms but lets show how the algorithm works. This is a simple example using a polygon with four points as the subject polygon and a simple rectangle as our cutting polygon.

Sutherland Hodgman algorithm takes a list of points as input and output a new list of points, in this case the list of points is a polygon. It works by looking at every line of the subject polygon and deciding which points of the line to add to the new list based on if they are outside or inside the cutting polygon. This method is usually repeated on every side of the cutting polygon and only looking if it is outside that line but as this example only has one line with point outside it we will only cover that in this example.

The algorithm works on looking at both points in the line point 1 and point 2 and see if they are outside or inside the cutting polygon. There are four cases:

1. If both points are inside then add point 2 to the new list.
2. If both points are outside then add none of them.
3. If point 2 is outside but point 1 is inside then add the intersection of the current line and the appropriate line of the cutting polygon.
4. If point 1 is outside but point 2 is inside then add the intersection and point 2 to the list.

Now we will go through an example of this This matches case 1 so we will add point 2 to the new list.

This matches case 3 so we will add the intersection of the lines to the output list.

This matches case 2 so we wont add any points.

This matches case 4 so we will add the intersection and point 2 to the list. We finally end up with this polygon

Split a polygon using an infinite line

Cutting a polygon using an rectangle or any other convex shape is good if you only need to mask something but if you want to cut more complex shapes you have to be able to save some sides and remove some others so in this part we will create an function to split a polygon into two using a dividing line.

We will start by defining some classes

class Point {
  public x: number;
  public y: number;

  constructor(x: number, y: number) {
    this.x = x;
    this.y = y;
  }
}
class Line {
  public start: Point;
  public end: Point;

  constructor(start: Point, end: Point) {
    this.start = start;
    this.end = end;
  }
}
class Polygon {
  public points: Point[];

  constructor(points: Point[]) {
    this.points = points;
  }
}

Now we will create a helper function for getting which side of the line the point is on

function sideOfLine(line: Line, point: Point): number {
  return Math.sign(
    (line.end.x - line.start.x) * (point.y - line.start.y) -
    (line.end.y - line.start.y) * (point.x - line.start.x)
  );
}

this function will return either a -1 or 1 depending on which side of the line the point is or 0 if the point is on the line.

Now we need another function to get the intersection between the line and two points

function intersection(line: Line, a: Point, b: Point) {
  const x1 = line.start.x;
  const y1 = line.start.y;

  const x2 = line.end.x;
  const y2 = line.end.y;

  const x3 = a.x;
  const y3 = a.y;

  const x4 = b.x;
  const y4 = b.y;

  const denominator = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
  if (denominator === 0) return null;

  const u = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator;
  if (u < 0 || u > 1) return null;

  return new Point(
    x3 + u * (x4 - x3),
    y3 + u * (y4 - y3)
  );
}

this function calculates where the intersection point is, if there is no intersection then it returns null.

Now its time to glue everything together, we start by making a function

function cutPolygon(polygon: Polygon, line: Line) {
  const sideA: Point[] = [];
  const sideB: Point[] = [];

  // logic goes here

  return [
    new Polygon(sideA),
    new Polygon(sideB)
  ];
}

we start by making the logic to loop through all point pairs in the polygon

for (let i = 0; i < polygon.points.length; i++) {
  const a = polygon.points[i];
  const b = polygon.points[i + 1] ?? polygon.points[0];

  // do stuff here
}

now we add code to add them respectively to each list

const aSide = sideOfLine(line, a);
const bSide = sideOfLine(line, b);

// add to sideA
if (aSide >= 0 || bSide >= 0) {
  // do the checking for which point to add
}

// add to sideB
if (aSide <= 0 || bSide <= 0) {
  // do the checking for which point to add
}

now we change the two last if statements to actually work

if (aSide >= 0 || bSide >= 0) {
  const intersectionPoint = intersection(line, a, b);
  if (intersectionPoint) sideA.push(intersectionPoint);
  if (bSide >= 0) sideA.push(b);
}

if (aSide <= 0 || bSide <= 0) {
  const intersectionPoint = intersection(line, a, b);
  if (intersectionPoint) sideB.push(intersectionPoint);
  if (bSide <= 0) sideB.push(b);
}

We now have a final function for splitting polygons

function cutPolygon(polygon: Polygon, line: Line) {
  const sideA: Point[] = [];
  const sideB: Point[] = [];

  for (let i = 0; i < polygon.points.length; i++) {
    const a = polygon.points[i];
    const b = polygon.points[i + 1] ?? polygon.points[0];

    const aSide = sideOfLine(line, a);
    const bSide = sideOfLine(line, b);

    if (aSide >= 0 || bSide >= 0) {
      const intersectionPoint = intersection(line, a, b);
      if (intersectionPoint) sideA.push(intersectionPoint);
      if (bSide >= 0) sideA.push(b);
    }

    if (aSide <= 0 || bSide <= 0) {
      const intersectionPoint = intersection(line, a, b);
      if (intersectionPoint) sideB.push(intersectionPoint);
      if (bSide <= 0) sideB.push(b);
    }
  }

  return [
    new Polygon(sideA),
    new Polygon(sideB)
  ];
}

Thank you for reading

If you liked this article please give it a like and share it with your friends. This is my first blog here so please give me suggestions to make it better