mikolalysenko / delaunay-triangulate Goto Github PK

Easy to use robust Delaunay triangulation

License: MIT License

JavaScript 100.00%

delaunay-triangulate's Introduction

delaunay-triangulate

Triangulates a set of points into a Delaunay triangulation. This code works in arbitrary dimensions, and both in the server and in the browser.

Here are some in browser demos:

Example

var triangulate = require("delaunay-triangulate")

var points = [
  [0, 1],
  [1, 0],
  [1, 1],
  [0, 0],
  [0.5, 0.5]
]

var triangles = triangulate(points)

console.log(triangles)

Install

npm install delaunay-triangulate

API

`require("delaunay-triangulate")(points[,pointAtInfinity])`

Constructs a Delaunay triangulation over points

points is a collection of points in Euclidean space.
pointAtInfinity is a flag, which if set adds an extra point at infinity to give the spherical compactification of the triangulation. The index of the point at infinity is -1

Returns A list of cells representing the faces of the triangulation. These are triangles in 2D or tetrahedra in 3D.

Credits

delaunay-triangulate's People

Contributors

Stargazers

Watchers

delaunay-triangulate's Issues

Cell orientation problem with some 3D point sets

These two point sets of each five points in 3D space differ only by one component (x in fouth coordinate) and are triangulated correctly into two tetrahedra. However, the second one (points2) seems to have a strange orientation:

var points1 = [ [0, 0, 0], [2, 0, 0], [2, 1, 0], [2, 0, 1], [4, 0, 0] ];
var points2 = [ [0, 0, 0], [2, 0, 0], [2, 1, 0], [1, 0, 1], [4, 0, 0] ];

The two delaunay-triangulate generated tetrahedra are:

var simplices1 = [ [3, 2, 1, 4], [2, 0, 3, 1] ];
var simplices2 = [ [3, 2, 1, 4], [3, 2, 0, 1] ];

Oddly cell-orientation returns the same orientation for all three result simplices (-1), but somehow they still seem to differ---at least looking at the 2-skeletons shows that the resulting triangles are clearly oriented differently:

var k2simplices1 = [ [2, 0, 1], [0, 3, 1], [2, 0, 3], [2, 3, 1] ];
var k2simplices2 = [ [2, 0, 1], [3, 0, 1], [3, 2, 0], [3, 2, 1] ];

Is this a bug or expected? This behavior is unfortunate, because boundary calculation (e.g. in simplicial-complex and simplicial-complex-boundary) and reduce-simplicial-complex don't work on the the simplices having a different orientation (they expect the same orientation). Additionally, visualization becomes problematic, since normals can't be easily calculated anymore (because orientation isn't consistent). If this is expected, is there already a way to unify orientation across all simplices?

Unexpected output for 3D points in grid layout

Generating the Delaunay tetrahedralization of points in a regular grid pattern, I'm getting results that differ from what I'd expect:

Note the long lines connecting vertices at far ends of the layout. If this rule for n=2 ...

no point in P is inside the circumcircle of any triangle in DT(P).

... applies in n=3 as something like no point P is inside the circumsphere of any tetrahedron in DT(P), surely those tetrahedra are breaking that rule? I haven't gotten far enough in debugging yet to render the tetrahedra individually. Or have I misunderstood how Delaunay works in 3D? I was hoping for non-intersecting, somewhat uniform tetrahedra.

I'm seeing essentially the same result with another library, too.

Thanks!