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).

Filter by
Sorted by
Tagged with
4 votes
0 answers

FVM for non-regular domain with triangular mesh

Setup The 1D convection-diffusion equation is given by: \begin{equation}\tag{1} \frac{\partial u}{\partial t} + v \frac{\partial u}{\partial x} - \mu \frac{\partial^2 u}{\partial x^2} = 0, \end{...
VIVID's user avatar
  • 91
0 votes
2 answers

How to remove triangles in a hollow hemisphere shape?

So I have this code where I am designing a hollow hemispherical shape and I want to create a 3D volume to input it into FEBio software. I am using delaunay triangulation for meshing. But the problem ...
dazemood's user avatar
-1 votes
1 answer

Delaunay triangulation libraries for sets of 3D points CGAL

I need help. Do you know such a library for 3D triangulation - CGAL? How to get from it the order of joining the vertices to enter into your variable? Found nothing on the official site. Thanks!
Max Panchuk's user avatar
3 votes
2 answers

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 ...
EMP's user avatar
  • 2,069
5 votes
1 answer

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 ...
Thanos Maravel's user avatar
3 votes
0 answers

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 ...
Kimukook's user avatar
4 votes
0 answers

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:...
user27789's user avatar
5 votes
1 answer

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 ...
Misery's user avatar
  • 475
1 vote
0 answers

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 ...
Sara's user avatar
  • 111
4 votes
1 answer

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 ...
XavierStuvw's user avatar
6 votes
1 answer

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 ...
allo's user avatar
  • 607
1 vote
0 answers

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 ...
jensv's user avatar
  • 133
1 vote
1 answer

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 ...
mishatomsk's user avatar
1 vote
1 answer

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?
mich's user avatar
  • 11
3 votes
1 answer

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 ...
smilingbuddha's user avatar
27 votes
1 answer

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 ...
denfromufa's user avatar
1 vote
1 answer

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 ...
Rhei's user avatar
  • 402
3 votes
2 answers

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 ...
Juha Itkonen's user avatar
2 votes
5 answers

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:...
3DSpace14's user avatar
11 votes
3 answers

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 ...
mirams's user avatar
  • 433
8 votes
2 answers

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 ...
mengxia's user avatar
  • 81
1 vote
0 answers

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 ...
user avatar
29 votes
5 answers

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 ...
Open the way's user avatar
5 votes
0 answers

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$, ...
Paul's user avatar
  • 12k
12 votes
1 answer

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 "...
Deathbreath's user avatar
  • 1,042
10 votes
5 answers

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 ...
Paul's user avatar
  • 12k
6 votes
1 answer

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 ...
Paul's user avatar
  • 12k