Polygons play a major role in a lot of visualization applications. Besides the possibility of drawing polygons, there is neither an explicit presentation of polygon data nor are common polygon operations supported in ActionScript. As far as I know, there is no simple solution available that solves the following geometrical problems for simple 2D polygons, so I wrote one.

• Computation of the polygon area and the location of its centroid (which means the center of its mass)
• Mesh simplification for faster rendering at lower resolutions
• Computation of bounding geometry like bounding box and the convex hull
• Deciding whether a given point or circle is inside a polygon or not (“Point in Polygon”)
• Determining whether a given set of polygon points are sorted in clockwise- or counter-clockwise order
• Computation of intersecting points between a line and a polygon The following code shows the implemented interface:

package net.vis4.geom
{
	import flash.geom.Point;
	import flash.geom.Rectangle;

	public interface IPolygon
	{
		function get points():PointSet;
		function get area():Number;
		function get centroid():Point;
		function get boundingBox():Rectangle;
		function get convexHull():IPolygon;
		function simplify(radius:Number):IPolygon;
		function containsPoint(point:Point):Boolean;
		function containsCircle(circle:Circle):Boolean;
		function get sortedClockwise():Boolean;
		function intersectLine(line:Line):Array;
	}
}

The class uses another class PointSet which is an extension of the native actioscript-array and provides type-safety and some simple computations. I implemented the following well known algorithms to solve the stated problems:

• Area & Centroid: I used the algorithm by Paul Bourke as shown here.
• Convex Hull: I used Melkman’s Algorithm to compute the convex hull.
• Simplification: I used the simple and fast vertex reduction algorithm for polygon simplification.
• Point in Polygon: I used the simple scanline algorithm as shown here. The whole point set is only tested, if the given point lies inside the bounding box and inside the convex hull.

The following flash movie demonstrates the usage:

You can download the classes via bitbucket.org.

Comments

World Map of Internet Adresses | vis4 | information visualization (Jan 12, 2010)

[…] created this visualization using ActionScript, based on my classes for map projections and polygon maths, which you can download for own usage. The data was extracted from the free GeoLite-City database […]