Fun with convex polygons

Figure 8
Submit to StumbleUpon

Hello and welcome back to my blog!

I wanted to talk about a couple of elegant ways of working with polygons that I’ve used over the years.

Simple convex polygon area

I’ve seen a lot of people go through and calculate the area of a polygon by breaking it up into separate triangles, carefully calculating the area of each, then sum and halve. This is all well and good, logical even, but there is a much shorter more elegant way of doing things:

public function GetArea( ):Number
{
	var area:Number = 0;
	for ( var i:int = 0; i<m_numPoints; i++ )
	{
		var A:Vector2 = m_localSpacePoints[i];
		var B:Vector2 = m_localSpacePoints[(i+1)%m_numPoints];
 
		area += A.Wedge( B );
	} 
 
	return area/2;
}

Believe it or not, this tiny code fragment will compute the correct area of a convex polygon, no matter what space the vertices are in. Looking at the code its hard to see what is going on. For reference, a description of the wedge product can be found here.

So lets make with the diagrams already:

Figure 1

Figure 1 shows the simplest of convex polygons with non-zero area, a triangle on the left and the right shows the vectors A and B from the code on the first iteration.

Figure 2

Figure 2 shows the the wedge product in action on the left – the area A^B is shown in pink, representing negative. An essential point to note is that the wedge product A^B is always negative when A is ‘above’ B – this is key to this process. On the right we can see the value of (A^B) / 2 which we end up summing in the code.

The above demo lets you experiment with the wedge product in real time – notice the negative result when A is above B?

Figure 3

Figure 3 shows iterations 2 and 3 of the routine. The green areas represent the positive value of A^B which is found in both of these iterations, since A is ‘below’ B in both iterations.

Figure 4

Now we start to get a good understanding of how this technique works. Figure 4 shows what we’re left with – a positive area on the left which is overly large since it includes triangles extending all the way to the origin and a negative area on the right which exactly matches this region which we don’t want to include in our area calculation.

Figure 5

After summing these negative and positive areas, what we’re left with is the correct area of the polygon as shown in Figure 5! This is why we don’t need to worry about what space the vertices are in, because the negative area always covers the region we don’t want to include.

This technique extends to polygons with any number of vertices, but they must always be convex, otherwise this ‘shadow removal’ wouldn’t work correctly.

Winding order

This technique relies on the winding order of the polygon being counter clockwise, as it is in this example. If you have opposite winding then your areas will have negative sign. You can use this property to confirm whether a given set of 2d polygon vertices have the correct winding order; if you expect counter clockwise winding but you get a negative area you can assert that the winding is incorrect.

Point inside poly

Another common routine to be over-engineered is the point within polygon query, again there is an elegant solution:

public function Within( localP:Vector2 ):Boolean
{
	for ( var i:int = 0; i<m_numPoints; i++ )
	{
		var A:Vector2 = m_localSpacePoints[(i+1)%m_numPoints].Sub( m_localSpacePoints[i] );
		var B:Vector2 = localP.Sub( m_localSpacePoints[i] );
 
		if ( A.Wedge( B )<0 )
		{
			// separating axis
			return false;
		}
	}
 
	return true;
}

This one requires that the candidate point be in the same space as the vertices of the polygon. Again, this works using the almighty wedge product – the property it has of being negative when B is on one ‘side’ of A and positive on the other is perfect for detecting a separating axis.

Figure 6

Figure 6 shows this property in more detail – B is on the positive ‘side’ of A.

Figure 7

Figure 7 shows a polygon and a candidate point on the left. The right shows the first iteration of the above routine – the wedge product A^B is positive in this case so no separating axis is detected.

Figure 8

Figure 8 shows the second and final iteration of the routine – A^B is negative and therefore a separating axis has been detected and the routine can terminate! We can terminate here because if the point is ever detected to have a separating axis, it can never be inside the polygon.

Again, this works on arbitrary convex polygons (including rectangles!) and is the simplest and most elegant way I know of to detect if a point is within a polygon.

That’s it for now… Until next time, have fun!

Cheers, Paul.

Submit to StumbleUpon

About Paul Firth

A games industry veteran of ten years, seven of which spent at Sony Computer Entertainment Europe, he has had key technical roles on triple-A titles like the Bafta Award Winning Little Big Planet (PSP), 24: The Game (PS2), special effects work on Heavenly Sword (PS3), some in-show graphics on the BBC’s version of Robot Wars, the TV show, as well as a few more obscure projects.   Now joint CEO of Wildbunny, he is able to give himself hiccups simply by coughing.   1NobNQ88UoYePFi5QbibuRJP3TtLhh65Jp
This entry was posted in AS3, Geometry, Graphics, Polygons, Technical and tagged , , , , , , . Bookmark the permalink.

12 Responses to Fun with convex polygons

  1. Jameson says:

    My boss and I re-derived the area of polygon method recently, although I think we came to the conclusion that it works for non-convex polygons a lot of the time, due to areas cancelling each other out. I think it even works with bow-tie-like shapes.

    As for the second, I hadn’t thought of doing it that way, and have always dotted with the right vector to get left or right of line. I think yours is computationally more efficient, and is easier to work in an arbitrary plane (if we go into 3-D).

  2. Tim says:

    Calculating the area is an example of using Green’s Theorem . It can also be extended to calculate the first and second moments of area by carefully choosing the potential function.

  3. Azur says:

    This can be extended to compute the area of any oriented, piecewise smooth, simple closed curve, see .

  4. Sergei says:

    Works for no convex non-selfintersecting polygons as well. Suffices to google before reinventing

  5. Michael says:

    This works for any simple (non self intersecting) polyline curve. Just use stokes theorem to prove it.

  6. dana says:

    This is correct in theory (which is great), but incomplete in context — which is computing actual areas, and getting useful numbers. The answer is to use existing, professional (and usually free) code, when possible (and practical — they trade some time for robustness (they know when they cannot compute a good result).

    As is well known, this algorithm will fail for many triangles due to the necessary use of floating-point calculations in finite precision. Most of the numerical problems (but not all) can be avoided through the use of more sophisticated algorithms: see Kahan’s website at Berkeley, or the CGAL library, BLAS (the “sdot” implementation, say), or the QHULL core for examples of how to avoid numerical problems inherent in these sort of geometric calculations.

    In fact, it looks like this algorithm will fail in practice when computing the area of congruent triangles, which differ in distance to the (arbitrary) origins (the length of the vectors A and B are large compared to the length of B-C, say), or the orientation of the triangle with respect to the origin (where the vector to B and C are nearly parallel).

    • Paul Firth says:

      Hi Dana,

      I’m afraid I have to disagree with your point about bringing in external libraries. The context is commercial game development – where resources are tight and there is complete domain knowledge. Often these libraries are GPLed making them impossible to include in a commercial game in practice.

      As for the algorithm not being robust, its been in use in a shipped game for a while without issues. If you are talking about degenerate or near degenerate triangles, you will find issues yes – but such triangles should generally be filtered out before they enter into production in the tools pipeline since they serve no purpose and just waste memory.

      The purpose of my articles is not to suggest the right and only way to do things, but to give the reader a better understanding, mentally preparing them to be able to tackle larger problems without having to constantly reach for assistance.

      Cheers, Paul.

  7. Stephen says:

    On the point-in-poly test, what cases were you thinking of when you said “over engineered”? I would use the winding number algorithm for point-in-poly, which has the benefit of working for any polygon, convex or not, and still remains elegant. For the convex case where they both work – they are both O(N)… do you reckon the winding number algorithm when implemented optimally to be significantly slower by its constant factor?

    • Paul Firth says:

      Hi Stephen,

      By over-engineered, I mean I’ve seen people write a point in triangle routine, and then break up a polygon into triangles and call that function for each one. While correct, its wasting a lot of calculations.

      I have to confess, I wasn’t aware of the winding-number technique, but I will certainly consider using it in the future, should I need to deal directly with non-convex polygons :)

      Cheers, Paul.

  8. Amit Patel says:

    I love the way you explain things, use diagrams, and provide demos. I keep your blog on my list of sites that inspire me when I’m in the mood to write. Thanks Paul!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing