Urquhart Graph

Urguhart Graph

In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation. Using the as3delaunay library to generate the triangulation, I then proceeded to remove the longest edge from each triangle to create the Urquhart graph. I had to modify the library slightly to keep track of the triangles when building the delaunay triangulation. Luckily the code was already there, just commented out.

This demo shows that the Urquhart is a subset of the Delaunay and that a Minimum Spanning Tree is often, but not always, a subset of the Urquhart.

The code

private function createUrquhartGraph(voronoi:Voronoi):Vector.
{
	var hash:String;
	var hashline:Function = function(line:LineSegment):String
	{
		return "" + Math.max(line.p0.x, line.p1.x) + "" + Math.min(line.p0.x, line.p1.x) + "" + Math.max(line.p0.y, line.p1.y) + "" + Math.min(line.p0.y, line.p1.y);
	};

	var uniqueSegments:Object = {};
	var line1:LineSegment, line2:LineSegment, line3:LineSegment;
	var triangles:Vector. = voronoi.delaunayTriangles();
	for each (var triangle:Triangle in triangles)
	{
		line1 = new LineSegment(triangle.sites[0].coord, triangle.sites[1].coord);
		line2 = new LineSegment(triangle.sites[1].coord, triangle.sites[2].coord);
		line3 = new LineSegment(triangle.sites[2].coord, triangle.sites[0].coord);

		var maxLength:Number = Math.max(line1.length, line2.length, line3.length);
		if (uniqueSegments[hashline(line1)] == null)
			uniqueSegments[hashline(line1)] = {line: line1, toRemove: false};
		if (uniqueSegments[hashline(line2)] == null)
			uniqueSegments[hashline(line2)] = {line: line2, toRemove: false};
		if (uniqueSegments[hashline(line3)] == null)
			uniqueSegments[hashline(line3)] = {line: line3, toRemove: false};

		// cannot inline above for some reason
		if (line1.length == maxLength)
			uniqueSegments[hashline(line1)].toRemove = true;
		if (line2.length == maxLength)
			uniqueSegments[hashline(line2)].toRemove = true;
		if (line3.length == maxLength)
			uniqueSegments[hashline(line3)].toRemove = true;
	}

	var objectKeys:Array = allObjectKeys(uniqueSegments);
	var urquhartGraph:Vector. = new Vector.();
	for each (var key:String in objectKeys)
		if (uniqueSegments[key].toRemove == false)
			urquhartGraph.push(uniqueSegments[key].line);

	return urquhartGraph;
}