TODO
--------------------------------------------------
Problems to be solved from Sam's reading (september 2012)
--------------------------------------------------
*) Substitute iterator : it seems to be comparing the point directly, instead
of comparing the iterator. That look like a big performance killer.
*) I have marked with 'FIXME' all the lines where the code assumes, or seems to
assume that the vertex at infinity is at index 0 in the full cell. The code is
still working because the vertex at infinity is indeed at index 0, but this is
no more a requirement from the documentation, so that the code (Tr.h and
Delaunay_tr.h) should be changed. OR, we re-document 0 as the index of the
vertex at infinity.
ALL Remarks below are done or not important
--------------------------------------------------
Problems to be solved from the reviews (beginning 2012)
--------------------------------------------------
example delaunay does not execute properly
SAM: seems to be a compiler bug --> low priority.
OD: I am afraid that it is still some strange bug in the code that show up only in
some compilation circumstances.
running both delaunay compiled debug/release, the diverges after the 6th insertion (in 2d round)
in Triangulation_data_structure :
put a default value for dim in the constructor
(does not work, I do not understand why). OK done.
SAM: I've modified the Concept constructor's documentation to reflect this.
If it is not satisfying, we might remove this doc. from the Concept and
move it to the class documentation.
check that the perturbation scheme is independant of the order of insertion
SAM: It is your and Monique's scheme. It should be independent, which
is a requirement anyway for the Delaunay::remove() function to work
properly.
OD: seems ok, lexicographic order.
Add a template parameter Location_policy
ambient dim vs max dim
OD: global replace done, remains to get the dim from the traits (and not from the point of the traits)
check all is_valid function, precise in the doc what they are doing.
(do sth like 2/3 d)
SAM: I suggest that the documentation of the function in the concepts only
states that "any validity check can be performed here (see model doc. for
details)", and that we re document the same function in the class documentation
with details on what exactly is performed by the implementation.
OD: seems reasonable
SAM: I've changed my mind a little. We need some easy mandatory checks in
concepts T...DSFullCell and T...DSVertex so that we can rely on these tests in
the implementation of T.._data_structure, instead of having to re-implement them.
So : the concepts lists simple validity checks taht must be present, and refers
to the documentation of the models for possible additional validity checks
that are implemented.
--> This scheme is done (code&doc) for TDS TDSFullCell and TDSVertex and Triangulation.
--> ALL DONE.
small feature with iterator "all tuples"
make the code and doc agree on Flat_* stuff (orientation in a flat)
iterator on points in concept TriangulationVertex should be removed to keep requirements minimal
REMOVED: But this makes the concept TriangulationFullCell empty and useless.
make doc of TDS-FullCellStoragePolicy in user manual
DONE.
missing figures : Triangulation/fig/detail.png Triangulation/fig/illustration.png
--------------------------------------------------
Old todo list (beginning 2011)
--------------------------------------------------
Les premiers points meritent d'etre examinés
Je me replonge dans Triangulation en dim d
ma liste de trucs à faire ou questions à résoudre:
--- Constructeur de triangulation
prévoir un constructeur qui prends d+1 points en position générale
--- Doc 1.5 à faire
--- mirror_index
- policy a ajouter dans le user manual
- le code ne fait pas ce qui est dit dans la doc (ça ne retourne pas -1)
PS: Samuel tu as benché la policy ? ça vaut vraiment la peine de s'embeter avec ça ?
--- Face
- pourquoi une face ne pourrait pas être de pleine dimension ?
c'est pas la peine d'avoir un truc générique pour les faces de toutes dim sauf un
OD: J'ai propose de viré cette restriction dans la doc, mais il faudrait vérifier le code.
--- TriangulationTraits et DelaunayTraits
lower dimensional predicates
le truc de l'orientation "consistante"est quand même un peu délicat
- d'une part, je proposerai un truc du genre: le noyau doit fournir un iterateur
de points en position générale
(un truc fixe, ça donne toujours les mêmes points e.g. l'origine et les points
avec une coordonnée à 1 et les autres à 0).
Ce générateur permet donc de compléter tout ensemble de points pour obtenir
des points en position générale.
- d'autre part ???? il faut un minimum en plus pour qu'on comprenne que
l'orientation du sous-espace est stocké qq part.
--- TriangulationTraits has models
... il faut voir ce que l'on met vraiment.
--- Marque visité.
elle devrait etre dans le concept TDSFullCell
--------------------------------------------------
ci dessous les points ont deja etes traites
--- Index du sommet à l'infini.
Il est en ce moment prévu que le sommet à l'infini est l'index 0 dans les full
cell où il apparraît. Ça me semble très discutable, en particulier la tds ne sait
pas qui est à l'infini, et donc comment peut-elle garantir dans une manipulation
que toutes les cellules crées ou modifiées vont préserver cette position.
je suis donc pour virer ce truc ce qui implique des modifs dans la doc
(1.3 - ? p54) et dans le code.
en plus il y a des trucs pas cohérent, i.e. p. 50 dans la doc de locate
l'infini est en dernier, pas en premier.
finite_vertex_iterator marche pas
SAM: J'ai corrigé le problème, mais c'est pas super propre. Le problème
vient de boost::filter_iterator qui suppose que le prédicat de filtrage
prend en argument |const value_type &| plutôt que |iterator|. Mais
quand on veut tester si un sommet est infini, on a envie de comparer
les iterator (ou handle)... ce qui n'est pas possible avec le
filter_iterator de boost. (Le filter_iterator de CGAL appele le
prédicat de filtrage sur l'itérateur, et non pas sur la valeur vers
lequel il pointe, comme le fait boost. Mais je ne sais pas si le filtre
d'iterateur de CGAL est destiné à durer)
--- Orientation des cellules.
les cellules sont orientées positivement par convention
- le dire dans la doc (deux full cell partagent une facet, elles doivent avoir
des orientation complémentaires
- dans Triangulation, il faut virer la méthode "orientation"
(ou au minimum, la mettre advanced)
--- Triangulation is_infinite
j'avais viré les préconditions, et je maintiens.
en dim 0 on a une full cell finie et une infinie
en dim 1 on a 2 full cell infinie, 1 vertex/facet infini
et ok, en d=0, facet n'a pas de sens, mais l'utilisateur aura du mal a en avoir une
--- Triangulation fonctions incident_* et star
est-il nécessaire de reprendre leur doc? (on pourrait pointer sur celle de TDS)
au moins pour incident_upper_faces
--- dans Triangulation_data_structure.h insert_in_tagged_hole
on a l'air de supposer que full_cell(f) est marqué visité
(pourquoi ça serait pas l'autre représentation de la Facet f ?)
la doc de TDS::insert_in_hole est maintenant claire
Older todo list (2010 ?)
__________________________________________________________________________RENAMING
*) doc :
--------
*) code not done :
------------------
bring part of Delaunay::remove into TDS (see comments in Delaunay_triangulation.h, and item FUTURE below)
__________________________________________________________________________ALL
*) FUTURE: better system for simplex's flags to know if we can use them or not
in Delaunay_triangulation::remove(Vertex_handle)
_________________________________________________TRIANGULATION_DATA_STRUCTURE
*) Un-recursify insert_in_tagged_hole : crashed in dimension 8 : stack overflow.
*) TriangulationDataStructure:
- Should we put >> and << in the documentation of the class
Triangulation_data_structure ?
*) Triangulation_data_structure.h:
- Ensure that it is topologically possible to collapse the Face in
collapse_face(Face)
*) TriangulationDSVertex
- Should we put >> and << in the documentation of the class
Triangulation_ds_vertex instead of in that of the concept ?
*) TDSFullCellStoragePolicy
what is it ? => see the doc.
it is undocumented. => it is documented (Triangulation_ds_full_cell)
if the aim is to choose between "full representation" and "1-skeleton"
I would prefer a different TDS class, at least the doc has to rewriten a sentence
like "class TDS explicitely stores its vertices and full cells"
does not apply to 1-skeleton representation
=> no, this has nothing to do with 1-skeleton.
*) default dim parameter in constructor (especially in the static case)
done
________________________________________________________________TRIANGULATION
*) default dim parameter in constructor (especially in the static case)
done
*) Why vertex at infinity should have index 0 in all cells it appears ?
This is a convention that is enforced throughout the code. Makes it faster
to check for an infinite cell.
The "old" package "Convex_hull_d" does the same.
done
_______________________________________________________DELAUNAY_TRIANGULATION
________________________________________________________REGULAR_TRIANGULATION
*) write Regular_triangulation.h (!)
*) write RegularTriangulationTraits.tex
*) write Regular_triangulation.tex
-------------------------------------------------------
RANDOM DESIGN IDEAS extracted from Convex_hull.h
-------------------------------------------------------
- Use a policy tag to choose for incremental with inserts only or
incremental with removals and inserts.
In the first case: use Triangulation for storage.
In the second case: use Delaunay !
In this second case, we must keeps the points that are inserted in the hull,
as they may become part of the boundary later on, when some points are removed.
- Constructor with range argument uses quickhull.
*/
