多角形の内外判定

マウスが画面に描画されている多角形の内側（白い部分）かどうかを判定
します

方針）
　・対象点から任意の方向にレイを発射し、多角形の線分との交差数をカ
　　ウントする。
　・交差数が偶数の場合、外側。奇数の場合は、内側になる。

また、線分の交差判定のアルゴリズムは下記の文献を参考にしています。

参考）
ゲームプログラミングのためのリアルタイム衝突判定(Real-Time Collision Detection)
http://www.amazon.co.jp/dp/493900791X

potix2

forked:0
favorite:13
lines:118
license : MIT License
modified : 2009-11-24 18:46:04

Embed: Tweet

/**
マウスが画面に描画されている多角形の内側（白い部分）かどうかを判定
します

方針）
　・対象点から任意の方向にレイを発射し、多角形の線分との交差数をカ
　　ウントする。
　・交差数が偶数の場合、外側。奇数の場合は、内側になる。

また、線分の交差判定のアルゴリズムは下記の文献を参考にしています。

参考）
ゲームプログラミングのためのリアルタイム衝突判定(Real-Time Collision Detection)
http://www.amazon.co.jp/dp/493900791X
*/
package {
	import flash.display.Graphics;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.events.TimerEvent;
	import flash.geom.Point;
	import flash.text.TextField;
	import flash.utils.Timer;
	
	[SWF(width = 465, height = 465, backgroundColor = 0x0, frameRate = 60)]
	public class IsPointInPolygonTest extends Sprite {
	private static const CANVAS_WIDTH:int = 1000;
	private static const CANVAS_HEIGHT:int = 1000;
	private static const DEFAULT_NUM_OF_VERTICES:int = 3;
	private static const REFRESH_INTERVAL:int = 5000; //5秒ごとに図形を再描画
	private var console:TextField;
	private var canvas:Sprite;
	private var vertices:Array;
	private var refreshTimer:Timer;
	private var numOfVertices:int;
	public function IsPointInPolygonTest()
	{
		numOfVertices = DEFAULT_NUM_OF_VERTICES;
		addEventListener(Event.ADDED_TO_STAGE, initialize);
	}
	
	private function setup():void {
		console = new TextField();
		console.width = stage.stageWidth;
		console.height = stage.stageHeight / 3;
		console.textColor = 0xFFFFFF;
		console.y = stage.stageHeight / 3 * 2;
		addChild(console);
	}
	
	private function initialize(event:Event):void {
		removeEventListener(Event.ADDED_TO_STAGE, initialize);
		setup();
		
		//多角形の頂点を生成
		initCanvas();
		initVertices();
		initListeners();
		initTimer();
		draw();
	}

private function initCanvas():void {
		canvas = addChild(new Sprite()) as Sprite;
		canvas.width = stage.stageWidth;
		canvas.height = stage.stageHeight * 2 / 3;
	}
	
	private function initVertices():void {
		vertices = new Array();
		for (var i:int = 0; i < numOfVertices; i++)
		{
			vertices.push(new Point(Math.random() * 465, Math.random() * 310));
		}
	}
	
	private function initListeners():void {
		stage.addEventListener(MouseEvent.MOUSE_MOVE, check);
	}

private function initTimer():void {
	    refreshTimer = new Timer(REFRESH_INTERVAL, 0);
	    refreshTimer.addEventListener(TimerEvent.TIMER, refresh);
	    refreshTimer.start();
    }

private function draw():void {
		var g:Graphics = this.graphics;
		g.clear();
		g.beginFill(0xFFFFFF);
		g.moveTo(vertices[0].x, vertices[0].y);
		for (var i:int = 1; i < vertices.length; i++)
		{
			g.lineTo(vertices[i].x, vertices[i].y);
		}
		g.lineTo(vertices[0].x, vertices[0].y);
		g.endFill();
	}

private function check(event:MouseEvent):void {
		var clickPoint:Point = new Point(event.stageX, event.stageY);
		_debug((isPointInPolygon(this.vertices, clickPoint) ? 'in' : 'out') + ':' +clickPoint.toString());
	}
	
	private function refresh(event:TimerEvent):void {
		numOfVertices++;
		initVertices();
		draw();
	}
	
	//geometry functions
	public static function signed2DTriArea(a:Point, b:Point, c:Point):Number {
		return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
	}
	
	public static function test2DSegmentSegment(a:Point, b:Point, c:Point, d:Point):Point {
		var a1:Number = signed2DTriArea(a, b, d);
		var a2:Number = signed2DTriArea(a, b, c);
		if ( a1 * a2 < 0.0 ) {
			var a3:Number = signed2DTriArea(c, d, a);
			var a4:Number = a3 + a2 - a1;
			if  ( a3 * a4 < 0.0 ) {
				var t:Number = a3  / (a3 - a4);
				var p:Point = new Point(a.x + t * (b.x - a.x), a.y + t * (b.y - a.y));
				return p;
			}
		}
		
		return null;
	}
	
	public static function isPointInPolygon(polygonVertices:Array, target:Point):Boolean {
		//レイを発射する方向
		var destPoint:Point = new Point(CANVAS_WIDTH, CANVAS_HEIGHT);
		var crossCount:uint = 0;
		for ( var i:int = 0; i < polygonVertices.length; i++ ) {
			var a:Point = polygonVertices[i] as Point;
			var b:Point = polygonVertices[(i + 1) % polygonVertices.length] as Point;
			var crossPoint:Point = test2DSegmentSegment(a, b, target, destPoint);
			if ( crossPoint != null ) {
				crossCount++;
			}
		}
		return (crossCount % 2) == 1;
	}
	
	//helpers
	private function _debug(message:String):void {
		console.text = message + "\n" + console.text;
	}
}

}

Code Fullscreen

Preview Fullscreen