<!--

Minimum spanning tree example using the Kruskal algorithm

this standalone version has no dependencies
L 335 to change point count

/-->

html, body {
    width:100%;
    height:100%;
    /*#0e1521*/
    background: #EEEEEE; /* Old browsers */
    background: -moz-radial-gradient(center, ellipse cover,  #EEEEEE 1%, #444444 100%); /* FF3.6+ */
    background: -webkit-gradient(radial, center center, 0px, center center, 100%, color-stop(1%,#EEEEEE), color-stop(100%,#444444)); /* Chrome,Safari4+ */
    background: -webkit-radial-gradient(center, ellipse cover,  #EEEEEE 1%,#444444 100%); /* Chrome10+,Safari5.1+ */
    background: -o-radial-gradient(center, ellipse cover,  #EEEEEE 1%,#444444 100%); /* Opera 12+ */
    background: -ms-radial-gradient(center, ellipse cover,  #EEEEEE 1%,#444444 100%); /* IE10+ */
    background: radial-gradient(ellipse at center,  #EEEEEE 1%,#444444 100%); /* W3C */
    filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#EEEEEE', endColorstr='#444444',GradientType=1 ); /* IE6-9 fallback on horizontal gradient */

    background-color:#444444;
    overflow:hidden;
}

/**
 * computes and returns a Minimum Spanning Tree using the Kruskal Algorithm
 * @param metric a function( edge ) to compute the weight of the edge
 * @param sortMethod a sort function( edge0, edge1 ) to sort edges by increasing weight
 * @constructor
 */
var KruskalMinimumSpanningTree = function( metric, sortMethod )
{

	this.metric = metric || function( edge )
	{
		var dx = edge.p0.x - edge.p1.x;
		var dy = edge.p0.y - edge.p1.y;
		edge.weight = ( dx*dx + dy*dy );
	};

	this.sortMethod = sortMethod || function( edge0, edge1 )
	{
		return edge0.weight - edge1.weight;
	};


	this.PARENT = [];
	this.RANK = [];
	this.tree = [];
	this.sortedEdges = [];

	this.find = function( vertex )
	{
		if( this.PARENT[ vertex.id ] == vertex )
		{
			return this.PARENT[ vertex.id ];
		}
		else
		{
			return this.find( this.PARENT[ vertex.id ] );
		}
	};

	this.union = function( root0, root1 )
	{
		var id0 = root0.id;
		var id1 = root1.id;

		if( this.RANK[ id0 ] > this.RANK[ id1 ] )
		{
			this.PARENT[ id1 ] = root0;
		}
		else if( this.RANK[ id0 ] < this.RANK[ id1 ] )
		{
			this.PARENT[ id0 ] = root1;
		}
		else
		{
			this.PARENT[ id0 ] = root1;
			this.RANK[ id1 ]++;
		}

	};

	this.makeSet = function( vertex )
	{
		this.PARENT[ vertex.id ] = vertex;
		this.RANK[ vertex.id ] = 0;
	};

	this.compute = function( vertices, edges )
	{

		var self = this;
	    this.tree = [];
		this.PARENT = [];
		this.RANK = [];

		vertices.forEach( function( vertex )
		{
			self.makeSet( vertex );
		} );

	    this.sortedEdges = edges.concat();

		this.sortedEdges.forEach( function( e )
		{
			self.metric( e );
		});

		this.sortedEdges.sort( this.sortMethod );

		for ( var i = 0; i < this.sortedEdges.length; i++)
		{

	        var edge = this.sortedEdges[ i ];

			var root1 = this.find( edge.p0 );
			var root2 = this.find( edge.p1 );

			if( root1 != root2 )
			{
				this.tree.push( edge );
				this.union( root1, root2 );
			}

			if( this.tree.length == vertices.length - 1 )
			{
				return this.tree;
			}

		}
	    return this.tree;
	}
};



var Point = function(x,y)
{
	this.x = x || 0;
	this.y = y || 0;

	Point.id = Point.id || 0;//TODO get rid of this
	this.id = Point.id++;

};

var Edge = function( p0, p1 )//TODO store vertices ids instead of vertices refernces
{
	this.p0 = p0;
	this.p1 = p1;
	this.weight = 0;//computed by the Kruskal metric method

	this.render = function( ctx )
	{
		ctx.beginPath();
		ctx.moveTo( this.p0.x, this.p0.y );
		ctx.lineTo( this.p1.x, this.p1.y );
		ctx.stroke();
	};

};

/////////////////////////////////////////////////////////////////

///////////////// TEST

/////////////////////////////////////////////////////////////////

// DELAUNAY TRIANGULATION

var Delaunay = function()
{
    this.EPSILON = 0.00001;
    this.SUPER_TRIANGLE_RADIUS = 1000000;

    this.compute = function( points )
    {
        points.sort( function( a, b ){ return a.x < b.x ? -1 : 1;} );

        this.indices = [];
	    this.circles = [];

        var nv = points.length;
        if (nv < 3) return null;

        var d = this.SUPER_TRIANGLE_RADIUS;
        points.push( 	new Point( 0, -d ) 	);
        points.push( 	new Point( d, d ) 	);
        points.push( 	new Point( -d, d )	);

        this.indices = [];
        this.indices.push( points.length - 3 );
        this.indices.push( points.length - 2 );
        this.indices.push( points.length - 1 );

        this.circles = [];
        this.circles.push( 0 );
        this.circles.push( 0 );
        this.circles.push( d );

        var edgeIds = [];
        var i, j, k, id0, id1, id2;
        for ( i = 0; i < nv; i++ )
        {

            j = 0;
            while( j < this.indices.length )
            {
                if ( 	this.circles[ j + 2 ] > this.EPSILON &&  this.circleContains( j, points[ i ] )	)
                {
                    id0 = this.indices[ j ];
                    id1 = this.indices[ j + 1 ];
                    id2 = this.indices[ j + 2 ];

                    edgeIds.push( id0 );
                    edgeIds.push( id1 );
                    edgeIds.push( id1 );
                    edgeIds.push( id2 );
                    edgeIds.push( id2 );
                    edgeIds.push( id0 );

                    this.indices.splice( j, 3 );
                    this.circles.splice( j, 3 );
                    j -= 3;
                }
                j += 3;
            }

            j = 0;
            while ( j < edgeIds.length )
            {
                k = ( j + 2 );
                while ( k < edgeIds.length )
                {
                    if(	(	edgeIds[ j ] == edgeIds[ k ] && edgeIds[ j + 1 ] == edgeIds[ k + 1 ]	)
                    ||	(	edgeIds[ j + 1 ] == edgeIds[ k ] && edgeIds[ j ] == edgeIds[ k + 1 ]	)	)
                    {
                        edgeIds.splice( k, 2 );
                        edgeIds.splice( j, 2 );
                        j -= 2;
                        k -= 2;
                        if ( j < 0 || j > edgeIds.length - 1 ) break;
                        if ( k < 0 || k > edgeIds.length - 1 ) break;
                    }
                    k += 2;
                }
                j += 2;
            }
            j = 0;
            while( j < edgeIds.length )
            {
                this.indices.push( edgeIds[ j ] );
                this.indices.push( edgeIds[ j + 1 ] );
                this.indices.push( i );
	            this.computeCircle( points, edgeIds[ j ], edgeIds[ j + 1 ], i );
                j += 2;
            }
            edgeIds = [];

        }

        id0 = points.length - 3;
        id1 = points.length - 2;
        id2 = points.length - 1;

        i = 0;
        while( i < this.indices.length )
        {
            if (    this.indices[ i ] == id0     || this.indices[ i ] == id1     || this.indices[ i ] == id2
                ||	this.indices[ i + 1 ] == id0 || this.indices[ i + 1 ] == id1 || this.indices[ i + 1 ] == id2
                ||	this.indices[ i + 2 ] == id0 || this.indices[ i + 2 ] == id1 || this.indices[ i + 2 ] == id2 )
            {
                this.indices.splice( i, 3 );
                this.circles.splice( i, 3 );
                if( i > 0 ) i-=3;
                continue;
            }
            i += 3;
        }
        points.pop();
        points.pop();
        points.pop();

        return this.indices;

    };

    this.circleContains = function( circleId, p )
    {
        var dx = this.circles[ circleId ] - p.x;
        var dy = this.circles[ circleId + 1 ] - p.y;
        return this.circles[ circleId + 2 ] > dx * dx + dy * dy;
    };

    this.computeCircle = function( Points, id0, id1, id2 )
    {
        var p0 = Points[ id0 ];
        var p1 = Points[ id1 ];
        var p2 = Points[ id2 ];
        var A = p1.x - p0.x;
        var B = p1.y - p0.y;
        var C = p2.x - p0.x;
        var D = p2.y - p0.y;
        var E = A * (p0.x + p1.x) + B * (p0.y + p1.y);
        var F = C * (p0.x + p2.x) + D * (p0.y + p2.y);
        var G = 2.0 * (A * (p2.y - p1.y) - B * (p2.x - p1.x));

        var x = (D * E - B * F) / G;
        this.circles.push( x );

        var y = (A * F - C * E) / G;
        this.circles.push( y );

        x -= p0.x;
        y -= p0.y;
        this.circles.push( x * x + y * y );
    };
};

/////////////////////////////////////////////////////////////////


var c = document.createElement( "canvas" ),
	ctx = c.getContext( "2d" ),
	id0 = 0,
	id1 = 0,
	id2 = 0,
	p = null,
	vertices = [],
	indices = [],
	edges = [],
	MST  = [],
  margin = 10,
	width = window.innerWidth,
	height = window.innerHeight,
	size = Math.min( width, height),
	delaunay = new Delaunay(),
	renderInterval = 0,
	time = 0;

//INIT CANVAS

c.width = c.height = size;
c.style.margin = "auto";
c.style.position = "absolute";
c.style.top = c.style.left = c.style.bottom = c.style.right = "0";
document.body.appendChild( c );



function reset( )
{

	//CREATE VERTEICES LIST

	vertices = [];
	for( var i = 0; i < 500; i++ )
	{
		//polar coordinates
//		var angle = Math.random() * Math.PI * 2;
//		var radius = ( 1 - Math.sqrt( Math.random() ) * size / 2 );
		p = new Point(
//						size / 2 + Math.cos( angle ) * radius,
//						size / 2 + Math.sin( angle ) * radius
						margin + ( width - margin * 2 ) * Math.random(),
						margin + ( height - margin * 2 ) * Math.random()
		);
		vertices.push( p );
	}

	//CREATE EDGES' LIST

	indices = delaunay.compute( vertices );

	edges = [];
	for( i = 0; i < indices.length; i+=3 )
	{

		id0 = indices[ i ];
		id1 = indices[ i+1 ];
		id2 = indices[ i+2 ];

		edges.push( new Edge( vertices[ id0 ], vertices[ id1 ] ) );
		edges.push( new Edge( vertices[ id1 ], vertices[ id2 ] ) );
		edges.push( new Edge( vertices[ id2 ], vertices[ id0 ] ) );

	}

	ctx.clearRect( 0,0,size, size );

	//render triangles
	ctx.strokeStyle = "#444";
	ctx.lineCap = "round";
	ctx.lineWidth = 1;
	edges.forEach( function( edge ){	edge.render( ctx );     });


	//COMPUTE THE MINIMUM SPANNING TREE

	var k = new KruskalMinimumSpanningTree( null, null );
	MST = k.compute( vertices, edges );


	time = 0;
	clearInterval( renderInterval );
	renderInterval = setInterval( render, 30 );

}

function render()
{
	if( time >= 1 )
	{
		clearInterval( renderInterval );
		console.log( "finished" );
		return;
	}

	//RENDER
	var i,
		max = parseInt( time * MST.length +.5 );

	//render the back
	ctx.strokeStyle = "#000";
	ctx.lineWidth = 20;
	for( i = 0; i < max; i++ )
	{
		MST[ i ].render( ctx );
	}

	ctx.strokeStyle = "#FFF";
	ctx.lineWidth = 10;
	for( i = 0; i < max; i++ )
	{
		MST[ i ].render( ctx );
	}

	time+=.1;
}

window.onresize = onResize;
window.onmousedown = onResize;
function onResize( e )
{

	width = window.innerWidth;
	height = window.innerHeight;
	size = Math.min( width, height );

	c.width = width;
	c.height = height;
	reset();

	e.preventDefault();

}

onResize( null );

External CSS

This Pen doesn't use any external CSS resources.

External JavaScript

This Pen doesn't use any external JavaScript resources.