Delaunay triangulation and relative-neighborhood graph on the sphere
Notes
1
Create n nodes in random positions on the unit sphere.
Input
Count of nodes
2
Create the Delaunay triangles that are formed by the nodes created in step 1.
Computation time scales with the fourth power of the count of nodes: the circumcircle of every trio of nodes (1, 2, 3) must be checked against every node that could be inside that circumcircle (4), in order to determine whether the circumcircle forms a valid triangle. According to Wikipedia, this could be reduced to n2 or even nlog(n), but I don't care enough to figure out flipping algorithms on the sphere at this time. (Note: Creating the SVG map seems to scale slower than linearly as well.)
3
Create the edges that compose the Delaunay triangles created in step 2.
4
From among the edges created in step 3, find those that are part of the relative-neighborhood graph.
5
Not implemented at this time
From among the edges found in step 4, find those that are part of the minimum spanning tree.
6
Project all the nodes and edges onto a two-unit cube with the gnomonic projection, unfold the cube so that all faces are coplanar, and display the result as an SVG file.
Output
Map (adjustable with CSS)
List of nodes
List of triangles
List of edges
The trio of coordinates given for a triangle indicates the circumcenter of that triangle—i. e., the location of the Voronoi node that corresponds to that Delaunay triangle.
All longitudes and latitudes are given, not in degrees, but in radians.
In maps that contain only a few nodes, every edge that crosses more than one face boundary will be drawn either incorrectly (the short arc rather than the long arc) or not at all. To fix this problem, increase the node count.
Input
Output
Estimated time to finish : seconds
Map
Grid color:
Delaunay nodes color:
Delaunay edges color:
Delaunay edges subset:
Voronoi nodes color:
Voronoi edges color:
Voronoi edges subset:
List of nodes
List of triangles
List of edges