https://github.com/CGAL/cgal
Tip revision: 5220a1748908f06307974db093f33706159c2cac authored by Laurent Rineau on 21 October 2020, 07:27:10 UTC
Merge remote-tracking branch 'lrineau/Triangulation_2-improve_CDT_plus_2-GF' into releases/CGAL-5.0-branch
Merge remote-tracking branch 'lrineau/Triangulation_2-improve_CDT_plus_2-GF' into releases/CGAL-5.0-branch
Tip revision: 5220a17
TODO
TDS
- operator->() dans it/circ de facettes/edges (idem T2, a coordonner)
- reflechir a un support de facettes explicites (cf papier de Giesen)
- nettoyer les trucs 2d only (face_circulator etc)
- Bistellar flips ? (cf shewchuck's SoCG'03 paper).
(it's when you have 4 coplanar points, you break 4 cells,
and it gives 4 cells back).
- More compact representation [inspired by a CUJ article for lists] :
instead of having a cell which stores 4 vertex pointers, it only stores the
XOR of them. And a Cell_handle now additionaly stores the 4 vertex pointers
of the cell, the "context".
One problem is the Cell_iterator : it loses the context, so I think that
one way to work around this is to write the Cell_iterator as based on the
Vertex_iterator (a bit like the reverse used to be made) : we iterate over
the vertices, and for each vertex, we compute the incident cells, but we
pick only those whose smallest vertex (address-wise) is the one in question.
T3
- documenter le 2eme tableau de Triangulation_utils
- degree() devrait-il, au niveau geometrique, ne pas compter le sommet infini ?
- is_valid devrait verifier l'enveloppe convexe
- prevoir differentes sorties : geomview (ameliorer le rendu pour
donner un effet de perspective), vrml...
cf Polyhedron_3, file I/O.
Delaunay
- Put side_of_bounded_sphere_3 into the DelaunayTriangulationTraits_3 as
it is used in the is_Gabriel tests
- dual(vertex) -> Polyhedron_3
- faire en sorte que les types line, ray, etc Voronoi ne soient plus
qu'optionnels dans la traits, et requis seulement si les fonctions
dual sont effectivement utilisees
- remplacer les create_face du remove2D par des create_cell et virer
les create_face de la tds
- optimiser remove :
- algo d'Olivier si constructions filtrees disponibles (cf Olivier
rappel de la reunion a ce sujet)
- pour la creation de la TDS_2, on devrait pouvoir faire plus simple,
sachant que le trou n'est pas quelconque, mais etoile, et donc on peut
profiter de ca pour avoir les adjacences directement (peut-etre en
squattant le flag des cellules pour y mettre un pointeur vers la facette
2d correspondante).
- natural neighbors de Raphaelle a integrer
- Pb du type de points pour les fonctions "dual" (robustesse dans le cas
des tetraedres presque plats) rounding ?
Regular :
- acces aux hidden points et remove sur hidden points, etc
- Regular_triangulation_euclidean_traits_3.h
add a functor Construct_smallest_orthogonal_weighted_point_3
to build at the same time both the center and the square radius
of the smallest orthogonal sphere
- la cell_base speciale qui stocke une liste de points caches ou pas (et un
tag qui dit si oui ou non elle stocke les points caches ou pas), et un
iterator pour y acceder. A DOCUMENTER.
- remove - les dimensions 1 et 2 ne sont pas gerees.
- faire marcher la hierarchie avec. Le probleme est qu'on delete des
vertex, et donc la hierarchie est perdue avec ses pointeurs up/down qui
pointent dans l'espace, du coup...
La solution qu'on a discutee est :
- la hierarchy devrait avoir tous les etages superieurs simplement Delaunay,
et pas autre chose.
- le insert() (ou find_conflict) de Regular devrait fournir un iterator sur
les Vertex_handle correspondant aux points qui seront caches, et en
fonction de ca, une hierarchy speciale Regular fera ce qu'il faut.
- programmer centre ortho-sphere de 4 points. Aussi centre de l'ortho-cercle
de 3 points... (requete Tamal Dey)
- .dual()
Hierarchie
- nettoyer hierarchie
cf mail Mariette
la hierarchie surcharge correctement certaines
versions du insert() et locate()
et fait n'importe quoi pour les autres....
(c'est tout ce qui se trouve apres
// added to make the test program of usual triangulations work
// undocumented
public:
.....
)
--------------------------------------------------------------------
General
- mettre des locate_2D, locate_3D, insert idem, pour eviter les tests
redondants sur la dimension a chaque insertion.
- trouver une interface avec T_2 qui permette d'eviter de reprogrammer
tout le 2d dans le 3d
- valgrind
- gcov
- const handle, const it, const circ ...
- utiliser le cell_container_iterator partout ou c'est possible
(unifier le code pour differentes dimensions)
TEST-SUITE
- si un jour elle est revue, voici quelques idees pour l'organiser :
- prendre un noyau exact pour tout, et supposer qu'on l'a dans les tests.
- avoir des fonctions qui generent differentes distributions
(cas degeneres, grands nombre de points...)
- pour nearest_vertex() : comparer le resultat avec Spatial_searching ?
(c'est impossible dans le cas ou il y a plusieurs points equidistants,
puisqu'il y a un choix arbitraire, il n'y a aucune raison que ca soit
le meme dans un autre package)
- Test-suite Delaunay : .dual() n'est pas vraiment teste...