G# - Computational geometry for .NET

G# - Computational geometry for .NET

G# is a computational geometry math library for .NET.

It features conforming Delaunay triangulations, 2d and 3d convex hulls, smallest enclosing circles and rectangles, bounding boxes and much more. It easily handles large point sets.

PLUS: Access exact and floating point arithmetic predicates!

2D Delaunay triangulations and Digital Terrain Modelling

G# is perfectly suitable for Digital Terrain Modelling (DTM):

its fast O(n·log(n)) randomized incremental algorithm enables the extremely fast triangulation of very large point sets. At the same time, G# is very robust due to the implementation of exact arithmetic. Click here to see an example.

G# can also triangulate edge constraints (breaklines), holes, islands and arbitrary shaped bounds by both inserting ("conforming Delaunay") and not inserting ("constraint Delaunay") additional triangulation points. Click here to see an example.

Digital Terrain Modelling requires editing triangulated surfaces: G# provides methods to compute contour and profile lines, to project points and lines onto and to to slice such surfaces, to import and export them and lots of other DTM features.

Click here for more details on the implemented triangulation algorithm, valid input data and restrictions.

Surface reconstruction from wireframe edges

Given a set of completely unordered wireframe edges, G# can reconstruct a surface consisting of triangular and quadrialteral faces in O(n·log(n)) time.

2D and 3d convex hulls

A 2d convex hull is the shortest path enclosing a planar set of points. G# computes the convex hull of n planar points in O(n·log(n)) time. Click here to see an example.

A 3d convex hull encloses a set of 3d points with a minimal surface area. G# computes the convex hull of n 3d points in O(n·log(n)) time. Click here to see an example. Click here to see a performance chart.

For ultimate robustness, G# uses exact arithmetic.

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.

Minimum area and perimeter enclosing rectangles

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.

Smallest enclosing circles

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

3d polylines and polygons

A polyline is a list of sorted edges where the end point of each edge is the start point of the next edge. G# converts hundreds of thousands of unordered lines in space into 3d polylines. Ultra fast!

A closed planar polyline is regarded as a polygon. G# provides fast exact arithmetic point-in-polygon and polygon-in-polygon tests.

Stereolithography (STL) file import and export

Import and export binary and ASCII stereolithograpy STL format files. This file format is widely spread and supported by many other software packages.

G# also supports the simple ASCII object file format (.off). This is a widely spread format to describe polyhedra consisting of polygons.

Predicates

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

Amongst the most important predicates, G# provides .NET implementations of Jonathan R. Shewchuck's robust exact arithmetic predicates in C.

Credits

Check out Jonathan R. Shewchuck’s "Triangle" site! The exact arithmetic predicates used in G# are a .NET implementation of Jonathans predicates in C, which are in the public domain.

Scholar