Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [delaunay-triangulation]

The process of generating a subdivision of ${R}^{2}$ consisting of conforming triangles from a given point set. The delaunay triangulation has the special property that no 4 points lie in the circumcircle of any given triangle. The concept extends to ${R}^{3}$ (sometimes referred to as a ...

3
votes
0answers
41 views

Approximate the largest simplex in N-dimensional Delaunay triangulation

I am working on determining the spatial information of a set of $M$ points in $N$-dimensional space. It is well-known that the construction of Delaunay triangulation is expensive in high dimensional ...
3
votes
0answers
70 views

Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions

I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:...
4
votes
1answer
105 views

Delaunay triangulation for datasets with four or more co-circular points

I am working on a library that requires subdivision of polygons into triangles. The polygons are divided into triangles by (more or less) random points that are inside them. In general, the approach ...
1
vote
0answers
63 views

How to measure euclidean distance between points with vtkDelaunay3D package? [closed]

I'm working with python vtkDelaunay3D package for a special purpose. I have set some points but I do not know how can I measure euclidean distance between points with this package. Is there anyone who ...
4
votes
1answer
231 views

Relationship between number of nodes, elements and sides in a triangular 2D mesh

Say that N is the number of nodes, E the number of elements and S the number of sides in a triangular 2D mesh. Is there a relationship that links these quantities, possibly taking into account that ...
7
votes
1answer
364 views

Is the marching triangles algorithm guaranteed to terminate?

Is the marching triangles algorithm guaranteed to terminate (sucessfully)? The algorithm does roughly speaking: iterate over all boundary edges project a new point, add a new triangle from the edge ...
1
vote
0answers
471 views

linearly interpolate and determine gradients for data on non-uniform grid

I have measurements of a quantity on a 3d grid. My measurements are distributed on four x-y planes similar to what is shown in the image below. The measurements roughly follow a Cartesian grid but ...
1
vote
0answers
208 views

Can TETGEN generate triangulation of a 2D point set?

I would like to link my Fortran 90 application to a library which would give me Delaunay triangulation (for a 2D set of points) and tetrahedralization (for a 3D set of points). As suggested in Fastest ...
1
vote
1answer
62 views

Finding Common Side of Triangle

Given a triangulation (geometry), are there known algorithm in finding common side of triangles, that is O(N) or better?
3
votes
1answer
345 views

Software for triangulating a point set (with restrictions)

I want to triangulate a point-set like the one below. I would like the triangulation of the point-set to have the following properties The triangles must have as vertices the black and orange points ...
18
votes
1answer
11k views

What is the preferred and efficient approach for interpolating multidimensional data?

What is the preferred and efficient approach for interpolating multidimensional data? Things I'm worried about: performance and memory for construction, single/batch evaluation handling dimensions ...
1
vote
1answer
197 views

Conceptual question about fitting of scattered data

What are the problems that arise when fitting (2D or 3D) a set of scattered data? (non uniformly distributed) I had some data I had to fit and I solved the problem using the ...
3
votes
2answers
379 views

Best incremental multidimensional Delaunay tessellation algorithm

I'm looking for a specific type of Delaunay tessellation algorithm. The algorithm should be: incremental so that I can add new sites inside known simplexes (i.e. no searching for the right simplex ...
2
votes
5answers
280 views

Iterating through a 3D triangle

Given a triangular plane formed by three points in R3 space {p1, p2, p3}, I want to iterate through all points on the triangle plane by using two variables, x0,y0, something like in this example: http:...
9
votes
3answers
876 views

N-dimensional Delaunay Tesselation Software Libraries

I have a set of known points/nodes irregularly spaced in N-Dimensional space (N>=2), and I would like a way to generate the Delaunay triangulation of these points, and return the corresponding ...
8
votes
2answers
2k views

Proper data-structure and algorithm for 3-D Delaunay triangulation

I have worked out some poor code to achieve the goal of 3D Delauney triangulation(random points in E3), but the time consuming is huge, and when five points are exactly (or nearly due to the round-off ...
1
vote
0answers
361 views

features recognition & reconstruction of 3d mesh delaunay matlab

I managed to display the coordinates of x,y and z into a 3D mesh by using delaunay function. The coordinates are in .obj format actually and i have read it into matrix form. Now, i would like to ...
25
votes
5answers
15k views

Fastest Delaunay triangulation libraries for sets of 3D points

Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of ...
4
votes
0answers
382 views

Why is my lower convex hull extraction algorithm not working?

Recently, I wrote an algorithm to obtain a delaunay triangulation of a random point set in $I=[-10,10]$x$[-10,10] \subset R^2$ by projecting these points onto the 3 dimensional paraboloid $z=x^2+y^2$, ...
12
votes
1answer
335 views

Enumeration of graphs deriving from Delaunay tessellations in 3D

Is there an algorithm that enumerates the graphs that correspond to some Delaunay tessellation of points in 3D? If so, is there an efficient parameterization of geometries that correspond to any "...
9
votes
5answers
5k views

How are the Voronoi Tesselation and Delaunay triangulation problems duals of each other?

I have always been told that the Voronoi diagram is the dual of the Delaunay triangulation problem. In what sense can they be duals of each other? I thought that dual problems (i.e. in linear ...
5
votes
1answer
301 views

What efficient algorithms are there to generate arbitrary dimensional meshes of simplices?

I know that delaunay triangulation can be extended into arbitrary dimensions by solving the convex hull problem in $(p+1)$ dimensions and projecting the lower hull into dimension $p$ to obtain a mesh ...