Commits

Alexandru Moșoi committed 658e046

Simple fractals implementation.

Comments (0)

Files changed (3)

+application: simplefractal
+version: 1
+runtime: go
+api_version: 3
+
+handlers:
+- url: /.*
+  script: _go_app

fractal/fractal.go

+package fractal
+
+import (
+	"http"
+	"time"
+	"log"
+	"fmt"
+)
+
+func drawSVG(w http.ResponseWriter, req *http.Request) {
+	tree, err := ParseTree(req.URL.Query())
+	if err != nil {
+		http.Error(w, err.String(), http.StatusBadRequest)
+	}
+
+	start := time.Nanoseconds()
+	w.Header().Add("Content-Type", "image/svg+xml")
+	tree.WriteSVG(w)
+	end := time.Nanoseconds()
+
+	log.Printf("%v in %fs", req.URL, float64(end-start)*1e-9)
+}
+
+func indexHTML(w http.ResponseWriter, req *http.Request) {
+	fmt.Fprintln(w, "<html>")
+	fmt.Fprintln(w, "<head>")
+	fmt.Fprintln(w, "<title>Fractal</title>")
+	fmt.Fprintln(w, "</head>")
+	fmt.Fprintln(w, "<body>")
+	fmt.Fprintln(w, "<img src=\"/draw.svg?r=0,0,0,128&e=0,0,0,128&s=-48,128,48,128&s=-32,0,32,0&s=-40,64,40,64\"/>")
+	fmt.Fprintln(w, "<img src=\"/draw.svg?r=0,0,128,128&e=0,0,128,128&s=0,0,128,0&s=128,0,128,128&s=64,64,128,0&se=128,0,64,64\"/>")
+	fmt.Fprintln(w, "<img src=\"/draw.svg?r=0,0,128,128&e=0,0,128,128&s=0,0,128,0&s=0,128,128,128\"/>")
+	fmt.Fprintln(w, "<img src=\"/draw.svg?r=0,0,0,128&e=0,0,0,128&s=-48,128,48,128&s=-48,0,48,0\"/>")
+	fmt.Fprintln(w, "<img src=\"/draw.svg?r=0,0,0,128&e=0,0,0,128&s=-16,48,64,0&s=32,128,-64,128\"/>")
+	fmt.Fprintln(w, "<img src=\"/draw.svg?r=0,0,0,128&e=0,0,0,128&s=-48,176,+48,160&s=-48,-48,+48,-32\"/>")
+	fmt.Fprintln(w, "<img src=\"/draw.svg?r=0,0,0,128&e=0,0,0,128&s=-48,160,+48,160&s=-48,-32,+48,-32\"/>")
+
+	fmt.Fprintln(w, "</body>")
+	fmt.Fprintln(w, "</html>")
+}
+
+func init() {
+	http.HandleFunc("/draw.svg", drawSVG)
+	http.HandleFunc("/index.html", indexHTML)
+}
+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
+}