Computational Geometry

Fri Jul 14 20:24:30 PDT 2000

Way back in 1994 I realized that the web could be described as a directed graph, whose nodes are documents and whose branches are links. I wrote software that drew these graphs, but it didn't work well because of the huge amount of interconnection. Webviz solves this problem by using hyperbolic geometry.

This is just one of my several run-ins with computational geometry. The Directory of Computational Geometry Software contains a list of free computational geometry programs and packages. Geomview, an interactive 3D geometry viewing program written at The Geometry Center, runs under my current platform of choice, Linux. It's so nice not to have to worry about windoze any more!

The web has been very good to computational geometry. Netlib continues to provide access to triangle, hull, and sweep. When you really need a mesh for finite element analysis, you should check out Finite element mesh generation . If you need a really fancy mesh, look in the Meshing Research Corner. Some of those guys mesh like their lives depend on it.

When you need the Voronoi object, and you have more dimensions than you should, then you can find relief at the Home page for Qhull.

I shouldn't be amazed, but I am anyway, by the claims made about The Ipe extendible drawing editor . How about editing arbitrary postscript, extensibility, computing Voronoi diagrams, and clipping to polygons? After all, we're talking free software that runs on Linux!

It seems like we all live within a world of constraints, and it is difficult to see what all our possibilities are. Some nice work has been done on Geometric Constraint Solving, but they aren't giving away the code.

Now, what if you wanted to glue a mesh generator to Matlab and solve an isotropic nonconstant-coefficient Laplace equation?

Polygon soups are models which contain no adjacency information and obey no topological constraints. RAPID is a rapid and accurate polygon interference detection library for large polygon soups.

Since this is supposed to be both fun and educational, maybe you should just go straight to David Eppstein's pages, which include The Geometry Junkyard, one of the most interesting places on the net.