标签归档:

自然连通图

引言

接上一文章,当每个随机区块完成后,需要对每个区块进行连接,如果更好的进行连接,随机乱连肯定是不行的,会出现如下情况

图片1

直觉上告诉我们,我们希望得到的是类似下面的图

QQ截图20140122111343

这种连接方式看上去很“自然”,那如何得到这种比较自然的连线方式呢?我们从结果出发可以得到几点规则:

  1. 连线不能交叉
  2. 连线不要经过其他点
  3. 最好不好一个点有多条连线

通过上面的约束,我们可以得到一个算法

  1. 初始时所有点都处在自己的独立集合中
  2. 从第一个集合出发,找到一个离开最近的集合
  3. 与最近的集合做连线,并将那个集合取消,将连线后的点增加到当前集合
  4. 重复第2步,直到所有点都在一个集合

代码

package
{
	import flash.display.Sprite;
	import flash.events.MouseEvent;
	import flash.geom.Point;

	[SWF(frameRate="60", width="800", height="600")]
	public class LineMap extends Sprite
	{
		private var points:Array;
		private var lines:Vector.;
		private var units:Vector.;
		private var step:int = 0;
		private var currentPoint:Point;

		public function LineMap()
		{
			stage.addEventListener(MouseEvent.CLICK, onClick);
		}

		public function initUnit():void {
			units = new Vector.();
			// 初始时每个球一个单元
			for each (var p:Point in points) {
				var u:Unit = new Unit();
				u.points.push(p);
				units.push(u);
			}
		}

		protected function onClick(event:MouseEvent):void
		{
			init();
			initUnit();
			line();
			draw();
		}

		private function line():void
		{
			lines = new Vector.();
			// 遍历所有单元,选择出最近连线,且不相交
			while (units.length > 1) {
				var u:Unit = units[0];

				// 遍历其余单元,找出距离最短的那个单元
				var minDist:Number = Number.MAX_VALUE;
				var minIndex:int = -1, minP1:Point, minP2:Point;
				for (var j:int = 1; j < units.length; ++j) {
					var o:Unit = units[j];
					assert(o.points.length <= 1);
					var dist:Array = u.dist(o);
					if (dist[0] < minDist) {
						minDist = dist[0];
						minIndex = j;
						minP1 = dist[1];
						minP2 = dist[2];
					}
				}

				var l:Line = new Line();
				l.p1 = minP1;
				l.p2 = minP2;
				lines.push(l);

				// 将最短距离的那个单元加入当前单元
				u.points.push(units[minIndex].points[0]);
				units.splice(minIndex, 1);

//				currentPoint = minP1;

//				step++;
//				break;
			}
		}

		public function init():void {
			var count:int = 30;
			var padding:int = 10;
			points = [];
			for (var i:int = 0; i < count; ++i) {
				var p:Point = new Point(rand(padding, stage.stageWidth - padding), rand(padding, stage.stageHeight - padding));
				points.push(p);
			}
		}

		public function rand(x:Number, y:Number):Number {
			return x + Math.random() * (y - x);
		}

		public function draw():void {
			graphics.clear()
			for each (var p:Point in points) {
				graphics.beginFill(0x0);
				if (currentPoint == p) {
					graphics.beginFill(0xFF0000);
				}
				graphics.drawCircle(p.x, p.y, 10);
				graphics.endFill();
			}
			for each (var l:Line in lines) {
				graphics.lineStyle(1, 0x0);
				graphics.moveTo(l.p1.x, l.p1.y);
				graphics.lineTo(l.p2.x, l.p2.y);
			}
		}

		public function assert(b:Boolean):void {
			if (! b) {
				throw new Error("断言错误");
			}
		}
	}
}
import flash.geom.Point;

class Unit {
	public var points:Array = [];

	public function dist(u:Unit):Array {
		var minDist:Number = Number.MAX_VALUE;
		var minP1:Point, minP2:Point;
		for each (var p1:Point in points) {
			for each (var p2:Point in u.points) {
				var dist:Number = p1.subtract(p2).length;
				if (dist < minDist) {
					minDist = dist;
					minP1 = p1;
					minP2 = p2;
				}
			}
		}
		return [minDist, minP1, minP2];
	}
}

class Line {
	public var p1:Point;
	public var p2:Point;
}

效果

Get Adobe Flash player