BIT-101

Super Triangle

Delaunay Triangulation

Recently I was working on implementing Delaunay triangulation using the Bowyer-Watson algorithm. I used the exact steps outlined in that link and, while fairly complex, it worked perfectly. There was just one point that was a bit more vague than the others.

add super-triangle to triangulation // must be large enough to completely contain all the points in pointList

Making the super Triangle

To visualize what we need, here’s an idea of what I had in front of me. I have a bunch of random points (actually created through Poisson disk sampling). These were distributed across the full canvas like the rectangle shown here:

For the first step of the formula, I needed a triangle that completely encompassed all of these points. To get things working at first, I just made a really huge triangle. But “really huge” wasn’t very mathematical. I tried creating increasingly larger triangles until all points tested as inside the triangle, but that was very brute-force and inelegant. I saw one method where you calculate the convex hull of all the points and iteratively use the points of that to create triangles and check the area of each triangle until you have the one with the smallest area. Neat, but WAY overkill, imo.

I had an idea in my head that if I could take the two left points of the rectangle and extend them up and down some amount, and then take the right midpoint of the rectangle and extend that more to the right some amount, I should wind up with a triangle that fit the rectangle.

My first shot at was to extend the left points up and down one screen height, and extend the right midpoint to the right one-half screen width. Using this formula:

triangle(
    x, y - h,
    x, y + h * 2,
    x + w * 1.5, y + h * 0.5,
)

Here, x and y are the top left corner of the rectangle (often 0, 0), and w and h are the width and height of the rectangle (generally the canvas size). I gave that a go and … lo and behold, it worked perfectly!

I was sure I just got lucky with my measurements, so I tried changing the size of the rectangle…

And it kept working perfectly. I love it when that happens.

Now, I’m not saying that this is the only triangle you can use, or even that it’s the best one, or even the one with the smallest area or … really anything other than:

1. It works.
2. It’s super easy to calculate.

I had one tiny concern though. There’s a chance that one of the points could end up at exactly x = 0.0 or close enough to potentially cause some kind of problem. I’m not entirely sure it would cause a problem, but I wanted to play it safe and give myself a little leeway just in case. So I made the triangle just a little bit larger be subtracting a bit off the x values on the left, and adding a bit on the right. Like this:

triangle(
    x - w * 0.1, y - h,
    x - w * 0.1, y + h * 2,
    x + w * 1.7, y + h * 0.5,
)

Here’s the result:

Now there’s no doubt at all that every point is safely inside the triangle.

In my library I made a function that iterates over the point list finding the min and max x and y values and uses that to create the triangle. It’s a bit more complex but it saves me from having to manually pass in the values to create the triangle. I just pass in the point list and all is done for me.

By the way, this is the result of Delaunay triangulation, which I’ll probably write something about at some point.

Comments? Best way to shout at me is on Mastodon

Or share this post directly on Mastodon