Aug 1, 2016 2d, Geometry, Javascript

Polygon Clipping (Part 2)

My previous polygon clipping tutorial dove into the Greiner-Hormann clipping algorithm. Unfortunately, this algorithm fails at common cases… so let’s revist the problem and try again.

The F. Martinez 2008 algorithm handles coincident edges (unlike Greiner-Hormann), but it still has some minor goofiness. Let’s solve this problem once and for all.

The Problem, Again

Given two polygons:

Overlapping Polygons

How do we calculate the different boolean operations?

Desired Results

Polygon Representation

First we need to pick a good representation of a “polygon”.

Your first instinct might be a simple list of points:

var poly1 = [ [0,0], [100,0], [50,100] ];

I think this is wrong. A more robust definition of a polygon is a list of regions along with an inversion flag:

var poly1 = {
  regions: [
    [ [350,60],[480,200],[180,60] ],
    [ [180,60],[500,60],[180,220] ]
  ],
  inverted: false
};

The inverted flag is free for the algorithm, so we might as well include it.

Defining a polygon with multiple regions is important because the result of a boolean operation is a list of regions. This means our clipping algorithm returns the same thing it consumes.

This is the natural result of observing that even simple boolean operations produce multiple regions:

It turns out that defining polygons with multiple regions is essentially free for the algorithm too. So don’t worry.

Segments

One of the key observations in the F. Martinez paper is to think in terms of segments.

This is completely obvious, but remember that our previous algorithm thought in terms of intersections – so it is only obvious in hindsight.

A segment is defined as part of a line that doesn’t intersect anything. Segments never overlap and only connect to each other at the endpoints.

Five Labeled Segments

The bottom line is divided into exactly five segments.

It doesn’t matter that some parts of the line belong only to the red polygon, or both polygons, or that some of the segments only exist between intersections – there are exactly five segments.

Train your eyes to see the segments no matter what’s in the source data.

Annotating Segments

Now that we’re seeing things in terms of segments, we can imagine annotating each segment with whether the side of the segment is filled or empty:

Fill Annoatations

A solid circle means that side of the edge is the inside of the polygon.

And when we look at two polygons overlapping, we can imagine annotating each segment with the combined fill knowledge:

Combined Fill Annotations

If you can understand the above image, then you have enough insight to derive the entire algorithm.

Line Intersection

Unfortunately, things are about to get a lot more complicated. We need to find all the intersection vertices.

You could see if two polygons have intersecting lines by just testing each pair of lines. Sure, that might be a little slow, but so what.

Another key insight of the F. Martinez paper is that if we use the Bentley-Ottmann algorithm to detect intersections between lines, then we can piggy-back off this process to compute the segment fill annotations at the same time.

This is a really clever observation… but it means we need to complicate our intersection detection quite a bit.

Another benefit of using this technique is that it’s much faster than just testing every pair of lines, especially as the number of lines grows.

Vertical Line Sweep

In order to calculate intersections, we imagine we are sweeping a vertical line from left to right:

At any given moment, we can imagine having a stack of all the lines that intersect the vertical line:

Bolded lines (A, B, C, D) in stack

We call this stack the “status” of the sweep. Order matters – the status is always sorted from top to bottom.

So: when do the contents of the status stack change?

If you think about it, the status only changes at key moments:

Key moments where the status changes

If you look at the channels created between the key moments, you’ll notice that the status would be the same the entire time – the polygon lines in the channels are always in the same order from top to bottom.

So when are these “key moments”? It’s actually quite simple:

As the vertical line scans from left to right, the status changes any time a new line is introduced, an old line goes away, or the vertical line scans over an intersection.

Events

So even though we think of the vertical line as scanning, in reality we only care about certain events that happen while this imaginary line is scanning.

Every time an event happens, we will be changing the status.

There are three kinds of events:

1. A new line is added to status (Start event)
2. An old line is removed from status (End event)
3. An intersection happens

Start and End events for a line

Notice that Start and End events are sorted from left to right, because that’s the direction the vertical line scans. The order of the line’s input vertices is ignored.

Decomposing Intersections

The key insight of the Bentley-Ottmann algorithm is that when we are adding a new line to the status, we only have to check for intersections between the lines directly above it and directly below it.

Introducing B to the current status (A, D)

When we hit line B’s Start event, we would calculate the insertion point in status without actually inserting it.

We use this insertion point to peek at who is above and below line B.

If there is an intersection, then we split the two intersecting lines at the intersection point – creating four more events!

What are the four new events?

1. End event for A’s left-most segment
2. End event for B’s left-most segment
3. Start event for A’s right-most segment
4. Start event for B’s right-most segment

Then, in order to continue our vertical scan, we keep A’s left-most segment in the status, and insert B’s left-most segment in the status.

It’s important to note that we do not keep the right-most segments in the status. We let future Start events take care of that. This is important because the right-most segments could intersect more lines, so we’ll need to do further checks for them.

Please convince yourself that this process works, because it’s only going to get more complicated from here.

Handling Vertical Lines

How should we handle vertical lines? It’s sort of like we would be processing Start and End events at the same time… which we obviously can’t do.

Ultimately it doesn’t matter, as long as we’re consistent. I decided the Start event would be the bottom-most point, and the End would be the top-most.

That means you can think of the vertical line as scanning from left to right, but once at a location, it scans from bottom to top.

Handling Coincident Lines

Lines are “coincident” when they are directly on top of each other. It happens more than you think!

There are six possibilities:

Six cases of coincidence assuming Red is processed before Blue

You might think there would be more cases – after all, what if Blue’s left vertex is to the left of Red’s left vertex?

But that can’t happen. If that were the case, then the Blue line would be processed before the Red line, so it would just flip the colors… but the logic would be exactly the same as a case already listed.

Our basic strategy is still the same, with one additional concern:

When two segments are exactly the same, we will need to merge the fill annotations somehow, and throw one of the segments away. Remember that annotated segments are our ideal representation, and they never overlap.

So we will still perform the splitting like normal, but we have to watch out for resulting segments that perfectly overlap.

For example, for case 5, we will split the red line at the blue line’s left vertex, split the blue line at the red line’s right vertex, then continue processing. Future events will detect the overlapping segments (via case 1) to perform the segment combination.

This is a little tricky, but not too bad.

Handling Intersections After End Events

There is one last scenario that can trip you up:

When we remove a segment from the status, the two segments that surrounded the removed segment become adjacent in the status. Therefore, we need to check them for intersections.

For example, consider:

The status will start at: (A, B, C, D, E).

Then it will process the End events of B and C (order doesn’t matter), resulting in a new status of: (A, D, E).

If we only looked for intersections when inserting new segments into the status, then we would miss the intersection between A and D. So we’ll have to remember that when we remove segments from the status to check for intersections between newly adjacent segments.

Intersection Code

Before moving forward, let’s look at some code that performs this line sweep algorithm. We will be adding to this code in order to calculate the fill annotations later – but it’s better to get acquainted with the algorithm at this point before we complicate it further.

Please be aware that I am removing some details that exist in the real code base from this tutorial in order to highlight the algorithm itself.

For example, in reality it takes special logic to handle inexact floating point math using an epsilon value, which is accounted for in the real code. Those details are omitted here.

If you want to see everything in its gory detail, view the project on GitHub (2017).

I updated and ported the library to TypeScript – it’s also on GitHub (2024).

Linked Lists

In order to implement the event queue and the status stack we will use a double linked list. This is handy because we need to look at elements directly around us, and insert elements randomly.

I won’t show the entire linked list implementation (you can read it if you want), but will highlight the basic API:

// create a linked list
var list = LinkedList.create();

// have some data we need stored
var data = {
  some: 'data',
  here: 1,
  hello: 'world'
};

// mutate the data object to have next/prev/remove
data = LinkedList.node(data);

console.log(data);
=> {
  some: 'data',
  here: 1,
  hello: 'world',
  next: null,
  prev: null,
  remove: function(){ ... }
}

// insert the node into the list at a location
list.insertBefore(data, function(node){
  // perform some check between `data` and the current `node`
  // if we want to insert `data` before `node`, return true
  // otherwise, return false
  return true;
});

// after insertion, we can remove the node via:
data.remove();

// search the list
var transition = list.findTransition(function(node){
  // keep checking for a condition
  // keep returning false until the condition is true
  if (someCondition(node))
    return true;
  return false;
});

// `transition` will contain the nodes before and after the
// condition changed from false to true
console.log(transition);
=> {
  before: nodeBeforeTransition or null,
  after: nodeAfterTransition or null,
  insert: function(node){ ... }
}

// insert `data` where the transition happened
transition.insert(data);

Initializing Events

First, let’s start with converting a region (which is a list of points), into a series of segments to be added into the event queue:

// create the event linked list
var event_root = LinkedList.create();

// convert a region to a series of segments
function eventAddRegion(region){
  // regions are a list of points:
  //  [ [0, 0], [100, 0], [50, 100] ]
  var pt1;
  var pt2 = region[region.length - 1];
  for (var i = 0; i < region.length; i++){
    pt1 = pt2;
    pt2 = region[i];

    var forward = pointsCompare(pt1, pt2);
    // if points are equal, we have a zero-length segment
    if (forward === 0)
      continue; // just skip it

    eventAddSegment(
      segmentNew(
        forward < 0 ? pt1 : pt2,
        forward < 0 ? pt2 : pt1
      )
    );
  }
}

For now, a segment is very simple:

function segmentNew(start, end){
  return {
    start: start,
    end: end
  };
}

Notice that eventAddRegion doesn’t care about the order the vertices are specified – it cares about which vertex will become the Start event, and which will become the End event.

It decides this using pointsCompare:

function pointsCompare(p1, p2){
  // returns:
  //   -1 if p1 is smaller
  //    0 if equal
  //    1 if p2 is smaller

  if (p1[0] === p2[0]) // are we on the same vertical line?
    if (p1[1] === p2[1]) // are we the same exact point?
      return 0;
    return p1[1] < p2[1] ? -1 : 1; // compare Y values
  }
  return p1[0] < p2[0] ? -1 : 1; // compare X values
}

Notice that we only compare the Y coordinates if the X coordinates are the same.

Next, converting a segment into the Start and End events:

function eventAddSegment(seg){
  var ev_start = eventAddSegmentStart(seg);
  eventAddSegmentEnd(ev_start, seg);
  return ev_start;
}

function eventAddSegmentStart(seg){
  var ev_start = LinkedList.node({
    isStart: true,
    pt: seg.start,
    seg: seg,
    other: null,
    status: null
  });
  eventAdd(ev_start, seg.end);
  return ev_start;
}

function eventAddSegmentEnd(ev_start, seg){
  var ev_end = LinkedList.node({
    isStart: false,
    pt: seg.end,
    seg: seg,
    other: ev_start,
    status: null
  });
  ev_start.other = ev_end;
  eventAdd(ev_end, ev_start.pt);
}

An event contains:

1. isStart – a flag that distinguishes between Start and End events
2. pt – the point associated with this event
3. seg – the segment that generated this event
4. other – the sister event (Start’s other points to its End, and vice-versa)
5. status – the future node inside the status stack

Also notice we have to manually pass along the event’s other point to eventAdd as the second parameter. Normally we would just follow the other field in the event – but when adding the Start event, the other field will be null because we haven’t created the End event yet.

Using our linked list API makes eventAdd pretty easy:

function eventAdd(ev, other_pt){
  event_root.insertBefore(ev, function(here){
    // should ev be inserted before here?
    var comp = eventCompare(
      ev  .isStart, ev  .pt,      other_pt,
      here.isStart, here.pt, here.other.pt
    );
    return comp < 0;
  });
}

We compare the two events – specifically, we need to know whether they are Start or End events, what point the event represents, and the other point.

Lastly, the function responsible for determining the order of the events:

function eventCompare(
    p1_isStart, p1_1, p1_2,
    p2_isStart, p2_1, p2_2
  ){
  // returns:
  //   -1 if p1 is smaller
  //    0 if equal
  //    1 if p2 is smaller

  // compare the selected points first
  var comp = pointsCompare(p1_1, p2_1);
  if (comp !== 0)
    return comp;
  // the selected points are the same

  // if the non-selected points are the same too...
  if (pointsCompare(p1_2, p2_2) === 0)
    return 0; // then the segments are equal

  // if one is a start event and the other isn't...
  if (p1_isStart !== p2_isStart){
    // favor the one that isn't the start
    return p1_isStart ? 1 : -1;
  }

  // otherwise, we'll have to calculate which one is below the
  // other manually
  return pointAboveOrOnLine(p1_2, p2_1, p2_2) ? 1 : -1;
}

This function is essential to understand. Every line is important, and if you get it wrong, you will have some nasty bugs.

First we compare the selected points. If the points aren’t equal, then it’s easy: the order is simply the same as whatever pointsCompare gives us.

If the selected points are the same, then that means the two events are right on top of each other.

Which one goes first?

Well, if the other points are also the same, then it doesn’t matter. The segments are equal, and will eventually be combined by the event loop.

If one of the points is a Start event, and the other is an End event, then we want the End event to go first.

Why? Because an End event means removing a segment from the status. We should remove a segment before inserting a new one, otherwise when inserting the new one, one of its neighbors will be a segment that cannot possibly intersect with it.

Lastly, we’re dealing with segments that share a common start point or common end point:

In this case, we need to carefully figure out which segment is on top. We do that by manually calculating whether the other point is above the line made by p2’s points, via pointAboveOrOnLine.

Event Loop

Now that we have events, let’s process the event loop:

// create the status stack
var status_root = LinkedList.create();

function eventLoop(){
  var segments = [];
  while (!event_root.isEmpty()){
    var ev = event_root.getHead();

    if (ev.isStart){
      // find the insertion location of ev
      var transition = statusFindTransition(ev);

      // figure out the events that are above and below this
      // event
      var above = null;
      if (transition.before)
        above = transition.before.ev;
      var below = null;
      if (transition.after)
        below = transition.after.ev;

      // check for intersections between ev and whoever is
      // above and below it
      var eve = checkBothIntersections(ev, above, below);
      if (eve){
        // ev and eve are equal
        // we'll keep eve and throw away ev

        // update eve.seg's fill annotations based on ev.seg
        // TODO: this

        ev.other.remove();
        ev.remove();
        continue;
      }

      // if there were intersections, then new events would
      // have been inserted... those new events *could* be
      // required to be processed before this event
      if (event_root.getHead() !== ev){
        // something was inserted before us in the event
        // queue, so loop back around and process it first
        continue;
      }

      // calculate fill annotations
      // TODO: this

      // create the status node
      var st = LinkedList.node({ ev: ev });

      // insert the node at the transition location
      transition.insert(st);

      // remember the node for later
      ev.other.status = st;
    }
    else{
      // this segment is ending, so we no longer have to worry
      // about future segments intersecting with it...

      // processing end event, so grab the previously inserted
      // status node
      var st = ev.status;

      // removing the status will create two new adjacent
      // edges, so we need to check for those
      if (status_root.exists(st.prev) &&
        status_root.exists(st.next)){
        // new adjacent edges exist, so check for further
        // intersections
        checkIntersection(st.prev.ev, st.next.ev);
      }

      // remove the status
      st.remove();

      // save the segment
      segments.push(ev.seg);
    }

    // remove the event and continue
    event_root.getHead().remove();
  }

  return segments;
}

This is the engine that processes events, and is the core of our entire algorithm.

Some things to notice:

1. checkBothIntersections might detect that ev’s segment is the same as another segment – which results in throwing away ev entirely and keeping the previously processed segment.
2. Events are not removed until after checking for intersections and confirming that no events created from the intersections should be processed first.
3. When we remove a segment from the status, we have a special check for newly adjacent segments.
4. We only save the segments that finish this process.

There is still a lot to go over when checking for intersections, and we will be adding to this core loop when calculating fill annotations, but this is the essence.

Checking for Intersections

Checking for intersections between the current event and whatever is above and below it is simple:

function checkBothIntersections(ev, above, below){
  if (above){
    var eve = checkIntersection(ev, above);
    if (eve)
      return eve;
  }
  if (below)
    return checkIntersection(ev, below);
  return false;
}

The complicated part is checkIntersection.

First let’s start with the easy case:

function checkIntersection(ev1, ev2){
  // returns the segment equal to ev1
  // or false if nothing equal

  var seg1 = ev1.seg;
  var seg2 = ev2.seg;
  var a1 = seg1.start;
  var a2 = seg1.end;
  var b1 = seg2.start;
  var b2 = seg2.end;

  var i = linesIntersect(a1, a2, b1, b2);

  if (i === false){
    // segments are parallel or coincident
    // ... special logic here ...
  }
  else{
    // otherwise, lines intersect at i.pt, which may or may
    // not be between the endpoints

    // is A divided between its endpoints? (exclusive)
    if (i.alongA === 0){
      if (i.alongB === -1) // yes, at exactly b1
        eventDivide(ev1, b1);
      else if (i.alongB === 0) // yes, between B's endpoints
        eventDivide(ev1, i.pt);
      else if (i.alongB === 1) // yes, at exactly b2
        eventDivide(ev1, b2);
    }

    // is B divided between its endpoints? (exclusive)
    if (i.alongB === 0){
      if (i.alongA === -1) // yes, at exactly a1
        eventDivide(ev2, a1);
      else if (i.alongA === 0) // yes, between A's endpoints
        eventDivide(ev2, i.pt);
      else if (i.alongA === 1) // yes, at exactly a2
        eventDivide(ev2, a2);
    }
  }
  return false;
}

The linesIntersect function performs the grunt of the raw calculation.

If it returns false, then the lines are coincident, and we need to handle the six cases we discussed above.

Otherwise, we check to see where the intersection occurs by looking at i.alongA and i.alongB.

These are set to specific values depending on where the intersection occurs by linesIntersect.

Each case that results in a division is checked for, and if a segment needs to be divided, the eventDivide function is called with the event that is divided, and the division point.

function eventDivide(ev, pt){
  var ns = segmentCopy(pt, ev.seg.end, ev.seg);
  eventUpdateEnd(ev, pt);
  return eventAddSegment(ns, ev.primary);
}

function eventUpdateEnd(ev, end){
  // slides an end backwards
  //   (start)------------(end)    to:
  //   (start)---(end)

  ev.other.remove();
  ev.seg.end = end;
  ev.other.pt = end;
  eventAdd(ev.other, ev.pt);
}

There are a few ways you could divide a segment.

I start by creating the segment that represents the right side of the intersection by copying the segment that is being divided.

Then I update the current event’s segment’s end point, and re-insert the updated End event.

Lastly, I add the new segment’s events to the event queue.

Concident Lines

Before finishing checkIntersection, we need to fill in the special handling for coincident lines:

// segments are parallel or coincident

// if points aren't collinear, then the segments are parallel
// so no intersections
if (!pointsCollinear(a1, a2, b1))
  return false;
// otherwise, segments are on top of each other somehow

// if segments touch at endpoints, then no intersection
if (pointsSame(a1, b2) || pointsSame(a2, b1))
  return false;

var a1_equ_b1 = pointsSame(a1, b1);
var a2_equ_b2 = pointsSame(a2, b2);

// if segments are exactly equal, return the equal segment
if (a1_equ_b1 && a2_equ_b2)
  return ev2;

var a1_between = !a1_equ_b1 && pointBetween(a1, b1, b2);
var a2_between = !a2_equ_b2 && pointBetween(a2, b1, b2);

if (a1_equ_b1){
  if (a2_between){
    //  (a1)---(a2)
    //  (b1)----------(b2)
    eventDivide(ev2, a2);
  }
  else{
    //  (a1)----------(a2)
    //  (b1)---(b2)
    eventDivide(ev1, b2);
  }
  // we've created equal segments, so throw away ev1 because
  // it is equal to ev2
  return ev2;
}
else if (a1_between){
  if (!a2_equ_b2){
    // make a2 equal to b2
    if (a2_between){
      //         (a1)---(a2)
      //  (b1)-----------------(b2)
      eventDivide(ev2, a2);
    }
    else{
      //         (a1)----------(a2)
      //  (b1)----------(b2)
      eventDivide(ev1, b2);
    }
  }

  //         (a1)---(a2)
  //  (b1)----------(b2)
  eventDivide(ev2, a1);
}

This looks like a lot, but it really isn’t. If you work through each case individually, it all makes sense.

First, we make sure we’re dealing with lines that lay on top of each other.

If they are exactly equal, we return ev2, which has the effect of discarding ev1 in the event loop.

Then we use pointsBetween to calculate which of the remaining five cases we have.

The only thing that might be confusing is: why do we return ev2 under the first if-block, but we don’t return anything under the else if-block? After all, aren’t there equal segments?

Yes: there are equal segments. But neither of those segments is in the status stack.

Since (b1)---(b2) is being divided by (a1), the only segment in the status will be the updated segment (b1)---(a1). That segment isn’t the same as any other segment.

The fact that (a1)---(a2) is the same as (a1)---(b2) will be detected later, because those segments are entirely in the event queue.

Finding the Status Transition

The last thing to explain about the event loop is statusFindTransition.

Remember that we don’t insert into the status stack immediately – first we locate where the insertion would happen, so we can grab the segments above and below the segment currently being processed.

function statusFindTransition(ev){
  return status_root.findTransition(function(here){
    var comp = statusCompare(ev, here.ev);
    return comp > 0; // top to bottom
  });
}

function statusCompare(ev1, ev2){
  var a1 = ev1.seg.start;
  var a2 = ev1.seg.end;
  var b1 = ev2.seg.start;
  var b2 = ev2.seg.end;

  if (pointsCollinear(a1, b1, b2)){
    if (pointsCollinear(a2, b1, b2))
      return 1; // doesn't matter, as long as it's consistent
    return pointAboveOrOnLine(a2, b1, b2) ? 1 : -1;
  }
  return pointAboveOrOnLine(a1, b1, b2) ? 1 : -1;
}

The statusCompare function determines the sort of the status stack.

Given two events, which ones goes first in the status stack?

We want to sort the status stack from top to bottom. This way, when finding the insertion location of a new event in the status stack, we will be able to look directly above and below the insertion point to see the two lines we need to check intersections against.

So our sort is simply calculating which line is above the other.

If a1 is above or below the other line, then we have our answer.

If a1 is collinear, then we’ll need to check a2 instead.

Lastly, if both a1 and a2 are collinear to the other line, then that means the two lines are collinear – so the sort doesn’t really matter, as long as they end up next to each other.

Calculating Annotations

At this point, we have an outline of a system that can take a list of lines and sweep through them, detecting intersections and splitting the lines into segments – and combine segments that perfectly overlap so we never have multiple segments in the same location.

Now: how do we calculate the apporpriate fill annotations as we move through this process?

Desired Combined Fill Annotations

Actually, it’s quite messy!

There is a secret that makes it significantly easier:

We run the vertical line sweep three times:

1. Sweep just the red polygon, checking for self-intersection, calculating just the red fill annotation
2. Sweep just the blue polygon, checking for self-intersection, calculating just the blue fill annotation
3. Sweep through the segments generated in steps 1 and 2, checking for intersections between the polygons, calculating the final combined fill annotations

In order to understand why we need to sweep three times, we first need to look at how to calculate the fill annotations for a single polygon.

Storing Annotations

Storing the annotation information is easy – we’ll just add it to the segment:

function segmentNew(start, end){
  return {
    start: start,
    end: end,
    myFill: {
      above: null, // is there fill above us?
      below: null  // is there fill below us?
    },
    otherFill: null
  };
}

There are three states: null means we haven’t calculated the fill yet, and true/false are the result of the calculation.

Notice we also have a distinction between myFill and otherFill – when annotating a single polygon, we’ll fill out the myFill information. When performing our third sweep to combine the polygons, we’ll fill out the otherFill information.

Annotating a Single Polygon

The Bentley-Ottmann intersection algorithm has a beautiful feature that is incredibly useful for calculating fill annotations:

For every segment that is added to the status, we know the segment directly below it.

That is all you need to know in order to calculate the new segments fill annotation.

// calculate fill annotations

var toggle; // are we a toggling edge?
if (ev.seg.myFill.below === null) // if we are a new segment...
  toggle = true; // then we toggle
else // we are a segment that has previous knowledge
  toggle = ev.seg.myFill.above !== ev.seg.myFill.below;

// next, calculate whether we are filled below us
if (!below){ // if nothing is below us...
  // we are filled below us if the polygon is inverted
  ev.seg.myFill.below = primaryPolyInverted;
}
else{
  // otherwise, we know the answer -- it's the same if whatever
  // is below us is filled above it
  ev.seg.myFill.below = below.seg.myFill.above;
}

// since now we know if we're filled below us, we can calculate
// whether we're filled above us by applying toggle to whatever
// is below us
if (toggle)
  ev.seg.myFill.above = !ev.seg.myFill.below;
else
  ev.seg.myFill.above = ev.seg.myFill.below;

The first observation is that:

• If we have a segment below us, then we are filled below us if the segment below us is filled above it.
• If we don’t have a segment below us, then we are at the bottom – and we are filled below us if the polygon is inverted.

That’s easy.

The second observation is that once we know whether we’re filled below us, we can calculate whether we’re filled above us:

• If we are a segment that toggles the fill status, then we are filled above us if and only if we aren’t filled below us.
• If we are a segment that doesn’t toggle the fill status, then we are filled above us if and only if we are filled below us.

This is a little more complicated. What does it mean to be a toggling segment, and why do we need this?

Remember that segments that perfectly overlap will become merged.

Suppose we merge two segments, and both of them are empty below, and filled above. The resulting segment should be empty below and empty above!

The bottom segment is a non-toggling segment. The fill below it is equal to the fill above it (both false in this case).

Therefore, once we know the fill status below a segment, and we know whether the segment is toggling or not, we can calculate the fill status above:

var toggle; // are we a toggling edge?
if (ev.seg.myFill.below === null) // if we are a new segment...
  toggle = true; // then we toggle
else // we are a segment that has previous knowledge
  toggle = ev.seg.myFill.above !== ev.seg.myFill.below;

...

if (toggle)
  ev.seg.myFill.above = !ev.seg.myFill.below;
else
  ev.seg.myFill.above = ev.seg.myFill.below;

New segments default to toggling segments. Previously divided segments (created via segmentCopy inside of eventDivde) will have fill information from previous merges, and that information will determine whether the segment is toggling or not.

Annotating During Merges

Lastly, when merging two segments, we need to update the surviving segment’s fill information, as described above.

If the intersection function determines that ev is a duplicate segment, it will return eve, which is the surviving segment:

// update eve.seg's fill annotations based on ev.seg
var toggle; // is the discarded edge a toggling edge?
if (ev.seg.myFill.below === null)
  toggle = true;
else
  toggle = ev.seg.myFill.above !== ev.seg.myFill.below;

// merge two segments that belong to the same polygon
// think of this as sandwiching two segments together, where
// `eve.seg` is the bottom -- this will cause the above fill
// flag to toggle
if (toggle)
  eve.seg.myFill.above = !eve.seg.myFill.above;

This one is a little trickier to visualize, because the segments are right on top of each other.

Since fill status is calculated bottom to top, the surviving segments below fill status is already calculated and can’t change.

The surviving segment’s above fill status will become whatever the discarded segment’s above fill status would have been.

The discarded segment’s below fill status would have been the same as the surviving segment’s above fill status.

The discarded segment’s above fill status would have been calculated by toggling its below fill status.

Therefore, if the discarded segment was a toggling segment, then we need to toggle the surviving segment’s above fill status.

What a mouthful!

Combined Fill Annoations

This is the last hard part, then we’re home free.

After performing the self-intersection phase on both polygons, and annotating them during that process, we have the following information:

Now we perform a third intersection sweep. This sweep will be the exact same as the ones before, except now we have to change our logic for calculating fill annotations.

So we will be swapping out the main fill annotation calculation, along with the logic when merging segments.

Let’s start with the logic for merging segments, since that’s easy.

Once again, ev is the discarded segment, and eve is the surviving segment:

// merge two segments that belong to different polygons
// each segment has distinct knowledge, so no special logic is
// needed -- note that this can only happen once per segment
// in this phase, because we are guaranteed that all
// self-intersections are gone
eve.seg.otherFill = ev.seg.myFill;

Oh my goodness, finally an easy situation!

Anytime segments are merged during the third sweep we are guaranteed that the segments belong to different polygons, because the first two sweeps removed all self-intersections.

Therefore, when merging two segments, simply copy over the fill information!

And now the harder part – how to calculate otherFill of a final segment:

if (ev.seg.otherFill === null){
  // if we don't have other information, then we need to figure
  // out if we're inside the other polygon
  var inside;
  if (!below){
    // if nothing is below us, then we're inside if the other
    // polygon is inverted
    if (ev.primary)
      inside = secondaryPolyInverted;
    else
      inside = primaryPolyInverted;
  }
  else{ // otherwise, something is below us
    // so copy the below segment's other polygon's above
    if (ev.primary === below.primary)
      inside = below.seg.otherFill.above;
    else
      inside = below.seg.myFill.above;
  }
  ev.seg.otherFill = {
    above: inside,
    below: inside
  };
}

First, if otherFill isn’t null, then it’s already been calculated from a previous merge – so don’t overwrite it!

Otherwise, the otherFill is determined by whether this segment is inside the other polygon.

If we don’t have anything below us, then we are inside the other polygon if it is inverted.

Otherwise, we can check the segment below us.

If we both belong to the same polygon, then we are inside the other polygon if the below segment is filled above it by the other polygon (via below.seg.otherFill.above).

If we belong to different polygons, then we are inside the other polygon if the below segment is filled above it (via below.seg.myFill.above).

The ev.primary, primaryPolyInverted, and secondaryPolyInverted variables are simply wired when the third phase begins, based on where the source segments come from. Easy.

Resulting Segments

One minor bookkeeping point: before saving the final segment to the results, we will swap myFill and otherFill if the segment was sourced from the secondary polygon. This means our resulting polygons will consistently have the primary fill status in myFill and the secondary fill status in otherFill, no matter where the segment came from.

// if we've reached this point, we've calculated everything
// there is to know, so save the segment for reporting
if (!ev.primary){
  // make sure `seg.myFill` actually points to the primary
  // polygon though
  var s = ev.seg.myFill;
  ev.seg.myFill = ev.seg.otherFill;
  ev.seg.otherFill = s;
}

// save the segment
segments.push(ev.seg);

Combined Knowledge

Let’s take a short break, and bask in the beauty of what we’ve calculated so far:

We have a list of unique segments that do not have any intersections and are annotated with the fill status of each polygon.

We’ve still got some work to do, but it’s significantly easier from here.

Selecting Resulting Segments

Once we have a fully annotated list of segments, we can select the resulting segments based on the boolean operator (intersection, union, difference, xor).

As an added bonus, if we’re smart, we can also calculate the future fill status of the segments. This is great if the user wants to perform multiple operations on the same data (for example, taking the union of three polygons by unioning two polygons, then unioning the third with the result).

After all – why not? We are guaranteed the resulting segments don’t intersect, so we can skip the self-intersection phase entirely for future calculations.

Union

Let’s walk through how to calculate union, and the same process can be used for calculating the other operators:

For each segment, there are four booleans, which results in 16 states to consider:

• Above 1: Primary polygon filled above? Yes/no
• Below 1: Primary polygon filled below? Yes/no
• Above 2: Secondary polygon filled above? Yes/no
• Below 2: Secondary polygon filled below? Yes/no

Considering our operation, we just need to answer the following question for each state:

• Do we keep this segment?
• If so, is the resulting segment filled above or below?

Well, let’s get to work:

How do you calculate each row?

Well, there’s no real secret… just go row by row, and visualize it.

If the segment is filled above and below it, then we don’t want to keep it – it’s worthless in a union.

If a segment is filled at least once on one side, then we want to keep it – and our fill status will be whatever side was filled.

Encoding the Table

How do we represent the table in code? I decided on an array of 16 elements, where 0 represents ditching the segment, 1 represents filled above, and 2 represents filled below.

The index in the array is determined by interpreting the flags as bits. So “No, Yes, No, No” is “0100”, which is index 4.

That means our five operations are defined by a 16 element array:

// union
[
  0, 2, 1, 0,
  2, 2, 0, 0,
  1, 0, 1, 0,
  0, 0, 0, 0
]

// intersect
[
  0, 0, 0, 0,
  0, 2, 0, 2,
  0, 0, 1, 1,
  0, 2, 1, 0
]

// difference (primary - secondary)
[
  0, 0, 0, 0,
  2, 0, 2, 0,
  1, 1, 0, 0,
  0, 1, 2, 0
]

// difference (secondary - primary)
[
  0, 2, 1, 0,
  0, 0, 1, 1,
  0, 2, 0, 2,
  0, 0, 0, 0
]

// xor
[
  0, 2, 1, 0,
  2, 0, 0, 1,
  1, 0, 0, 2,
  0, 1, 2, 0
]

Pretty cool, huh?

Lastly, given a list of segments, and an operation array, perform the selection:

var result = [];
segments.forEach(function(seg){
  var index =
    (seg.myFill.above ? 8 : 0) +
    (seg.myFill.below ? 4 : 0) +
    ((seg.otherFill && seg.otherFill.above) ? 2 : 0) +
    ((seg.otherFill && seg.otherFill.below) ? 1 : 0);
  if (selection[index] !== 0){
    // copy the segment to the results, while also calculating the fill status
    result.push({
      start: seg.start,
      end: seg.end,
      myFill: {
        above: selection[index] === 1, // 1 if filled above
        below: selection[index] === 2  // 2 if filled below
      },
      otherFill: null
    });
  }
});

Again, this should be fairly easy to understand at this point.

Segment Chaining

But wait – now we have a list of segments, each of which contain a start and end point. How do we convert this back to a polygon?

A polygon is a list of regions – not a list of segments.

It’s not that hard.

The basic algorithm is to keep a list of open chains.

When we process a segment, search to see if it can be added to the end of any open chains.

If it can’t be added to a chain, then create a new open chain with the single segment inside of it.

If it can be added to two open chains, then combine the chains into a single open chain.

Otherwise, if it is only added to a single open chain, then we’ll need to check if adding the segment causes the chain to close. If so, close the chain and add it to the region list (and remove it from the list of open chains).

While doing all this, we can go one step further and combine collinear segments. That gets rid of unneccessary verticies in the result without too much extra processing.

Since the algorithm is pretty straight forward, instead of listing the code, I will just link to it here. You can see it behaves exactly as I’ve described.

Done!

Amazingly, we’re done!

And thankfully, I’ve already written the entire algorithm in an easy to use library, published on GitHub (2017)!

I updated and ported the library to TypeScript – it’s also on GitHub (2024).

On top of that, I’ve also written an interactive demo:

Demo Screenshot

You can cycle through different test cases, change the operation, and watch an animation of the algorithm as it calculates the intersections and fill annotations, then chains the resulting segments together.

The project is released under the MIT license, but this article is © Copyright 2016 Sean Connelly, with All Rights Reserved.

Tags: 2d, Geometry, Javascript

View All Posts