G# - Computational geometry for .NET

A 2d triangulation of a 3d set of points is the triangulation of the projection of the points onto the XY plane. This simply says that the Z-coordinate is ignored for the triangulation.

A Delaunay triangulation maximizes the minimum angle of all triangles in the triangulation. This property makes it the triangulation of choice for projectable point sets as they occur - for example - in a Digital Terrain Model (DTM) or a Digital Elevation Model (DEM).

G# implements a fast O(n·log(n)) randomized incremental algorithm which enables you to triangulate even very large point sets very fast. G# implements exact arithmetic thus providing ultimate robustness.

Click here to see an example. Click here to see a performance chart.

A 2d conforming Delaunay triangulation allows to insert edge constraints while maintaining the Delaunay property by the insertion of additional triangulation points.

By defining boundaries, holes and islands can be added to a triangulation.

Click here to see an example.

A 2d convex hull is the shortest path enclosing a planar set of points. G# finds the convex hull of n planar points in O(n·log(n)) time. Exact arithmetic provides ultimate robustness.

Click here to see an example.

A 3d convex hull encloses a set of 3d points with a minimal surface area. G# finds the convex hull of n 3d points in O(n·log(n)) time. Exact arithmetic provides ultimate robustness.

Click here to see an example. Click here to see a performance chart.

Compute mass moments of inertia and the pricipal axes of the mass moments of inertia of 3d convex hulls! Use these methods to compute a bounding box along the principal axes of a 3d convex hull. Click here to see how this bounding box can be used as a fast approximate solution for a 3d container loading problem.

G# uses the rotating caliper technique to compute the minimum area and minimum perimeter enclosing rectangles of a 2d point set in O(n·log(n)) time.  Click here to see an example.

Compute the smallest enclosing circle of a planar point set in expected O(n) time!

Click here to see an example. Click here to see a performance chart.

Many geometric algorithms base on a few standard tests, whose robustness and performance are crucial for the robustness and performance of the entire algorithm.

G# provides state-of-the-art implementations of the most important predicates. Amongst them, you will find robust exact arithmetic predicates due to the work of Jonathan R. Shewchuck, which have been ported to .NET.

Check out Jonathan R. Shewchuck’s  great "Triangle" site! The exact arithmetic predicates used in G# are a .NET implementation of Jonathan Shewchuck’s predicates in C, which are in the public domain. ceometric can not guarantee that the ported predicates work correctly. Nevertheless, they never failed in numerous tests. If you have problems using them, please report.