Understanding polygon clipping and introducing PolygonClipper AS3 class

This is the second step in the creation of a Box2D (or Nape) destructible terrain without using bitmaps and marching squares rendering.

Let me do a small recap showing you some related, interesting posts about the topic:

* Using marching squares algorithm to trace the contour of an image – to trace the contour of a PNG image with transparency and turn it into a polygon.

* Reduce the number of points in a polygon with the Ramer-Douglas-Peucker algorithm – to reduce the number of points and vertices of the polygon.

* Polygon triangulation: decomposition of a polygon into triangles with AS3 – to split polygons in triangles.

* Create non-convex, complex shapes with Box2D – to make Box2D able to triangulate complex shapes and render them correctly.

* From PNG to Box2D – first attempt – putting all together.

The final example worked, but it did not allow me to create polygon with holes. The final goal of making a destructible terrain is the capability of adding holes in it.

So I played a bit with poly2tri class, which allows holes but does not want holes to overlap or break polygon perimeter.

Next step is using a library which handles polygon clipping. Angus Johnson made a Delphi script which manages difference, intersection, exclusive-or and union between polygons. It’s called Clipper, and has been ported to AS3 by Chris Denham, and it’s really what I need.

With this simple script:

package {
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.geom.Point;
	import com.logicom.geom.Clipper;
	import com.logicom.geom.ClipType;
	public class Main extends Sprite {
		public function Main():void {
			for (var i:int=0; i<4; i++) {
				var dX:Number=(i%2)*320;
				var dY:Number=Math.floor(i/2)*240
				var subjectPolygon:Array=[new Point(0+dX,0+dY),new Point(200+dX,0+dY),new Point(100+dX,200+dY)];
				var clipPolygon:Array=[new Point(0+dX,100+dY),new Point(200+dX,100+dY),new Point(300+dX,200+dY)];
				var resultPolygons:Array=Clipper.clipPolygon(subjectPolygon,clipPolygon,i);
				graphics.lineStyle(2, 0xFF0000, 1.0);
				drawPolygon(subjectPolygon);
				graphics.lineStyle(2, 0x0000FF, 1.0);
				drawPolygon(clipPolygon);
				graphics.lineStyle(3, 0x00FF00, 1.0);
				graphics.beginFill(0xFF0000, 0.5);
				for each (var polygon:Array in resultPolygons) {
					drawPolygon(polygon);
				}
				graphics.endFill();
			}
		}
		private function drawPolygon(polygon:Array):void {
			var n:uint=polygon.length;
			if (n < 3) {
				return;
			}
			var p:Point=polygon[0];
			graphics.moveTo(p.x, p.y);
			for (var i:uint = 1; i <= n; ++i) {
				p=polygon[i%n];
				graphics.lineTo(p.x, p.y);
			}
		}
	}
}

I am able to show you the four ways to perform polygon clipping:

From left to right, top to bottom, respectively intersection, union, difference and xor of two overlapping triangles.

Next step will be managing holes with this class to handle holes and poly2tri to triangulate resulting polygons. And finally we’ll have our Box2D/Nape pure destructible terrain engine.

Game design ideas are welcome, meanwhile download the source code.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers