CODEWITHSUNDEEP
algorithmgeometryvoronoi
Hans
Hans

Reputation: 7

Voronoi Filtering: How does this algorithm work?

Could someone please explain how this algorithm works in a simple way? The only thing I could find at the moment was this paper, which in my opinion does not explain the algorithm very simply.

EDIT: What I understand so far is that we have some set of sample points as an input. In the next step the Voronoi Cells and the Delaunay Triangulation have to be made. Next, the algorithm uses the voronoi vertices (which form the crust?) to remove triangles from the Delaunay triangulation.

Upvotes: 0

Views: 428

Answers (1)

Iddo Hanniel
Iddo Hanniel

Reputation: 2066

First, it is easier to understand the 2D Crust algorithm (the following description was modified from here):

1) Let S be the sample points and V be the vertices of the Voronoi diagram of S.
2) Let S' be the union of S and V.
3) Let D be the Delaunay triangulation of S'.
4) An edge of D belongs to the crust of S if both its endpoints belong to S.

However, for 3D points, a simple extension of the above 2D algorithm does not give good results, mainly because the Delaunay tetrahedra can contain ill-conditioned tetrahedrons ("slivers"). Therefore, for 3D, the authors perform additional filtering to avoid these problems. In particular, they don't use all the Voronoi vertices, only the so-called "poles".

I believe their Siggraph98 conference paper is easier to understand than the paper you reference. I also found this presentation to be a pretty good summary of the algorithm.

Upvotes: 1

Related Questions