# Tag Info

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

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

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

2

Seems like the experts are not answering your question so I will try to provide an idea. But before I do that I strongly suggest that you look up in the literature for some sophisticated methods that have been already developed. However, without guaranteeing that this is a good or fast or efficient suggestion, I propose the following methodology. Keep in ...

2

You could use a Least Square fit approach to fit some polynomial via neighboring nodes. You could even make the Least Square fit weighted based on distances (potentially passed through something like a Gaussian function) from neighboring nodes to the location you want to evaluate the polynomial at. The latter approach, which can be viewed as local ...

2

To compute the Voronoi diagram of huge (>100 millions) sets of points, you can use the following algorithm: 1) create a kd-tree with all the points 2) for each point p [in parallel optionally] N = 10 while not finished compute the N nearest neighbors of the point p compute the intersection of the N half-spaces defined by p ...

1

It is not polynomial, but you may be interested in the Natural Neighbors interpolation (it fits well with Voronoi diagram). To evaluate the interpolant at a given point, insert the point into the diagram, and compute the volumes of the intersections between the new Vornoi cell (of the added point) and the Voronoi cells in the diagram before inserting the ...

1

The simplest way of doing this is to surround your iner box with a bigger box that contains at least all the nearest neighbours of the points within your inner box. Note that there will be an issue arising when the inner box is close to the edge of the encompassing data box: you have no external points. Calculating a Voronoi/Delaunay tessellation may be ...

1

I understand your question as: I want to draw Voronoi diagram for a subset of points such that it is same as the one which is obtained when considering the complete set of points. Voronoi diagrams are drawn by first joining neighboring points and then drawing a plane perpendicular to the line at the midpoint. You do this for all the nearest neighbors and ...

1

I suggest using the method described in a recent paper I published: http://people.seas.harvard.edu/~nbonneel/vorpaline.pdf The idea is simple, and is as follows : You start with your polygon, and the goal is to cut it with the mediator planes defined by each seed using Sutherland-Hodgman polygon clipping algorithm. That can be efficiently done in parallel ...

1

Building the Voronoï diagram of $n$ points already takes time $O(n \log n)$. I assume that what you want to compute is the intersection of the Voronoï diagram with the polygon. One way to compute this in time $O((n+p+k) \log(n+p))$ (where $k$ is the number intersection points between the polygon and the Voronoï diagram) is to first compute the Voronoï ...

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