Bubble Tree Drawing
http://tulip.labri.fr/publi_tulip/grivetICCVG2004.pdf
not so perfect
/**
* Copyright wrotenodoc ( http://wonderfl.net/user/wrotenodoc )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/5aYu
*/
// forked from wrotenodoc's binary tree HV-Drawing
// forked from wrotenodoc's binary tree drawing
package {
import flash.display.Sprite;
import flash.display.Graphics
import flash.text.TextField
public class EnclosingCircle extends Sprite {
private var canv:Sprite
private var tree:Tree
private const size:Number = 8
private const spaceX:Number = 30
private const spaceY:Number = 20
private var _tf:TextField = new TextField // for debug
public function EnclosingCircle() {
// write as3 code here..
canv = new Sprite
tree = new Tree(20)
addChild(canv)
canv.x = stage.stageWidth * 0.5
canv.y = stage.stageHeight * 0.5
addChild(_tf)
_tf.autoSize = "left"
build(tree, 0)
calcEC(tree)
//adjustRoot(tree)
render(canv.graphics, tree)
stage.addEventListener("mouseMove", function(e:Object):void {
canv.scaleX = canv.scaleY = 0.1 + 0.9 * (mouseX / stage.stageWidth)
var dx:Number = mouseX - stage.stageWidth/2
var dy:Number = mouseY - stage.stageHeight/2
canv.rotation = 180/Math.PI * Math.atan2(dy, dx)
})
}
private function build(T:Tree, level:int):void {
var N:int = 5
var child:Tree
for(var i:int=0; i<N; i++){
child = new Tree(5 + Math.random()*5)
T.children.push(child)
if(level < 3 && Math.random() < 0.8) build(child, level+1)
}
}
public function render(g:Graphics, T:Tree):void {
var level:int = 0
var queue:Array = [T]
var num:int
while(queue.length){
num = queue.length
while(num--){
T = queue.shift()
g.lineStyle(1, 0xff0000)
g.drawCircle(T.x, T.y, T.radius)
g.lineStyle(1, 0xff)
//g.drawCircle(T.ecX, T.ecY, T.ecRadius)
for(var i:int=0; i<T.children.length; i++){
queue.push(T.children[i])
g.lineStyle(1, 0x0, 0.25)
g.moveTo(T.children[i].x, T.children[i].y)
g.lineTo(T.x, T.y)
}
}
level++
}
}
// calculate recursively the enclosing circle of T
// (assume ECs of T's children are already calculated)
public function calcEC(T:Tree):void {
if(T.children.length == 0){
T.ecX = T.x ; T.ecY = T.y ; T.ecRadius = T.radius
}else{
var remains:Vector.<Tree> = T.children.concat()
for(var i:int=0; i<remains.length; i++) calcEC(remains[i])
var totalR:Number = 0
var ang:Number=0, angi:Number, dx:Number, dy:Number
var dist:Number
for(i=0; i<remains.length; i++) totalR += remains[i].ecRadius
for(i=0; i<remains.length; i++){
angi = Math.PI*2 * remains[i].ecRadius / totalR
ang += angi
dist = Math.max(T.radius + remains[i].ecRadius, remains[i].ecRadius / Math.sin(angi/2))
dx = T.x + dist * Math.cos(ang - angi/2) - remains[i].ecX
dy = T.y + dist * Math.sin(ang - angi/2) - remains[i].ecY
fmap(function(t:Tree):void { t.ecX += dx ; t.ecY += dy ; t.x += dx ; t.y += dy }, remains[i])
}
T.ecX = T.x ; T.ecY = T.y ; T.ecRadius = T.radius
var ec:Tree = ec2(T, remains.shift())
while(remains.length){
ec = ec2(ec, remains.shift())
}
T.ecX = ec.x ; T.ecY = ec.y ; T.ecRadius = ec.radius
}
}
// enclosing circle of two nodes
public function ec2(a:Tree, b:Tree):Tree {
/*
var dx:Number = b.x - a.x
var dy:Number = b.y - a.y
var D:Number = Math.sqrt(dx*dx + dy*dy)
var R:Number = (a.radius + b.radius + D)/2
dx /= D ; dy /= D
var Cx:Number = a.x + dx * (R - a.radius)
var Cy:Number = a.y + dy * (R - a.radius)
var t:Tree = new Tree(R)
t.x = Cx ; t.y = Cy
*/
var dx:Number = b.ecX - a.ecX
var dy:Number = b.ecY - a.ecY
var D:Number = Math.sqrt(dx*dx + dy*dy)
var R:Number = (a.ecRadius + b.ecRadius + D)/2
dx /= D ; dy /= D
var Cx:Number = a.ecX + dx * (R - a.ecRadius)
var Cy:Number = a.ecY + dy * (R - a.ecRadius)
var t:Tree = new Tree(R)
t.ecX = Cx ; t.ecY = Cy ; t.ecRadius = R
return t
}
public function adjustRoot(T:Tree):void {
//
}
public function fmap(f:Function, t:Tree):void {
if(t){
f(t)
for(var i:int=0; i<t.children.length; i++){
fmap(f, t.children[i]);
}
}
}
}
}
class Tree {
public var children:Vector.<Tree>
public var parent:Tree
public var angle:Number = 0
public var radius:Number = 0
public var x:Number = 0, y:Number = 0
// (x, y, r) of enclosing circle
public var ecRadius:Number = 0
public var ecX:Number = 0, ecY:Number = 0
public function Tree(rad:Number) {
children = new Vector.<Tree>
radius = rad
}
}