点が多角形の内部にあるか判定

by genms 21 Jun 2009

Tags

graphics math
Embed

/**
 * Copyright genms ( http://wonderfl.net/user/genms )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/p4k4
 */

package {
	import flash.display.Sprite;
	public class Main extends Sprite {
		public function Main() {
			var commands:Vector.<int> = new Vector.<int>(6, true);
			commands[0] = 1;
			commands[1] = 2;
			commands[2] = 2;
			commands[3] = 2;
			commands[4] = 2;
			commands[5] = 2;
			
			var polygonData:Vector.<Number> = new Vector.<Number>(12, true);
			polygonData[0] = 50;
			polygonData[1] = 250;
			
			polygonData[2] = 100;
			polygonData[3] = 50;
			
			polygonData[4] = 150;
			polygonData[5] = 150;
			
			polygonData[6] = 200;
			polygonData[7] = 30;
			
			polygonData[8] = 250;
			polygonData[9] = 200;
			
			polygonData[10] = 150;
			polygonData[11] = 250;
			
			graphics.beginFill(0x00ff00);
			graphics.drawPath(commands, polygonData);
			graphics.endFill();
			
			var i:int;
			for (i = 0; i < 2000; i++) {
				var dotX:int = int(Math.random() * 300);
				var dotY:int = int(Math.random() * 300);
				if (checkDotAndPolygonHit(dotX, dotY, polygonData)) {
					graphics.beginFill(0xff0000);
				}
				else {
					graphics.beginFill(0xff);
				}
				
				graphics.drawCircle(dotX, dotY, 1);
				graphics.endFill();
			}
		}
		
		public static function checkDotAndPolygonHit(dotX:Number, dotY:Number,
				polygonData:Vector.<Number>):Boolean {
			var cnt:int = 0;
			for (var i:int = 0; i < (polygonData.length / 2); i++) {
				var i2:int;
				if (i == (polygonData.length / 2) - 1) {
					i2 = 0;
				}
				else {
					i2 = i + 1;
				}
				
				// レイの線上にある点はレイより上にあることとする
				var px1:Number = polygonData[i * 2];
				var py1:Number = polygonData[i * 2 + 1];
				if (py1 == dotY) {
					py1--;
				}
				var px2:Number = polygonData[i2 * 2];
				var py2:Number = polygonData[i2 * 2 + 1];
				if (py2 == dotY) {
					py2--;
				}
				
				var dx1:Number = dotX;
				var dy1:Number = dotY;
				var dx2:Number = dotX + 1000;
				var dy2:Number = dotY;
				
				// 2線分が交差している = 点A,Bを通る直線が線分CDと交差し、かつ点C,Dを通る直線が線分ABと交差している
				var cp11:Number = crossProduct(
						(dx2 - dx1), (dy2 - dy1), 
						(px1 - dx1), (py1 - dy1));
				var cp12:Number = crossProduct(
						(dx2 - dx1), (dy2 - dy1), 
						(px2 - dx1), (py2 - dy1));

				var cp21:Number = crossProduct(
						(px2 - px1), (py2 - py1), 
						(dx1 - px1), (dy1 - py1));
				var cp22:Number = crossProduct(
						(px2 - px1), (py2 - py1), 
						(dx2 - px1), (dy2 - py1));
				
				// 上から下に横切るときには横切り回数を１引き、下から上に横切るときには横切り回数を１足すこととする
				if (cp11 * cp12 <= 0 && cp21 * cp22 <= 0) {
					if (dy1 - py1 < 0) {
						cnt++;
					}
					else {
						cnt--;
					}
				}
			}

			/*
			var ret:DotAndPolygonHitResult = new DotAndPolygonHitResult();
			ret.hit = (cnt != 0);
			return ret;
			*/
			return (cnt != 0);
		}	
		
		public static function crossProduct(x1:Number, y1:Number, x2:Number, y2:Number):Number {
			return x1 * y2 - x2 * y1;
		}
	}
	
}