# 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 tetrahedralization), and ${R}^{d}$ (as mesh of simplices).

24 questions
Filter by
Sorted by
Tagged with
104 views

### Is the similar subdivision of a delaunay mesh still delaunay?

I have a delaunay triangulation for a 2d box with say an airfoil inside. If I uniformly refine this mesh by subdividing each triangle in the mesh into 4 triangles by halving each edge, is the ...
131 views

### How can one prove the duality of Voronoi and Delaunay?

Hoping I'm not misunderstanding the concept here, but it is my understanding that Voronoi Diagrams and Delaunay Tesselations are 'dual' to one another, owing to the fact that each' solution makes ...
52 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 ...
110 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:...
186 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 ...
93 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 ...
859 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 ...
627 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 ...
903 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 ...
556 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 ...
80 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?
430 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 ...
24k 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 ...
209 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 ...
435 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 ...
542 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:...
1k 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 ...
3k 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 ...
364 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 ...
18k 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 ...
434 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$, ...
362 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 "...
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 ...