Submit to StumbleUpon Share

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 Share