Source

simplefractal / fractal / tree.go

Full commit
package fractal

import (
	"url"
	"io"
	"fmt"
	"math"
	"os"
)

type Vector struct {
	x1, y1, x2, y2 float64
}

type Tree struct {
	width float64

	root  *Vector
	edges []*Vector
	seeds []*Vector
}

type Line struct {
	v *Vector
	w float64
}

type ParseError struct {
	ErrorString string
}

func (e *ParseError) String() string {
	return e.ErrorString
}

func ParseVector(str string) (*Vector, os.Error) {
	var x1, y1, x2, y2 float64
	_, err := fmt.Sscanf(str, "%f,%f,%f,%f", &x1, &y1, &x2, &y2)
	if err != nil {
		return nil, &ParseError{fmt.Sprintf("cannot parse %s: %v", str, err)}
	}
	return &Vector{x1, y1, x2, y2}, nil
}

func (v *Vector) Abs() float64 {
	dx := v.x2 - v.x1
	dy := v.y2 - v.y1
	return math.Sqrt(dx*dx + dy*dy)
}

func (v *Vector) Normalize(u *Vector) *Vector {
	var x, y float64
	var r Vector
	dx := u.x2 - u.x1
	dy := u.y2 - u.y1
	delta := dx*dx + dy*dy

	x = v.x1 - u.x1
	y = v.y1 - u.y1
	r.x1 = (dx*x + dy*y) / delta
	r.y1 = (dy*x - dx*y) / delta

	x = v.x2 - u.x1
	y = v.y2 - u.y1
	r.x2 = (dx*x + dy*y) / delta
	r.y2 = (dy*x - dx*y) / delta

	return &r
}

func (v *Vector) Denormalize(u *Vector) *Vector {
	var r Vector
	dx := u.x2 - u.x1
	dy := u.y2 - u.y1

	r.x1 = (dx*v.x1 + dy*v.y1) + u.x1
	r.y1 = (dy*v.x1 - dx*v.y1) + u.y1

	r.x2 = (dx*v.x2 + dy*v.y2) + u.x1
	r.y2 = (dy*v.x2 - dx*v.y2) + u.y1

	return &r
}

func ParseTree(query url.Values) (*Tree, os.Error) {
	var err os.Error
	var tree Tree

	if len(query["r"]) != 1 {
		return nil, &ParseError{"missing unique root (e.g. r=0,0,0,1)"}
	}

	tree.root, err = ParseVector(query["r"][0])
	if err != nil {
		return nil, err
	}

	for _, str := range query["e"] {
		v, err := ParseVector(str)
		if err != nil {
			return nil, err
		}
		tree.edges = append(tree.edges, v.Normalize(tree.root))
	}

	for _, str := range query["s"] {
		v, err := ParseVector(str)
		if err != nil {
			return nil, err
		}
		tree.seeds = append(tree.seeds, v.Normalize(tree.root))
	}

	return &tree, nil
}

func (tree *Tree) WriteSVG(w io.Writer) {
	lines := tree.flatten(nil, tree.root, 4)

	minx, maxx := math.MaxFloat64, -math.MaxFloat64
	miny, maxy := math.MaxFloat64, -math.MaxFloat64
	for _, l := range lines {
		minx = math.Fmin(minx, math.Fmin(l.v.x1, l.v.x2))
		maxx = math.Fmax(maxx, math.Fmax(l.v.x1, l.v.x2))

		miny = math.Fmin(miny, math.Fmin(l.v.y1, l.v.y2))
		maxy = math.Fmax(maxy, math.Fmax(l.v.y1, l.v.y2))
	}

	fmt.Fprintf(w, `<svg width="%f" height="%f" xmlns="http://www.w3.org/2000/svg" version="1.1">`,
		maxx-minx, maxy-miny)
	for _, l := range lines {
		fmt.Fprintf(w, `<line x1="%f" y1="%f" x2="%f" y2="%f" style="stroke:rgb(255,0,0);stroke-width:%f"/>`,
			l.v.x1-minx, l.v.y1-miny, l.v.x2-minx, l.v.y2-miny, l.w)
	}
	fmt.Fprintf(w, `</svg>`)
}

func (tree *Tree) flatten(lines []Line, root *Vector, width float64) []Line {
	if width < 0.1 || len(lines) > 100000 {
		return lines
	}

	for _, edge := range tree.edges {
		slap := edge.Denormalize(root)
		lines = append(lines, Line{slap, width})
	}

	for _, seed := range tree.seeds {
		slap := seed.Denormalize(root)
		lines = tree.flatten(lines, slap, width*slap.Abs()/root.Abs())
	}

	return lines
}