chongkong/animation.html

## animation.html
<!doctype html>
<head>
    <script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/snap.svg/0.4.1/snap.svg-min.js"></script>
</head>
<body>
    <script>
        const GREEN = "#77cc22";
        const BLUE = "#2277ee";
        const LIGHTGRAY = "#dddddd";
        const DARKGRAY = "#cccccc";
        const PINK = "#ffaaaa";
        const LIGHTPINK = "#ffcccc";
        const FRAMERATE = 16.67;

        /**
         * Normalize floating points into integer grids,
         * keeping all directions between points (direction refers to UE / UW / NW / NE)
         */
        function normalizePoints(points) {
            let xs = points.map(p => p.x).sort((a, b) => a - b);
            let ys = points.map(p => p.y).sort((a, b) => a - b);
            return points.map(point => ({
                x: xs.indexOf(point.x),
                y: ys.indexOf(point.y)
            }));
        }

        class MyCanvas {
            constructor(points) {
                this.rawPoints = points;
                this.points = normalizePoints(points);
                this.tasks = [];
                this.snap = Snap(1020, 1020);
            }

            drawGrids() {
                for (let i = 0; i <= 100; i++) {
                    if (i % 5 !== 0) {
                        this.drawLine({x: i, y: 0}, {x: i, y: 100}, LIGHTGRAY);
                        this.drawLine({x: 0, y: i}, {x: 100, y: i}, LIGHTGRAY);
                    }
                }
                for (let i = 0; i <= 100; i += 5) {
                    this.drawLine({x: i, y: 0}, {x: i, y: 100}, DARKGRAY);
                    this.drawLine({x: 0, y: i}, {x: 100, y: i}, DARKGRAY);
                }
            }

            t(point) {
                // Maps the point to svg plane
                // (from [0, 100] x [0, 100] to [10, 1010] x [10, 1010] (Scales x10)
                return {x: point.x * 10 + 10, y: point.y * 10 + 10};
            }

            drawLine(from, to, color) {
                let t_From = this.t(from);
                let t_To = this.t(to);
                let line = this.snap.line(t_From.x, t_From.y, t_To.x, t_To.y);
                line.attr({
                    stroke: color,
                    strokeWidth: 2
                });
            }

            commitTask(f, millis) {
                this.tasks.push({f, millis});
            }

            handleTasks() {
                if (this.tasks.length === 0)
                    return;
                let {f, millis} = this.tasks[0];
                this.tasks = this.tasks.splice(1);
                f();
                setTimeout(this.handleTasks.bind(this), millis);
            }

            show() {
                /* 1. Show initial points */

                for (let point of this.rawPoints) {
                    this.drawPoint(point, PINK);
                }

                /* 2. Show points normalization step */

                for (let i = 0; i < this.points.length; i++) {
                    this.commitTask(() => {
                        this.drawLine(this.rawPoints[i], this.points[i], LIGHTPINK);
                        this.drawPoint(this.points[i], GREEN);
                    }, 1 / FRAMERATE);
                }

                /* 3. Show how the tree is structured */

                // Point whose p.x + p.y is bigger comes earlier
                let sortedPoints = this.points.slice().sort((a, b) => b.x + b.y - a.x - a.y);
                let roots = [];
                for (let point of sortedPoints) {
                    let isChild = false;
                    for (let root of roots) {
                        // if any root point is placed upperwest to the point, let the point belongs to the root
                        // (== draw line from root to point)
                        if (root.x < point.x && root.y < point.y) {
                            this.commitTask(() => this.drawLine(root, point, BLUE), 1 / FRAMERATE);
                            isChild = true;
                            break;
                        }
                    }
                    if (!isChild) {
                        // If there's no root that is placed upperwest to the point,
                        // make the point as a new root, and check if there is any previous root point
                        // that can be a child of the new root point.
                        this.commitTask(() => this.drawPoint(point, BLUE, 0));
                        roots = roots.filter(root => {
                            if (point.x < root.x && point.y < root.y) {
                                this.commitTask(() => this.drawPoint(root, GREEN), 1 / FRAMERATE);
                                this.commitTask(() => this.drawLine(point, root, BLUE), 0);
                                return false;
                            } else {
                                return true;
                            }
                        });
                        roots.push(point);
                    }
                }

                // Play animations!
                this.handleTasks();
            }

            drawPoint(point, color) {
                let t_Point = this.t(point);
                let circle = this.snap.circle(t_Point.x, t_Point.y, 5);
                circle.attr({
                    fill: color,
                    strokeWidth: 0
                });
            }
        }

        points = [];
        for (let i = 0; i < 100; i++) {
            points.push({x: Math.random() * 100, y: Math.random() * 100});
        }
        let cnv = new MyCanvas(points);
        cnv.drawGrids();
        cnv.show();

    </script>
    <style>
        svg {
            background-color: #eee;
        }
    </style>
</body>
	<!doctype html>
	<head>
	<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/snap.svg/0.4.1/snap.svg-min.js"></script>
	</head>
	<body>
	<script>
	const GREEN = "#77cc22";
	const BLUE = "#2277ee";
	const LIGHTGRAY = "#dddddd";
	const DARKGRAY = "#cccccc";
	const PINK = "#ffaaaa";
	const LIGHTPINK = "#ffcccc";
	const FRAMERATE = 16.67;

	/**
	* Normalize floating points into integer grids,
	* keeping all directions between points (direction refers to UE / UW / NW / NE)
	*/
	function normalizePoints(points) {
	let xs = points.map(p => p.x).sort((a, b) => a - b);
	let ys = points.map(p => p.y).sort((a, b) => a - b);
	return points.map(point => ({
	x: xs.indexOf(point.x),
	y: ys.indexOf(point.y)
	}));
	}

	class MyCanvas {
	constructor(points) {
	this.rawPoints = points;
	this.points = normalizePoints(points);
	this.tasks = [];
	this.snap = Snap(1020, 1020);
	}

	drawGrids() {
	for (let i = 0; i <= 100; i++) {
	if (i % 5 !== 0) {
	this.drawLine({x: i, y: 0}, {x: i, y: 100}, LIGHTGRAY);
	this.drawLine({x: 0, y: i}, {x: 100, y: i}, LIGHTGRAY);
	}
	}
	for (let i = 0; i <= 100; i += 5) {
	this.drawLine({x: i, y: 0}, {x: i, y: 100}, DARKGRAY);
	this.drawLine({x: 0, y: i}, {x: 100, y: i}, DARKGRAY);
	}
	}

	t(point) {
	// Maps the point to svg plane
	// (from [0, 100] x [0, 100] to [10, 1010] x [10, 1010] (Scales x10)
	return {x: point.x * 10 + 10, y: point.y * 10 + 10};
	}

	drawLine(from, to, color) {
	let t_From = this.t(from);
	let t_To = this.t(to);
	let line = this.snap.line(t_From.x, t_From.y, t_To.x, t_To.y);
	line.attr({
	stroke: color,
	strokeWidth: 2
	});
	}

	commitTask(f, millis) {
	this.tasks.push({f, millis});
	}

	handleTasks() {
	if (this.tasks.length === 0)
	return;
	let {f, millis} = this.tasks[0];
	this.tasks = this.tasks.splice(1);
	f();
	setTimeout(this.handleTasks.bind(this), millis);
	}

	show() {
	/* 1. Show initial points */

	for (let point of this.rawPoints) {
	this.drawPoint(point, PINK);
	}

	/* 2. Show points normalization step */

	for (let i = 0; i < this.points.length; i++) {
	this.commitTask(() => {
	this.drawLine(this.rawPoints[i], this.points[i], LIGHTPINK);
	this.drawPoint(this.points[i], GREEN);
	}, 1 / FRAMERATE);
	}

	/* 3. Show how the tree is structured */

	// Point whose p.x + p.y is bigger comes earlier
	let sortedPoints = this.points.slice().sort((a, b) => b.x + b.y - a.x - a.y);
	let roots = [];
	for (let point of sortedPoints) {
	let isChild = false;
	for (let root of roots) {
	// if any root point is placed upperwest to the point, let the point belongs to the root
	// (== draw line from root to point)
	if (root.x < point.x && root.y < point.y) {
	this.commitTask(() => this.drawLine(root, point, BLUE), 1 / FRAMERATE);
	isChild = true;
	break;
	}
	}
	if (!isChild) {
	// If there's no root that is placed upperwest to the point,
	// make the point as a new root, and check if there is any previous root point
	// that can be a child of the new root point.
	this.commitTask(() => this.drawPoint(point, BLUE, 0));
	roots = roots.filter(root => {
	if (point.x < root.x && point.y < root.y) {
	this.commitTask(() => this.drawPoint(root, GREEN), 1 / FRAMERATE);
	this.commitTask(() => this.drawLine(point, root, BLUE), 0);
	return false;
	} else {
	return true;
	}
	});
	roots.push(point);
	}
	}

	// Play animations!
	this.handleTasks();
	}

	drawPoint(point, color) {
	let t_Point = this.t(point);
	let circle = this.snap.circle(t_Point.x, t_Point.y, 5);
	circle.attr({
	fill: color,
	strokeWidth: 0
	});
	}
	}

	points = [];
	for (let i = 0; i < 100; i++) {
	points.push({x: Math.random() * 100, y: Math.random() * 100});
	}
	let cnv = new MyCanvas(points);
	cnv.drawGrids();
	cnv.show();

	</script>
	<style>
	svg {
	background-color: #eee;
	}
	</style>
	</body>