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).
27
questions
4
votes
0
answers
120
views
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{...
- 91
0
votes
2
answers
75
views
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 ...
- 63
-1
votes
1
answer
232
views
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!
3
votes
2
answers
141
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 ...
- 2,069
5
votes
1
answer
680
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 ...
- 151
3
votes
0
answers
68
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 ...
- 31
4
votes
0
answers
174
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:...
- 41
5
votes
1
answer
231
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 ...
- 475
1
vote
0
answers
98
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 ...
- 111
4
votes
1
answer
2k
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 ...
- 246
6
votes
1
answer
702
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 ...
- 607
1
vote
0
answers
1k
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 ...
- 133
1
vote
1
answer
815
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 ...
- 11
1
vote
1
answer
128
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?
- 11
3
votes
1
answer
554
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
...
- 645
27
votes
1
answer
31k
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 ...
- 637
1
vote
1
answer
216
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 ...
- 402
3
votes
2
answers
454
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 ...
- 31
2
votes
5
answers
716
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:...
- 21
11
votes
3
answers
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 ...
- 433
8
votes
2
answers
4k
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 ...
- 81
1
vote
0
answers
367
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 ...
user3991
29
votes
5
answers
20k
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 ...
- 711
5
votes
0
answers
464
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$, ...
- 12k
12
votes
1
answer
374
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 "...
- 1,042
10
votes
5
answers
7k
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 ...
- 12k
6
votes
1
answer
393
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 ...
- 12k