I'd like to create a 3d Delaunay triangulation with a pre-specified
circumradius bound. At first I thought a dense enough regular grid is a good solution, but due to either the perturbation of the grid points or floating point arithmetic (which is it?) this creates very large tetrahedra. Say I want to limit the circumradius to 0.1. With 6000 points, most tetrahedra indeed have a circumradius below 0.1. However, a few will have circumradii as large as 3. Increasing the number of points won't help, as it will only increase the size and number of the tetrahedra with large circumradii. #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Delaunay_triangulation_3.h> #include <CGAL/point_generators_3.h> #include <vector> #include <iostream> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_3 Point; typedef CGAL::Creator_uniform_3<double, Point> Creator; typedef std::vector<Point> Vector; typedef CGAL::Delaunay_triangulation_3<K> Dt; typedef Dt::Tetrahedron Tetrahedron; double circumradius( const Tetrahedron& t) { return CGAL::sqrt(CGAL::squared_distance(CGAL::circumcenter(t),t.vertex(0))); } int main(){ int npts = 6000; //// Create a vector of random points Vector points; CGAL::points_on_cube_grid_3( 1, npts, std::back_inserter(points), Creator() ); //// Create a Delaunay triangulation from those points Dt T; T.insert(points.begin(),points.end()); /// Write out tetrahedron whose circumradii are too large for (Dt::Finite_cells_iterator cell = T.finite_cells_begin(); cell != T.finite_cells_end(); ++cell) { double circum = circumradius(T.tetrahedron(cell)); if (circum > 0.1) {std::cout << circum << std::endl;} } } Thank you for any help! -- Sent from: http://cgal-discuss.949826.n4.nabble.com/ -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
Can't you use the Mesh_3 package and set a criteria on the size of the
tetrahedron? The triangulation will not be a regular triangulation (and not a Delaunay one). https://doc.cgal.org/latest/Mesh_3 Sebastien. On 07/16/2018 06:36 PM, Dahn wrote: > I'd like to create a 3d Delaunay triangulation with a pre-specified > circumradius bound. At first I thought a dense enough regular grid is a good > solution, but due to either the perturbation of the grid points or floating > point arithmetic (which is it?) this creates very large tetrahedra. > > Say I want to limit the circumradius to 0.1. With 6000 points, most > tetrahedra indeed have a circumradius below 0.1. However, a few will have > circumradii as large as 3. Increasing the number of points won't help, as it > will only increase the size and number of the tetrahedra with large > circumradii. > > #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> > #include <CGAL/Delaunay_triangulation_3.h> > #include <CGAL/point_generators_3.h> > #include <vector> > #include <iostream> > > typedef CGAL::Exact_predicates_inexact_constructions_kernel K; > typedef K::Point_3 Point; > typedef CGAL::Creator_uniform_3<double, Point> Creator; > typedef std::vector<Point> Vector; > typedef CGAL::Delaunay_triangulation_3<K> Dt; > typedef Dt::Tetrahedron Tetrahedron; > > double circumradius( const Tetrahedron& t) { > return > CGAL::sqrt(CGAL::squared_distance(CGAL::circumcenter(t),t.vertex(0))); > } > > > int main(){ > int npts = 6000; > //// Create a vector of random points > Vector points; > CGAL::points_on_cube_grid_3( 1, npts, std::back_inserter(points), Creator() > ); > > //// Create a Delaunay triangulation from those points > Dt T; > T.insert(points.begin(),points.end()); > > /// Write out tetrahedron whose circumradii are too large > for (Dt::Finite_cells_iterator cell = T.finite_cells_begin(); cell != > T.finite_cells_end(); ++cell) { > double circum = circumradius(T.tetrahedron(cell)); > if (circum > 0.1) {std::cout << circum << std::endl;} > > } > } > > > > Thank you for any help! > > > > -- > Sent from: http://cgal-discuss.949826.n4.nabble.com/ > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
Hi Sebastien,
thank you for the suggestion. Sadly I cannot, as the triangulation is an initial configuration for an MCMC <https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo> algorithm which attempts to converge to a regular triangulation with certain properties (but has to start with certain properties for it to work, too). However, I have realized that a simpler solution might be to create a point pattern such that the resulting tetrahedra are regular (as in made of equilateral triangles), a 3d version of the equilateral triangle tiling <http://gwydir.demon.co.uk/jo/tess/bigtri.htm> . I am not able to test it now, but I will report back once I do. In the meantime, other suggestions are definitely welcome. -- Sent from: http://cgal-discuss.949826.n4.nabble.com/ -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
Another thing to try it to use the Lloyd algorithm, it should make you
tetrahedron almost identical as the points will be equally spaced. Sebastien. On 07/27/2018 08:49 AM, Dahn wrote: > Hi Sebastien, > > thank you for the suggestion. Sadly I cannot, as the triangulation is an > initial configuration for an MCMC > <https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo> algorithm which > attempts to converge to a regular triangulation with certain properties (but > has to start with certain properties for it to work, too). > However, I have realized that a simpler solution might be to create a point > pattern such that the resulting tetrahedra are regular (as in made of > equilateral triangles), a 3d version of the equilateral triangle tiling > <http://gwydir.demon.co.uk/jo/tess/bigtri.htm> . > I am not able to test it now, but I will report back once I do. In the > meantime, other suggestions are definitely welcome. > > > > -- > Sent from: http://cgal-discuss.949826.n4.nabble.com/ > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss |
Free forum by Nabble | Edit this page |