CGAL users discussion list

Hi,

I am still really not convinced that hiding vertices instead of points 
would make anybody's life easier... And, as Mariette mentioned, it would 
force us to do some dirty hacks on pointers.

Hiding points is clean and corresponds to what is really happening when 
computing a regular triangulation.

However, as I noticed in my first answer in this thread, I know that 
some interface for the user to easily play with hidden points, is 
missing. Adding this in the future, while keeping everything clean, is 
on our todo-list...

Joshua A Levine wrote:
>  wrote:
>
> > 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.
> >
> >
> > I don't see how storing hidden points directly instead of dummy 
> > vertices that contain hidden point creates an extra level of 
> > indirection. I would have said the contrary, since dummy vertices are 
> > an additional level of indirection to access hidden points.
>
> Sorry, I mispoke.  What I meant was using the dummy vertices gives the 
> extra layer of indirection (which seems like a positive to me).
>
> > > 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.
> >
> >
> > What do you need to remember from before the insertion? the poinst 
> > that were already hidden by cells that were deleted by the insertion?
> >
> > In any case, I don't see how dummy vertices would help here.
>
>
> In addition to carrying along extra information, which can be done with 
> Sylvain's technique, the idea is that by returning a vertex handle that 
> is at least valid you don't need external checks which can potentially 
> duplicate work.  For example, if you have to do:
>
> Point p;
> Vertex_handle vh = rt.insert(p);
>
> if (vh == Vertex_handle()) {
>  //(A) figure out where p is hiding (something insert() already did)
>  //handle any special cases for hidden vertices
>  //note you can't use vh to do any of this though because vh is garbage.
> } else {
>  //if I need it, gather the list of vertices that p's insertion hid
> }
>
> Naively, if you did it in that order it would be duplication of effort, 
> since insert has to do something like (A) in the first place.  Of course 
> (A) could be done before the insert (i.e. rt.locate()) to prevent 
> duplicate effort, and then the result remembered so that you can then 
> can speed up the insert() by passing a cell with it.  Instead it might 
> be pretty handy, since a vertex knows about one cell, if vh->cell() was 
> the hiding cell.  If you were using dummy vertices, you could do:
>
> vh = rt.insert(p);
>
> if (rt.is_hidden(vh) /* i.e. vh is a dummy vertex */) {
>  //vh->cell() is the cell hiding it
> }
>
> So by using the dummy vertex you save yourself the need to call locate() 
> first, external from the insertion.  I realize in the end that it's a 
> matter of opinion, but having to call locate() before every insertion 
> seems like a bit cumbersome for the interface. 
>
> > > 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.
> >
> >
> > ok, let us know if you have an idea about the ultimate interface for 
> > insert().
> > Maybe several insert() functions could be offered, to compute 
> > different informations depending on the user's needs.
>
>
> So for my project I don't need to do anything special on insertion for 
> hidden vertices as opposed to others.  I just want them to go in and 
> stay floating around maintaining what information I originally placed in 
> there.  This is where the motivation is coming from:  I want to take a 
> sequence (linked list) of points and maintain that sequence throughout 
> the Delaunay.  So instead of just storing an id, what I'd like to store 
> is a handle to the next and past vertex in the sequence.  And it's ok if 
> the sequence goes through hidden verts.  This would be easier to do if 
> every inserted point had it's own handle that stayed consistent 
> throughout the life of the triangulation.
>
> Thanks,
> Josh