# Tag Info

17

For the first part of my question, I found this very useful comparison for performance of different linear interpolation methods using python libraries: http://nbviewer.ipython.org/github/pierre-haessig/stodynprog/blob/master/stodynprog/linear_interp_benchmark.ipynb Below is list of methods collected so far. Standart interpolation, structured grid: http:/...

10

gStar4D is a fast and robust 3D Delaunay algorithm for the GPU. It is implemented using CUDA and works on NVIDIA GPUs. Similar to GPU-DT, this algorithm constructs the 3D digital Voronoi diagram first. However, in 3D this cannot be dualized to a triangulation due to topological and geometrical problems. Instead, gStar4D uses the neighborhood information ...

5

Yes there is a relationship, the Euler characteristic: For a 2-dimensional orientable manifold with boundaries embedded in $\mathbb{R}^3$, the Euler characteristic is $\chi = V - E + F = 2 - 2g - b$ where $V$ is the number of vertices, $E$ is the number of edges, $F$ is the number of faces, $g$ is the genus of the manifold, and $b$ is the number of ...

5

Why not transform your coordinates into the plane of the triangle and do your iterations there?

5

This feature seems to be available in CGAL

4

I think you can do this using convex hull software (e.g. QHull) via the lifting algorithm. At least, the documentation of matlab's "delaunayn" command seems to indicate as much.

4

This is implemented in qhull which is available from scipy (python). If you cannot use these implementations directly for some reason, the explanations of the data structures in the docs might be helpful. http://www.qhull.org/ http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html#scipy.spatial.Delaunay

4

Scipy already comes with Delaunay triangulation via Qhull, and is easy to install on Windows. Here's an example. As mentioned by Tyler Olsen in a comment above, "[a] normal Delaunay triangulation will work for any set of points where your enforced edges form the convex hull of the point set (as they do in this case)". In : %pylab Using matplotlib backend:...

4

According to the following paper, the algorithm creates cracks like you have (see figure 1 and surrounding discussion). Fournier, Marc. "Surface Reconstruction: An Improved Marching Triangle Algorithm for Scalar and Vector Implicit Field Representations." 2009 XXII Brazilian Symposium on Computer Graphics and Image Processing. IEEE, 2009. http://...

3

The duality between Voronoi cells and vertices of the triangulation is pretty clear: each vertex of the Delaunay triangulation is a site in the Voronoi diagram which gets associated with its Voronoi cell. To understand the duality between Delaunay triangles and Voronoi vertices, start by looking at this image from https://stackoverflow.com/questions/...

3

You can use exact predicates to detect co-circular points, and use symbolic perturbation to consistently decide which triangles to generate. Regarding exact predicates: If your point coordinates are integers, then it is easier, and you can use Hadamar's inequality to determine the range of valid coordinates for which the values computed by the predicates ...

3

I would recommend trying CGAL http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Section_39.2 , as Paul suggested above. CGAL is a robust and well-supported library that has been around quite some time. I've used it happily in the past, even on point sets with co-linear and co-planar points. I don't know if it's the very ...

2

If you know the number of edges and triangles, you could raster through a list of your triangles and create a triangle-to-edge map $(\mathcal{O}(N_{tri}))$ and simultaneously create the inverse map, which will give you the two triangles that share an edge. A naive search of that list for the right triangle-pair will be $\mathcal{O}(N_{edge})$, where \$N_{edge}...

2

If you use barycentric coordinates then the number of dimensions in which the triangle is embedded does not matter; the conversion from barycentric coordinates to euclidean coordinates is just a convex combination of the euclidean points at the vertices of the triangle.

1

TetGen is specifically designed to perform 3-D meshes -> tetrahedralization. I do not see a reliable and direct way to use it explicitly as a 2-D mesher. It is well pointed out that Triangle has a "surprisingly" similar API and specifically targets 2-D mesh generation. No surprise is there: both TetGen and Triangle are a part of pdelib2 software collection ...

1

Your comment mentions that the data shows a piecewise linear trend. In that case it would be most accurate to use linear interpolation. The other options you asked about (nearest neighbor and natural neighbor) result in piecewise constant (generally discontinuous) interpolants. The trade off is that it is more computationally expensive to compute the linear ...

1

As @NickAlger alludes, the incremental delaunay approach can scale exponentially with the dimension of the space, even if the final tesselation has few facets. Even if some computable solutions exist for special cases, it's unlikely that any practical algorithms exist for general tesselations, which seems to be what you're looking for.

1

To iterate over the triangle points you could follow this algorithm: find the longest edge and use it as direction for the inner loop, in the following it is assumed that the longest edge is (p1,p2) with the third point is p3 For the inner loop always iterate along the direction D:(p1->p2) Iterate along this line starting at point A=p1 with a given step ...

1

You can try the geogram software that I'm developping: http://alice.loria.fr/software/geogram/doc/html/index.html It has a parallel algorithm that computes the DT of 14 million vertices in less than 19 seconds on an Intel Core I7 (for 1 million vertices it takes around 0.8 s)

Only top voted, non community-wiki answers of a minimum length are eligible