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;
}
|
