自然连通图

引言

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

图片1-300x224

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

【图片丢失】

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

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

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

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

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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;
}

效果

LineMap.swf

updatedupdated2021-01-202021-01-20