May 22, 2016 2d, Geometry, Javascript

Polygon Clipping (Part 1)

Polygon clipping is an interesting problem: how do you intersect, union, or diff two polygons?

The Greiner-Hormann clipping algorithm is quite beautiful and intuitive. Let’s dissect it and take a look.

The Problem

First, let’s define the problem.

Imagine you have two polygons, each existing in 2D:

var poly1 = [ // red
  [ 181, 270 ],
  [  85, 418 ],
  [ 171, 477 ],
  [ 491, 365 ],
  [ 218, 381 ],
  [ 458, 260 ]
];
var poly2 = [ // blue
  [ 474, 488 ],
  [ 659, 363 ],
  [ 255, 283 ],
  [  56, 340 ],
  [ 284, 488 ],
  [ 371, 342 ]
];

Polygons

Even-Odd Rule

The polygons follow the Even-Odd Rule for determining whether a point is considered “inside” the area.

The basic technique is to imagine you are scanning from left to right on a single horizontal line. Every time you cross an edge, you toggle between outside and inside.

Even-Odd Rule

So: given these two polygons, how do we calculate the different boolean operations?

Basic Ideas

First, let’s define some basic ideas, so we’re on the same page.

Forward vs. Backward Movement

If we are sitting on any point in a polygon, we can always either go forwards or backwards.

Forwards simply means moving in the direction of the arrow, and backwards the reverse.

Movement Direction

Inserting Points

We will need to insert points in our polygons during processing. As long as we’re smart about how we insert them, it won’t change the shape of the polygon:

Insertion

Intersections

Now for the meat.

Identifying and categorizing intersections is the magic in the algorithm.

If you think about it, every operation we would perform (intersection, union, diff) would result in a polygon that contains all intersection points between the polygons.

Polygon Intersection Points

We are not concerned with intersections within the same polygon.

Also: if you imagine we are walking along a polygon and we hit an intersection, we have three choices:

1. Stay on the same polygon (which is pointless)
2. Switch polygons, and start moving forwards
3. Switch polygons, and start moving backwards

So if we can intelligently pick which direction we will go at each intersection, we can trace the correct resulting shape.

Intersection Examples

Imagine we are tracing the result of unioning two polygons.

At each intersection, we would want to move in the direction that would continue to grow the final shape.

We could do it this way:

We could get the same result going in the opposite direction, too:

What can we say that’s true about all four decisions?

At each intersection, we are always going in the direction away from the polygon we’re leaving.

So, for example, if we are traveling along Blue, and then hit an intersection, we should continue along Red in the direction away from Blue.

What would difference look like? Here’s Red - Blue:

And in the other direction:

What can we say about this?

When switching from Red to Blue, we go into Red. When switching from Blue to Red, we go away from Blue.

Ah ha!

So we have two basic decisions:

1. When switching from Red to Blue, do we go into or away from Red?
2. When switching from Blue to Red, do we go into or away from Blue?

For union, the answer is always to go away. But for Red - Blue, we want to go into Red, and away from Blue. If you play around, you’ll notice that intersection means always going into the polygon you’re leaving.

That gives us the following table:

Neat!

Entry/Exit Intersections

We don’t know how to go into or away though – we only know moving forwards and backwards along a polygon. How do we bridge this gap?

If we take two points on either side of an intersection, and test whether they are inside the other polygon, we are guaranteed that one point is outside, and one point is inside:

If the first point is outside, then we can think of the line as entering the polygon through the intersection. If the first point is inside, then the line exits the polygon through the intersection.

So, we really just need to label each intersection as either an entry or exit intersection.

We can be smart though:

As we travel along a path, each intersection toggles whether we are inside or outside. It must!

Therefore, we only need to calculate whether the first point is inside the other polygon. If it is, then the first intersection is an exit – otherwise the first intersection is an entry.

And since each intersection along the path toggles between entry and exit, we don’t have to keep testing whether points are inside or outside (which is expensive).

Representation

Lastly, it’s important to recognize that intersections are entry or exit relative to a polygon.

That means there are four possibilities per intersection:

White represents entry, Black exit. The left hemisphere is for Red, the right for Blue.

In practice, for each intersection, we will insert a point in each polygon. So there will be two points per intersection, one stored in each polygon. Each point will track whether it is an entry or exit.

Now we are ready to code!

Step 1. Convert Polygons to Linked Lists

A double linked list turns out to be a useful representation of a polygon for this algorithm, because we will be inserting points and traversing at the same time. By using a double linked list, we won’t have to worry about the insertions mucking up the traversing.

We’ll also need to track whether a point is an intersection or not, so we can start by initializing that to false here:

function UpgradePolygon(p){
  // converts a list of points into a double linked list
  var root = null;
  for (var i = 0; i < p.length; i++){
    var node = {
      point: p[i],
      intersection: false,
      next: null,
      prev: null
    };
    if (root === null){
      // root just points to itself:
      //    +-> (root) <-+
      //    |            |
      //    +------------+
      node.next = node;
      node.prev = node;
      root = node;
    }
    else{
      // change this:
      //    ...-- (prev) <--------------> (root) --...
      // to this:
      //    ...-- (prev) <--> (node) <--> (root) --...
      var prev = root.prev;
      prev.next = node;
      node.prev = prev;
      node.next = root;
      root.prev = node;
    }
  }
  return root;
}

Step 2. Calculate and Insert Intersections

Next, we need to iterate over each edge combination, and see if they intersect each other. If they do intersect each other, then we need to insert the intersection point in the polygon.

Line Intersection

First, we’ll need a helper function that can calculate where two lines intersect:

function LinesIntersect(a0, a1, b0, b1){
  var adx = a1[0] - a0[0];
  var ady = a1[1] - a0[1];
  var bdx = b1[0] - b0[0];
  var bdy = b1[1] - b0[1];

  var axb = adx * bdy - ady * bdx;
  var ret = {
    cross: axb,
    alongA: Infinity,
    alongB: Infinity,
    point: [Infinity, Infinity]
  };
  if (axb === 0)
    return ret;

  var dx = a0[0] - b0[0];
  var dy = a0[1] - b0[1];

  ret.alongA = (bdx * dy - bdy * dx) / axb;
  ret.alongB = (adx * dy - ady * dx) / axb;

  ret.point = [
    a0[0] + ret.alongA * adx,
    a0[1] + ret.alongA * ady
  ];

  return ret;
}

This is interesting math, but not the focus on this article. The most important thing is what it returns.

It calculates the intersection point of two lines, and also returns how far “along” the intersection is on each line. So, for example, if alongA is 0.75, then the intersection happens 75% of the way from a0 to a1.

These values are important because they could be negative or larger than 1, so if two lines actually intersect, we’ll need to test that alongA and alongB are between 0 and 1 (exclusive).

Next Non-Intersection Point

Since we will be inserting intersections into our linked list, it’s nice to have a helper function to find the next non-intersection point:

function NextNonIntersection(node){
  do{
    node = node.next;
  } while (node.intersection);
  return node;
}

Each Edge Pair

Now we can write the code that iterates over each edge pair:

var root1 = UpgradePolygon(poly1);
var root2 = UpgradePolygon(poly2);

var here1 = root1;
var here2 = root2;
do{
  do{
    //
    // TODO: test intersection between:
    //    here1 -> NextNonIntersection(here1)  and
    //    here2 -> NextNonIntersection(here2)
    //
    here2 = NextNonIntersection(here2);
  } while (here2 !== root2);
  here1 = NextNonIntersection(here1);
} while (here1 !== root1);

Testing for Intersection

Given two nodes, we can test for intersection:

var next1 = NextNonIntersection(here1);
var next2 = NextNonIntersection(here2);

var i = LinesIntersect(
  here1.point, next1.point,
  here2.point, next2.point
);

if (i.alongA > 0 && i.alongA < 1 &&
  i.alongB > 0 && i.alongB < 1){
  //
  // TODO: insert intersection points in both polygons at
  //       the correct location, referencing each other
  //
}

Inserting Intersection Nodes

Lastly, if two edges intersect, then we want to insert our intersection between the two non-intersection points.

In order to insert it at the correct location, we’ll have to track the alongA and alongB values to make sure that if two intersections are on the same edge, they are inserted in the correct order.

We’ll want to create two nodes, one for each of the polygons – but these nodes should point to each other so that we can later “hop” between polygons when we later hit an intersection.

var node1 = {
  point: i.point,
  intersection: true,
  next: null,
  prev: null,
  dist: i.alongA,
  friend: null
};
var node2 = {
  point: i.point,
  intersection: true,
  next: null,
  prev: null,
  dist: i.alongB,
  friend: null
};

// point the nodes at each other
node1.friend = node2;
node2.friend = node1;

var inext, iprev;

// find insertion between here1 and next1, based on dist
inext = here1.next;
while (inext !== next1 && inext.dist < node1.dist)
  inext = inext.next;
iprev = inext.prev;

// insert node1 between iprev and inext
inext.prev = node1;
node1.next = inext;
node1.prev = iprev;
iprev.next = node1;

// find insertion between here2 and next2, based on dist
inext = here2.next;
while (inext !== next2 && inext.dist < node2.dist)
  inext = inext.next;
iprev = inext.prev;

// insert node2 between iprev and inext
inext.prev = node2;
node2.next = inext;
node2.prev = iprev;
iprev.next = node2;

Step 3. Calculate Entry/Exit Intersections

We know that intersections alternate between entry and exit. But what is the first intersection? Is it an entry, or an exit?

Simple: if the polygon’s first point is inside the other polygon, then the first intersection must be an exit.

However, calculating whether a point is inside a polygon is actually a bit complicated!

Point In Polygon

Here is the code:

function PointInPolygon(point, root){
  var odd = false;
  var x = point[0];
  var y = point[1];
  var here = root;
  do {
    var next = here.next;
    var hx = here.point[0];
    var hy = here.point[1];
    var nx = next.point[0];
    var ny = next.point[1];
    if (((hy < y && ny >= y) || (hy >= y && ny < y)) &&
      (hx <= x || nx <= x) &&
      (hx + (y - hy) / (ny - hy) * (nx - hx) < x)){
      odd = !odd;
    }
    here = next;
  } while (here !== root);
  return odd;
}

Again, the math here isn’t the focus of this article.

PointInPolygon works by counting the number of edges a horizontal line would intersect. The horizontal line goes from (-Infinity, y) to (x, y). It only really cares if there is an odd or even number of intersections. It is based on ray casting.

Alternating Entry/Exit

Now we can easily calculate whether an intersection is an entry or exit:

function CalculateEntryExit(root, isEntry){
  var here = root;
  do{
    if (here.intersection){
      here.isEntry = isEntry;
      isEntry = !isEntry;
    }
    here = here.next;
  } while (here !== root);
}

var is1in2 = PointInPolygon(root1.point, root2);
var is2in1 = PointInPolygon(root2.point, root1);

CalculateEntryExit(root1, !is1in2);
CalculateEntryExit(root2, !is2in1);

Step 4. Generating the Result

We’ve come a long way! This is what we have so far:

We’ve calculated and inserted the intersections, and marked them as either entry or exit for each polygon.

Now for the fun part!

Where to Start?

Where do we start tracing the result? We can’t just pick a random point, because some points could actually be removed entirely from the result.

Since all operations include every intersection, we should start by looking for an unprocessed intersection.

Every intersection we add to the final result, we mark as processed.

Then, we just keep tracing until we no longer have any intersections left to process.

var result = [];
var isect = root1;
var into = [intoBlue, intoRed]; // explained below
while (true){
  do{
    if (isect.intersection && !isect.processed)
      break;
    isect = isect.next;
  } while (isect !== root1);
  if (isect === root1)
    break;

  //
  // TODO: process isect
  //
}

Which Way to Turn?

And finally, we come to the crux:

When we hit an intersection, how do we know which way to turn?

Let’s reason it out:

Therefore, we should move forward if isEntry === intoPoly.

Since the polygon we’re on switches back and forth, we simply make our decision dynamic by storing intoBlue and intoRed in the into list, and use curpoly as an index.

var curpoly = 0;
var clipped = [];

var here = isect;
do{
  // mark intersection as processed
  here.processed = true;
  here.friend.processed = true;

  var moveForward = here.isEntry === into[curpoly];
  do{
    clipped.push(here.point);
    if (moveForward)
      here = here.next;
    else
      here = here.prev;
  } while (!here.intersection);

  // we've hit the next intersection so switch polygons
  here = here.friend;
  curpoly = 1 - curpoly;
} while (!here.processed);

result.push(clipped);

No Intersections

What if there aren’t any intersections?

Our result set will be empty… which might be correct, or it might be wrong – depending on the operation.

A simple check is enough to fix it:

if (result.length <= 0){
  if (is1in2 === intoBlue)
    result.push(poly1);
  if (is2in1 === intoRed)
    result.push(poly2);
}

Demo

And we’re done!

But wait – you didn’t think I would write this huge article without an actual demo, did you?!

Click here to launch the demo!

Demo Screenshot

You can drag the points of each polygon, and switch the operation by clicking on the buttons.

The demo code is Public Domain, but this article is © Copyright 2016 Sean Connelly, with All Rights Reserved.

Addendum: Limitations

Sorry to say, but this algorithm has a serious limitation:

You can’t have points or edges that overlap perfectly.

If you think about it, this makes sense: the entire algorithm is based on the idea of intersections.

If points or edges directly overlap, then you don’t get that nice hopping effect.

The original paper recommended “perturbing” the points a bit, so that lines don’t end up exactly on top of each other. I originally thought this was a minor tweak and wouldn’t be a problem.

Boy, was I wrong.

Perturbing points corrupts the data – so properties of the source data that might be important (for example, smooth edges) becomes invalidated:

Real-World Results from "Perturbing"

Lucky for you I researched another algorithm that handles everything, and wrote a follow-up article!

Read the follow-up here: Polygon Clipping (Part 2)

Tags: 2d, Geometry, Javascript

View All Posts