CGAL users discussion list

[Mariette Yvinec <>]

Hi all
Let me add to this discussion a short story of what happened in 2D  for 
regular triangulation.
At the beginning the hidden points were stored as points in the hiding 
cell (here a facet)
as in the 3d case. Then we (Andreas and I) invented the hidden vertices
as a (convenient) way to make the hierarchy work on regular triangulations.
In fact when, upon a deletion, a hidden point  reappears into a vertex 
of the triangulation,
it is reinserted in the triangulation, meaning that you get for this 
point a new vertex-handle
and we had to code a rather dirty swap to make the vertex-handle of an 
hidden vertex that
becomes unhidden unchanged.
So, in the end, it appears that the notion of hidden vertices is not so 
convenient
and that a cleaner  version to make the hierarchy work would be to remove
the vertices corresponding to a point that gets hidden from all the 
levels of the hiearchy.
However it seems that it is some work to implement this strategy and nobody
did it yet.

Joshua A Levine wrote:
> Monique; Sylvain,
>
> Thanks for the replies.  I agree that dealing with hidden points is 
> awkward, and treating them as vertices has its problem.  Although I'm 
> not so sure that it wouldn't be easier to create a dummy vertex that 
> stores the point and give each cell a list of vertex handles which are 
> hidden instead of actual points.  It would seem to me that using the 
> vertex structure to gain an extra level of indirection might be worth 
> the sacrifice of having vertices that aren't really vertices.
> Sylvain's solution of storing additional information at the traits 
> level instead of the vertex level is good.  It solves how to store the 
> information, but you still run into problems on the insertion itself.  
> When you insert a point, the return type leaves much to be desired.  
> If the vertex is hidden, where is it hiding?  Harder: If the point I 
> inserted hides current vertices, which ones?  So now for every 
> insertion extra work external to the triangulation has to be done to 
> verify special cases for insertion.  To not duplicate work, this means 
> gathering all information before inserting and then do a fast insert 
> where I pass the cell to insert within.
>
> Thanks again, I'll see what kind of solution I can come up with here 
> and let you know if I find something that might be helpful.
>
> Josh
>
>
> On 11/16/2007 3:58 AM, 
>
>  wrote:
> > Dear Joshua,
> >
> > You are right, hidden points are stored as points in the 3D package.
> > In my opinion, storing hidden _vertices_ is ackward since when a 
> > point is hidden, then it is by definition not a vertex of the 
> > triangulation. Possible additional information are related more to 
> > the points themselves than to the combinatorial vertices.
> >
> > Still, the need for manipulating (accessing, removing,...) hidden 
> > points in an easier way is known. It is noted in our todo lists.
> >
> > Best
> >     Monique Teillaud
> >
> > Joshua A Levine wrote:
> > > Hi CGALers,
> > >
> > > I was wondering about the mechanism for storing hidden vertices in 
> > > the Regular_Triangulation_3 class.  It seems that unlike in the 2D 
> > > case, these vertices are only stored as a list of weighted points 
> > > associated with whichever cell they are contained in.  There seems 
> > > to be no global way to access all of the hidden points for the 
> > > triangulation (outside of checking every cell).  Is this correct?
> >
> >
> >
> > > Moreover, because they are stored as a list of weighted points 
> > > instead of as a list of actual vertices, it doesn't seem like there 
> > > is a mechanism for storing additional information associated with 
> > > these vertices.  By this I mean if I have a custom Vertex class with 
> > > some additional members, and if I'd like to use that class to store 
> > > additional information for a point I want to insert, I may not be 
> > > able to if that point becomes hidden.  Is there a recommended way to 
> > > store this sort of information without using some external 
> > > bookkeeping?  Is there even a moderately easy way to do it _with_ 
> > > external bookkeeping?
> > >
> > > To keep it simple for discussion purposes, consider a 
> > > Regular_Triangulation_3 class where I want to store an associated id 
> > > for each vertex I insert.  But the triangulation is changing with 
> > > both insertions and deletions, so at any time a point I insert could 
> > > itself be hidden, or could hide other vertices already present.  
> > > Similarly, on deletion I could unhide some points, but I'm pretty 
> > > sure never hide anything.
> > >
> > > Thanks,
> > > Josh

--
Mariette Yvinec
Geometrica project team
INRIA  Sophia-Antipolis