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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
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://www.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.

#### Want to learn more? Learn by example!

Get the full commented source code of an actual commercial cross platform HTML5 game!!

## Comments 7

Great Work Feronato!

Hi Emmanuel

It was wonderful as always.

Thank you

Great!, inspiring me since primary school :)

To create the destructible terrain from this,

I suppose the blue zone is the terrain, the small star is the explosion range, and the green (intersected) will be the zone to remove, but since box2d can’t remove zones like that, you created a new box2d polygon with the intersected vertex from the green zone and the blue zone, am i right?

Emmanuele, thanx for sharing! Good job, it helped me.

Hi, [getArea] function is works wrong with the shape http://my.jetscreenshot.com/3084/20130829-oopy-4kb, in my tests getArea() = 0 in this case :(

Author

It should be a perfect polygon, that is a polygon with no intersecting vertices