Generating a Voronoi Tessellation in JavaScript

The JavaScript code below, when run, generates a random Voronoi tessellation and displays it in two different representations. A Voronoi tessellation, according to its Wikipedia article, is “a partitioning of a plane into regions based on distance to points in a specific subset of the plane”.

To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

Featured image

<html>
<body>

<div id="divMain" />
<script type="text/javascript">

// main

function main()
{
	var voronoiTest = VoronoiTessellation.generateRandom
	(
		new Coords(100, 100), // size
		32 // numberOfCells
	);

	voronoiTest.drawAsPixels();
	voronoiTest.drawAsCellBorders();
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.contains = function(item)
	{
		return (this.indexOf(item) != -1);
	}

	Array.prototype.insert = function(indexToInsertAt, itemToInsert)
	{
		this.splice(indexToInsertAt, 0, itemToInsert);
	}
}

// classes

function ColorHelper()
{
	// static class
}
{
	ColorHelper.RGBComponentMax = 255;

	ColorHelper.random = function()
	{
		var returnValue = "rgb("
			+ Math.floor(Math.random() * ColorHelper.RGBComponentMax) + ","
			+ Math.floor(Math.random() * ColorHelper.RGBComponentMax) + ","
			+ Math.floor(Math.random() * ColorHelper.RGBComponentMax)
			+ ")";

		return returnValue;
	}
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		return this;
	}

	Coords.prototype.floor = function(other)
	{
		this.x = Math.floor(this.x);
		this.y = Math.floor(this.y);
		return this;
	}

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y);
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

	Coords.prototype.randomize = function()
	{
		this.x = Math.random();
		this.y = Math.random();
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function VoronoiTessellation(size, cells)
{
	this.size = size;
	this.cells = cells;
}
{
	// static methods

	VoronoiTessellation.generateRandom = function(size, numberOfCells)
	{
		var cells = [];

		for (var i = 0; i < numberOfCells; i++)
		{
			var cellColor = ColorHelper.random();

			var cellPos = new Coords().randomize().multiply
			(
				size
			);

			var cell = new VoronoiTessellationCell
			(
				ColorHelper.random(),
				cellPos
			);

			cells.push(cell);
		}

		var returnValue = new VoronoiTessellation
		(
			size,
			cells
		);

		return returnValue;
	}

	// instance methods

	VoronoiTessellation.prototype.cellClosestToPos = function(posToCheck)
	{
		var cellClosestSoFar = this.cells[0];
		var displacement = VoronoiTessellation.cellClosestToPos_CoordsTemp;
		displacement.overwriteWith
		(
			posToCheck
		).subtract
		(
			cellClosestSoFar.seedPos	
		);
		var distanceToCellClosestSoFar = displacement.magnitude();

		for (var i = 1; i < this.cells.length; i++)
		{
			var cell = this.cells[i];

			var distanceToCell = displacement.overwriteWith
			(
				posToCheck
			).subtract
			(
				cell.seedPos
			).magnitude();

			if (distanceToCell < distanceToCellClosestSoFar)
			{
				cellClosestSoFar = cell;
				distanceToCellClosestSoFar = distanceToCell;
			}		
		}

		return cellClosestSoFar;
	}
	VoronoiTessellation.cellClosestToPos_CoordsTemp = new Coords();

	VoronoiTessellation.prototype.cellVerticesCalculate = function()
	{
		var pixelPos = new Coords(0, 0);

		for (var y = 0; y < this.size.y - 1; y++)
		{
			pixelPos.y = y;

			for (var x = 0; x < this.size.x - 1; x++)
			{
				pixelPos.x = x;

				this.cellVerticesCalculate_Position(pixelPos);
			}
		}

		this.cellVerticesCalculate_Order();
	}

	VoronoiTessellation.prototype.cellVerticesCalculate_Order = function()
	{
		var displacementFromSeedToVertex = new Coords();

		for (var c = 0; c < this.cells.length; c++)
		{
			var cell = this.cells[c];
			var cellSeedPos = cell.seedPos;
			var cellVertices = cell.vertices;

			var anglesFromSeedToVertices = [];

			for (var v = 0; v < cellVertices.length; v++)
			{
				var vertex = cellVertices[v];

				displacementFromSeedToVertex.overwriteWith
				(
					vertex
				).subtract
				(
					cellSeedPos
				);

				var angleFromSeedToVertex = Math.atan2
				(
					displacementFromSeedToVertex.y,
					displacementFromSeedToVertex.x
				);

				anglesFromSeedToVertices.push
				(
					angleFromSeedToVertex
				);
			}

			var vertexIndicesOrdered = [];

			for (var v = 0; v < anglesFromSeedToVertices.length; v++)
			{
				var angleUnsorted = anglesFromSeedToVertices[v];

				var vi;
				for (vi = 0; vi < vertexIndicesOrdered.length; vi++)
				{
					var vertexIndexSorted = vertexIndicesOrdered[vi];
					var angleSorted = anglesFromSeedToVertices[vertexIndexSorted];
					if (angleUnsorted < angleSorted)
					{
						break;
					}
				}

				vertexIndicesOrdered.insert(vi, v);
			}

			var verticesOrdered = [];

			for (var vi = 0; vi < vertexIndicesOrdered.length; vi++)
			{
				var vertexIndex = vertexIndicesOrdered[vi];
				var vertex = cellVertices[vertexIndex];
				verticesOrdered.push(vertex);
			}

			cell.vertices = verticesOrdered;
		}
	}

	VoronoiTessellation.prototype.cellVerticesCalculate_Position = function(parentPos)
	{
		var pixelPos = VoronoiTessellation.cellVerticesCalculate_Position_CoordsTemp;
		var cellsClosest = [];

		this.cellVerticesCalculate_Position_Edges
		(
			parentPos,
			cellsClosest
		);

		for (var y = parentPos.y; y <= parentPos.y + 1; y++)
		{
			pixelPos.y = y;

			for (var x = parentPos.x; x <= parentPos.x + 1; x++)
			{
				pixelPos.x = x;

				cellClosest = this.cellClosestToPos(pixelPos);
				if (cellsClosest.contains(cellClosest) == false)
				{
					cellsClosest.push(cellClosest);
				}				
			}
		}

		if (cellsClosest.length > 2)
		{
			for (var i = 0; i < cellsClosest.length; i++)
			{
				var cell = cellsClosest[i];
				if (cell != null)
				{
					cell.vertices.push(pixelPos.clone());
				}
			}
		}
	}
	VoronoiTessellation.cellVerticesCalculate_Position_CoordsTemp = new Coords();

	VoronoiTessellation.prototype.cellVerticesCalculate_Position_Edges = function(parentPos, cellsClosest)
	{
		var cellDummy = null;
		if (parentPos.x == 0)
		{
			cellsClosest.push(cellDummy);
		}
		if (parentPos.x == this.size.x - 2)
		{
			cellsClosest.push(cellDummy);
		}
		if (parentPos.y == 0)
		{
			cellsClosest.push(cellDummy);
		}
		if (parentPos.y == this.size.y - 2)
		{
			cellsClosest.push(cellDummy);
		}
	}

	VoronoiTessellation.prototype.drawAsCellBorders = function()
	{
		this.cellVerticesCalculate();

		var canvas = document.createElement("canvas");
		canvas.width = this.size.x;
		canvas.height = this.size.y;
		
		var graphics = canvas.getContext("2d");
		graphics.strokeStyle = "Gray";
		graphics.fillStyle = "Gray";

		graphics.strokeRect(0, 0, this.size.x, this.size.y);

		for (var c = 0; c < this.cells.length; c++)
		{
			var cell = this.cells[c];
			var cellVertices = cell.vertices;
			graphics.strokeStyle = cell.color;

			graphics.beginPath();

			var vertex = cellVertices[0];

			graphics.moveTo(vertex.x, vertex.y);

			for (var v = 1; v < cellVertices.length; v++)
			{
				var vertex = cellVertices[v];
				graphics.fillRect
				(
					vertex.x, vertex.y,
					1, 1
				);
				graphics.lineTo(vertex.x, vertex.y);
			}

			graphics.closePath();
			graphics.stroke();

		}

		var divMain = document.getElementById("divMain");
		divMain.appendChild(canvas);
	}

	VoronoiTessellation.prototype.drawAsPixels = function()
	{
		var canvas = document.createElement("canvas");
		canvas.width = this.size.x;
		canvas.height = this.size.y;
		
		var graphics = canvas.getContext("2d");

		var pixelPos = new Coords(0, 0);

		for (var y = 0; y < this.size.y; y++)
		{
			pixelPos.y = y;

			for (var x = 0; x < this.size.x; x++)
			{
				pixelPos.x = x;

				var cellClosest = this.cellClosestToPos(pixelPos);
			
				graphics.fillStyle = cellClosest.color;
				graphics.fillRect
				(
					pixelPos.x, pixelPos.y,
					1, 1
				);
			}
		}

		var divMain = document.getElementById("divMain");
		divMain.appendChild(canvas);
	}
}

function VoronoiTessellationCell(color, seedPos)
{
	this.color = color;
	this.seedPos = seedPos;

	this.vertices = [];
}

// run

main();

</script>
</body>
</html>
Advertisements
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s