Emanuele Feronato

How to check if a polygon is completely inside another polygon

Talking about Actionscript 3 and Flash.

Checking if a polygon is completely inside another polygon is a very common problem in geometry, and most solutions you can find in the web aren’t that easy, especially when you are dealing with irregular polygons.

Today I want to show you a quick solution based on the PolygonClipper AS3 class.

Basically we can say a polygon called A is completely inside another polygon called B when the intersection between these two polygons returns the same polygon A.

So, mixing the concepts seen in understanding polygon clipping and introducing PolygonClipper AS3 class and AS3 code snippet: draw a star and determine its area I was able to do this prototype in a few minutes:

Use the mouse to move the small star and watch what happens when it’s inside the big star.

This is the commented source code:

package {
	import flash.display.Sprite;
	import flash.geom.Point;
	import flash.events.Event;
	import flash.text.TextField;
	import com.logicom.geom.Clipper;
	import com.logicom.geom.ClipType;
	public class Main extends Sprite {
		private var mainPolygon:Array;
		private var clipPolygon:Array;
		private var clipCanvas:Sprite=new Sprite();
		private var txt:TextField=new TextField();
		public function Main():void {
			var mainCanvas:Sprite=new Sprite();
			addChild(mainCanvas);
			// this is the main polygon
			mainPolygon=createStar(7,new Point(320,240),220,120,180);
			drawPolygon(mainPolygon,mainCanvas,0x0000FF);
			addChild(clipCanvas);
			addChild(txt);
			txt.width=200;
			addEventListener(Event.ENTER_FRAME,clip);
		}
		private function clip(e:Event):void {
			// clearing the canvas of the moving polygon
			clipCanvas.graphics.clear();
			// this is the polygon we want to check if it's completely inside the main polygon
			var clipPolygon:Array=createStar(5,new Point(mouseX,mouseY),100,70,0);
			// calculating the area of the moving polygon
			var clipArea:Number=getArea(clipPolygon);
			// drawing the moving polygon, using a red color
			drawPolygon(clipPolygon,clipCanvas,0xFF0000);
			// getting the polygons forming the intersection between the main polygon and the moving polygon
			var resultPolygons:Array=Clipper.clipPolygon(mainPolygon,clipPolygon,ClipType.INTERSECTION);
			// in totalArea variable we will sum the areas of all polygons (if more than one) forming the intersection
			// between the main polygon and the  moving polygon
			var totalArea:Number=0;
			// looping through all the polygons forming the intersection
			for (var i:int=0; i<=resultPolygons.length-1; i++) {
				// drawing the intersection polygon (that is the polygon inside the main polygon) with a green background
				drawPolygon(resultPolygons[i],clipCanvas,0x00FF00);
				// updating total area
				totalArea+=getArea(resultPolygons[i]);
			}
			// if the total intersection area is equal to the area of the moving polygon, we can say
			// the moving polygon is completely inside the main polygon
			if (totalArea==clipArea) {
				txt.text="COMPLETELY INSIDE";
			}
			else {
				// otherwise, let's show the ratio of the moving polygon inside the main polygon
				txt.text=Math.floor(totalArea/clipArea*100).toString()+"%";
			}
		}
		// simple function to draw a polygon given an array with vertices, a display object where to draw it and a fill color
		private function drawPolygon(polygon:Array,canvas:Sprite,color:Number):void {
			canvas.graphics.lineStyle(3,0x000000,1);
			canvas.graphics.beginFill(color,1);
			var n:uint=polygon.length;
			if (n<3) {
				return;
			}
			var p:Point=polygon[0];
			canvas.graphics.moveTo(p.x, p.y);
			for (var i:uint = 1; i <= n; ++i) {
				p=polygon[i%n];
				canvas.graphics.lineTo(p.x, p.y);
			}
			canvas.graphics.endFill();
		}
		// function to draw a star. More information at 
		// http://emanueleferonato.com/2013/06/22/as3-code-snippet-draw-a-star-and-determine-its-area/
		private function createStar(arms:int,center:Point,outer:Number,inner:Number,offsetAngle:Number):Array {
			offsetAngle*=0.0174532925;
			var starArray:Array=new Array();
			var r:Number;
			var angle:Number=Math.PI/arms;
			for (var i:int=0; i<2*arms; i++) {
				if ((i%2)==0) {
					r=outer;
				}
				else {
					r=inner;
				}
				starArray.push(new Point(Math.round(center.x+Math.cos(i*angle-angle/2+offsetAngle)*r),Math.round(center.y+Math.sin(i*angle-angle/2+offsetAngle)*r)));
			}
			return starArray;
		}
		// function to get the area of any polygon
		private function getArea(poly:Array):Number {
			var i:int=0;
			var j:int=0;
			var n:int=poly.length;
			var surface:Number=0;
			for (i=0; i<n; i++) {
				j=(i+1)%n;
				surface+=Point(poly[i]).x*Point(poly[j]).y;
				surface-=Point(poly[i]).y*Point(poly[j]).x;
			}
			surface=surface/2;
			return surface;
		}
	}
}

Checking if a polygon is inside another polygon is the last theoretical step before creating real physics destructible terrain, so download the source code and wait for the final prototype.