hanyeah

网友发的一个题“之前遇到一个问题，就是canvas中任意四个点，如何让四个点自动串联成一个封闭图形，并计算其面积”。据说是18k的面试题。

讨论半天，都不如实际做一下。

问题分成两步：

第一步、4个点组成多边形；

第二步、求多边形面积；

其实第二步比较简单，因为求多边形面积算法很成熟，网上一搜就有，照着抄就行了。

第一步比较难。应该是要求组成的多边形是简单多边形，即可以是凸多边形，可以是凹多边形，但是边与边之间不能有交叉。我们需要对4个点进行排序来满足要求。

这个问题可能要用到图论的知识，只是我没系统的学过。

自己想到两种方式：

1、随意找3个点，组成一个三角形[p1,p2,p3]，然后根据第四个点p4与三角形的关系，把第四个点插入到三角形中。

2、4个点，总共有6条线，可以分为3组互不相邻的线段，判断一组线段是否相交，如果相交，去掉，刚好剩余4条线，即为4变形的4条边。如果3组都不想交，去掉任意一组都可以（刚好对应方法1中第4个点在三角形内的情况）。

用第二种方式做了个demo，效果如下：

参考：http://blog.csdn.net/rickliuxiao/article/details/6259322

http://www.cnblogs.com/void/archive/2011/04/17/2018729.html

代码：

package  {
	
	import flash.display.MovieClip;
	import flash.display.Shape;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.geom.Point;
	import flash.text.TextField;
	
	
	public class Main extends MovieClip {
		
		public var p1:MovieClip;
		public var p2:MovieClip;
		public var p3:MovieClip;
		public var p4:MovieClip;
		public var tf:TextField;
		private var curSp:Sprite;
		
		public function Main() {
			// constructor code
			stage?initStage(null):addEventListener(Event.ADDED_TO_STAGE, initStage);
		}
		
		private function initStage(e:Event):void 
		{
			removeEventListener(Event.ADDED_TO_STAGE, initStage);
			drag(p1);
			drag(p2);
			drag(p3);
			drag(p4);
			tf.mouseEnabled = false;
			mouseMoveHandler(null);
			//画个网格
			drawGrid();
		}
		
		private function drawGrid():void {
			var shape:Shape = new Shape();
			this.addChildAt(shape,0);
			shape.graphics.lineStyle(0, 0x000000, 0.6);
			var i:int = 0;
			for (i = 0; i < stage.stageWidth+10;i+=10 ) {
				shape.graphics.moveTo(i, 0);
				shape.graphics.lineTo(i, stage.stageHeight);
			}
			for (i = 0; i < stage.stageHeight+10;i+=10 ) {
				shape.graphics.moveTo(0,i);
				shape.graphics.lineTo(stage.stageWidth,i);
			}
		}
		
		private function drag(sp:Sprite):void {
			sp.buttonMode = true;
			sp.addEventListener(MouseEvent.MOUSE_DOWN, mouseDownHandler);
		}
		
		private function mouseDownHandler(e:MouseEvent):void 
		{
			if (curSp) curSp.stopDrag();
			curSp = e.currentTarget as Sprite;
			curSp.startDrag();
			addEventListener(MouseEvent.MOUSE_MOVE, mouseMoveHandler);
			addEventListener(MouseEvent.MOUSE_UP, mouseUpHandler);
		}
		
		private function mouseUpHandler(e:MouseEvent):void 
		{
			curSp.stopDrag();
			curSp = null;
			removeEventListener(MouseEvent.MOUSE_MOVE, mouseMoveHandler);
			removeEventListener(MouseEvent.MOUSE_UP, mouseUpHandler);
		}
		
		private function mouseMoveHandler(e:MouseEvent):void 
		{
			var result:Array = []; 
			
			if (detectIntersect(p1,p2,p3,p4)) {
				result = [p1, p3, p2, p4];
			}
			else if (detectIntersect(p1,p3,p2,p4)) {
				result = [p1, p2, p3, p4];
			}
			else if (detectIntersect(p1,p4,p2,p3)) {
				result = [p1, p2, p4, p3];
			}
			else {
				result = [p1, p2, p3, p4];
			}
			
			graphics.clear();
			var colors:Array = [0xff0000,0x00ff00,0x0000ff,0xffff00];
			graphics.lineStyle(1, 0xff0000, 1.0);
			var i:int = 0;
			for (i = 0; i <= 4;i++ ) {
				var p:Object = result[i%4];
				if (i==0) {
					graphics.moveTo(p.x, p.y);
				}
				else {
					graphics.lineStyle(1, colors[i-1], 1.0);
					graphics.lineTo(p.x, p.y);
				}
			}
			
			//
			var area:Number = 0;
			area = mult(result[0], result[1], result[2]) + mult(result[0], result[2], result[3]);
			area = area / 2;
			if (area<0) {
				area = -area;
			}
			tf.text = "面积：" + area;
		}
		
		
		
		private function detectIntersect(aa:Object,bb:Object,cc:Object,dd:Object):Boolean {
			if (Math.max(aa.x,bb.x)<Math.min(cc.x,dd.x)) {
				return false;
			}
			if (Math.max(aa.y,bb.y)<Math.min(cc.y,dd.y)) {
				return false;
			}
			if (Math.max(cc.x,dd.x)<Math.min(aa.x,bb.x)) {
				return false;
			}
			if (Math.max(cc.y,dd.y)<Math.min(aa.y,bb.y)) {
				return false;
			}
			if (mult(cc,bb,aa)*mult(bb,dd,aa)<0) {
				return false;
			}
			if (mult(aa,dd,cc)*mult(dd,bb,cc)<0) {
				return false;
			}
			return true;
		}
		/**
		 * 叉积。
		 * @param	a
		 * @param	b
		 * @param	c
		 * @return
		 */
		private function mult(a:Object,b:Object,c:Object):Number {
			return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
		}
		
	}
	
}

源码打包下载