Issues in dD Triangulation

[efifogel]

Issues in dD Triangulation

1. [ ] In Triangulation_data_structure.h the function mirror_vertex() has several problems:
   • [x] I believe that the return type should be Vertex_handle.
   • [x] The call s->mirror_vertex(i) is missing the cur_dim second parameter.
   • [ ] Also, the const version of mirror_vertex() is missing. As a matter of fact, several const or mutable versions are missing in all constructs in this package.
2. [ ] In Triangulation_data_structure.h, the body of the function collapse_face() defines a Full_face using the default constructor (namely, Full_cell s), but the default constructor is canceled. (There is one that accepts the dimension...)
3. [ ] In the manual of insert_in_tagged_hole(..., OutputIterator oi) please explicitly indicate the type of the dereferenced object *oi.
4. [x] In the manual of insert_in_hole(ForewardIterator start, ForwardIterator end, ...) the text says, and I quote, "Removes the full cells in the range C=[s, e)". Change s and e to start and end, respectively (or the other way around...)
5. [x] In both variants of insert_in_hole() and in insert_in_tagged_hole() the input parameter facet should probably be passed as a reference (and not by value).
6. [x] The manual of Triangulation lists the function collapse_face(), while the code as contract_face(). This function also calls the member contract_face() of Triangulation_data_structure, while the latter has collapse_face().
7. [ ] At least in one case the name of a concept (as opposed to the name of a template parameter) has the suffix _, which is, of course, wrong; it also causes the link to the concept page to be absent. Issue git grep -i "concept [^ ]*_".
8. [ ] The Facet type is is not documented (does not exist in the Reference Manual).
9. [ ] The documentation of the several functions (e.g., clear(), incident_full_cells(), incident_faces(), and star(), are missing in Triangulation. (The do exist in TriangulationDataStructure concept.
10. [ ] The description of the function insert_in_hole() of the concept TriangulationDataStructure refers to a point p, but p is not a parameter (as opposed to the function insert_in_hole() of the Triangulation class template.
11. [ ] Three functions (i.e., (insert_in_hole() X 2, insert_in_tagged_hole()) of the concept TriangulationDataStructure accept a parameter of type Facet by value; why don't them accept a const reference? Observe that similar functions of the Triangulation class template do accept const reference.
12. [ ] In the ref. man. of Triangulation_data_structure::insert_in_tagged_hole() it says, and I quote, "A set C of full cells satisfying the same condition as in method Triangulation_data_structure::insert_in_hole().... " It is unclear what is C exactly. As far as I understand, the method Triangulation_data_structure::insert_in_hole() accepts C as input, but Triangulation_data_structure::insert_in_tagged_hole() accepts a facet.
13. [ ] What is so special about is_valid() that it is specified twice: once in the concept TriangulationDataStructure and once in the model Triangulation_data_structure?
14. [ ] The description of the 3rd locate() in CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ > is missing the facet parameter.
15. [ ] Why isn't there a default constructor for Face? It is passed, e.g., to one of the overloaded locate() member functions as an output parameter, so it is irrelevant how it is initialized.
16. [ ] The description of the constructor that accepts an optional dimension parameter of CGAL::Triangulation_data_structure< Dimensionality, TriangulationDSVertex_, TriangulationDSFullCell_ > is missing.
17. [ ] The CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ > has a major defficiency, which makes it useless in many cases: The user cannot provide a Triangulation_data_structure (Tds) instance, which implies that neither the Vertex nor the Full_cell constructs can be extended to include user auxiliary data. In the manual it says and I quote: "Regular_triangulation can be defined by specifying only the first parameter, or by using the tag CGAL::Default as the second parameter." So, first, this makes this class a "toy" (as opposed to "professional"). Second, it is not quite true. One can extend it using the source code below, which only shows that the interface is screwed up. On the one hand, the user is expected to provide a "bare" traits (such as a D-dimensional kernel). On the other hand, she or he is expected to provide a Tds already defined with the adapter. It can be fixed no problem using the rebind idiom (see, e.g., Arrangement_on_surface_with_history_2.h), perhaps with slightly breaking backward compatibility, but seriously, the way it is currently written is a bit amateurish.

Source Code

#include <CGAL/Epick_d.h> #include <CGAL/point_generators_d.h> #include <CGAL/Regular_triangulation.h>

#include #include #include #include

const int N = 100; // Number of points

const int D = 5; // Dimension using Dt = CGAL::Dimension_tag<D>; using Kernel_d = CGAL::Epick_d<Dt>;

using Traits = CGAL::Regular_triangulation_traits_adapter<Kernel_d>;

using Vb = CGAL::Triangulation_ds_vertex; using Vertex_data = bool; using V = CGAL::Triangulation_vertex<Traits, Vertex_data, Vb>; using Sd = CGAL::TDS_full_cell_default_storage_policy; using Cb = CGAL::Triangulation_ds_full_cell<void, Sd>; using Fc_data = bool; using Fc = CGAL::Triangulation_full_cell<Traits, Fc_data, Cb>; using Tds = CGAL::Triangulation_data_structure<Dt, V, Fc>;

using T = CGAL::Regular_triangulation<Kernel_d, Tds>; // using T = CGAL::Regular_triangulation<Kernel_d>;

using Bare_point = Kernel_d::Point_d; using Weighted_point = Kernel_d::Weighted_point_d;

int main() { // Instantiate a random point generator CGAL::Random rng(0); typedef CGAL::Random_points_in_cube_d<Bare_point> Random_points_iterator; Random_points_iterator rand_it(D, 1.0, rng);

// Generate N random points std::vector<Weighted_point> points; for (int i = 0; i < N; ++i) points.push_back(Weighted_point(*rand_it++, rng.get_double(0., 10.)));

T t(D); assert(t.empty());

// Insert the points in the triangulation t.insert(points.begin(), points.end()); assert( t.is_valid() ); std::cout << "Regular triangulation successfully computed: " << t.number_of_vertices() << " vertices, " << t.number_of_finite_full_cells() << " finite cells." << std::endl; std::cout << typeid(Weighted_point).name() << std::endl; std::cout << typeid(T::Weighted_point).name() << std::endl;

return 0; }

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): All
• Compiler: All
• Release or debug mode: Both
• Specific flags used (if any):
• CGAL version: Latest
• Boost version: Irrelevant
• Other libraries versions if used (Eigen, TBB, etc.):

[afabri]

4,5, and 6 fixed in PR #8862. Also 1.1 and 1.2.

[afabri]

contract_face() is hence not tested :< For OutputIterator you mean just that its value type must be Full_cell_handle?

[afabri]

1.3 I do not understand. Maybe you can give the URL to the line in the file?

[efifogel]

Regarding the OutputIterator, if you ask me, and this should be consistent across the entire documentation, the text should be much more precise and say:

\pre Dereferencing <the-name-of-the-parameter> must yield an object of type .

BW, the OutputIterator concept does not require value_type, so it cannot be used.

In this particular instance nothing is specified. (In the doc. of insert_in_hole() the output iterator is at least mentioned...

[efifogel]

Regarding collapse_face() issue, it's a bug in the code---it fails to compile.

[afabri]

Which concept has a trailung underscore. Nothing here

[efifogel]

It's in the user manual. Issue the command:

git grep -i "concept [^ ]*_"

[mglisse]

Hi, could you add some

```c++

and

```

around your block of code? As is, it is hard to read, half of the includes appear empty... (I don't think I can edit someone else's post)

EDIT: (it is done) thanks!

[mglisse]

1. Three functions (i.e., (insert_in_hole() X 2, insert_in_tagged_hole()) of the concept TriangulationDataStructure accept a parameter of type Facet by value; why don't them accept a const reference? Observe that similar functions of the Triangulation class template do accept const reference.

I don't think it matters for the concept. It should probably be changed in the class Triangulation_data_structure though, which does the same.