Math Installment #4: Bounding Regions
There may already be a few entries on bounding regions that I posted many months ago. At one point I think I described some different types of bounding region scenarios including strict and relaxed fit scenarios. To add some math to this a strict region fit is going to inscribe the shape that it is bounding. We'll take a look at inscribing a number of shapes inside of a bounding circle. A relaxed fit reverses the equation with the region begin inscribed inside of the shape.
Inscribing Shapes
I actually gave this as a challenge to Darren, but didn't really tell him how much it would aid him later. Inscribed shapes can be reduced to interpolated points along the curve of the circle. For instance, an equilateral triangle is simply three points equally spaced around the inside of the circle. Being three points we can divide the 360 degrees by 3, get 120, and each point has to be 120 degrees apart. You can rotate the triangle anywhere in the circle by picking a different starting angle and then adding 120 and 240 degrees respectively when computing the remaining points.
startAngle = ???
offsetAngle = 360 / n
point0angle = startAngle + (offsetAngle * 0)
...
pointnangle = startAngle + (offsetAngle * n)
Computing the locations of each point using the previously defined trig methods is easy. Plot the points, draw lines between them, and what you get is a shape of some number of points where every point touches the circle and the shape is entirely contained within the circle. What about computing the bounding circle for a given shape? Well this is a bit different, especially if the shape isn't regular. But let's see what we can do.
First, you start by taking the distance between all of the points or extremes in the shape. For a triangle, you'll be computing three edges or the distance between all three points. The longest distance becomes your diameter or taken by one half and you get your radius. The center point of the bounding circle is the center point of the longest line. As you start to get larger numbers of points in the shape or polygon, the number of distance checks that must occur increases geometrically. For four points you'll have to do 6 distance checks and for five points you are up to 10.
; Bounding circle for a triangle
radius = max(d(p1, p2), d(p2, p3), d(p3, p1)) / 2
center = mid(p?, p?)
; Bounding helpers for other shapes
distance checks = n(n-1)/2
Now you should be able to inscribe any regular shape given a circle and then turn around an create a bounding circle given any regular or irregular polygon.
Circumscribing Shapes
When you circumscribe a shape, you generally draw it such that it contains a circle using the least bounding area. Every edge of the circumscribed shape is drawn tangent to the circle so that it brushes it at a single point. You might think this process is hard, but it is actually quite easy if you recall that any regular shape can be quickly and easily drawn within a circle. That means we simply need the radius of the inscribing circle for the circumscribing shape. Confused?
Don't be. Making this realization only makes our life easier. It means that if we find a single point for the circumscribing shape, we can use that point to find the rest of them with ease. Finding a single point involves making use of the trigonemtric sine rules that allow us to take any two angles and a side and get the length of the remaining sides. Take a look at the figure for getting the first point of a circumscribing square. We are using a square for now because it is pretty easy.
We start by making the following assertions. The angle from the center of the circle to two points on the circumscribing square is going to be 360 / n. This is called the internal angle and is the same angle we used earlier for inscribing shapes as well. Now, we extend the legs of a triangle beyond the radius of the circle until the third leg drawn opposte our internal angle touches the circle at only one point. The distance from the center to where the point touches is the radius or Cr. This will be important given information in a second.
Because the far leg is drawn tangent to the circle, the radius is perfectly perpindicular. That means the radius forms a right angle with the tangent line breaking our larger triangle T(C, P1, P2) into two triangles T(C, P1, T1) and T(C, P2, T1) where C is the center point, P1 and P2 are the points on the circumscribing square we are creating and T1 is the tangent point. By definition the radius also becomes a perpindicular bisector splitting that internal angle of ours from 360 / n in half to 360 / n / 2. The third angle or cross side angle is whatever is left of the 180 degrees allowed in a triangle. We now have three angles and a side. The following sin rules now apply:
sideA / sin(angleA) = sideB / sin(angleB) = sideC / sin(angleC)
In the example, sideA will be Cr, angleA will be the cross side angle and angle b will be 90 degrees. This reduces the sideB equation to:
Cr / sin(cross side angle) * sin(90) = sideB
sin(90) = 1
Cr / sin(cross side angle) = sideB
Frigin sweet. We have a basic equation that gives us the distance between the center of our circle to the first point in the circumscribing square. Use this distance as the radius of a new circle given the center of the original. Now, inscribe the rest of the square within this larger circle and you are done. You've just circumscribed the circle within a square. You could just as easily have used another shape though.
Cr / sin(90 - (Internal Angle / 2)) = distance to point
Cr = 100
; Triangle
100 / sin(90 - (120 / 2)) = 200
; Square
100 / sin(90 - (90 / 2)) = 141
; Hexagon
100 / sin(90 - (72 / 2)) = 123.6
; Pentagon
100 / sin(90 - (60 / 2)) = 115
This is some of the basic math behind creating anywhere from simple to complex bounding regions. You can see where this might come in handy if you have a complex shape that you might need to create a clipping region for. You can start by creating a bounding circle and then using it to circumscribe a bounding square that can be used for the clipping region.
Where this really comes into play is clipping systems for sprite functions. A simple or complex sprite can easily be examined to create a simple bounding region such as a circle. Depending on the application, this region may be too strict, so you can make it less strict by playing with some math and reworking the regions programmatically, rather than having to eyeball the final bounding regions. It's up to you, but hopefully this helps out a bit.