CGAL users discussion list

[Ben Supnik <>]

Hi Efi,


 wrote:
> Ben, I believe that you are right. Let me summarize, and you can 
> confirm. In the
> meantime, we'll fix it, and then provide a patch or something.

Your summary is completely right - since the curve direction can change 
but is cached, one of two changes is possible:

1. Enforce a new precondition (curve dir doesn't change or curve must be 
overlapping) and add appropriate docs and precondition tests.

2. Recompute the direction.

Right now I do (rough pseudocode) this to merge two half-edges:

void my_merge(Pmwx& arr, Halfedge_handle e1, Halfedge_handle e2)
{
        Curve_2 nc(Segment_2(
                e1->source()->point(),
                e2->target()->point()));
        Halfedge_handle m = pmwx->merge_edge(e1,e2,nc);
        Arr_halfedge_direction retained_dir = m->direction();
        typedef Arr_accessor<Pmwx>::Dcel_halfedge   DHalfedge;
        if(new_dir != retained_dir)
        {
                DHalfedge * dcel_he = &(*m);
                dcel_he->set_direction(new_dir);
        }
}

at least that's it in principle....basically my curve (segment traits 
cached) knows its direction, so if it mismatches I cast to a DCEL and 
fix it myself. :-)

> This condition (of having the target of one curve equal to the source of 
> the other) is probably not stated anywhere, as it does not really have 
> to be enforced, so for a geometry traits that does not enforce the 
> condition the problem is real, and besides that, as you state, it is 
> much more efficient to merge than to insert and delete.

Wait - I think the condition is weirder than that.  The "unspoken" 
precondition would be one of:

- The direction of the merged curve must match the direction of one of 
the underlying curves.  (This would be a crazy precondition, since 
client code doesn't want to know which edge is going to be used!)

- The new merged edge's curve is the union of the two edge's curves.

(That's not good mathematical speak - union isn't quite the term I want, 
but I think you know what I mean...for line segments this would mean a 
shared vertex and the curves are colinear...for polylines it would mean 
end points coincide and there isn't a change in the X direction of the 
curves, because the union wouldn't be monotonic.)

In other words, if the new curve must be the same point as the old two 
curves, your direction can't change as long as the new curve must be 
monotone.  But this somewhat reduces the utility of the merge_edge for 
certain weird cases.

> 2. It seems that a similar argument can and should be made for the split 
> operation.

I think so - looks like split_edge simply copies the direction from what 
halfedge to the other and doesn't check whether this is true.

> 3. In order to set the direction properly in the general case, a 
> geometric operation must be applied, that is, comparing 2 points for 
> equality. So far, the code of the merge operation (and the code of the 
> split operation for that matter) did not involve geometric operations. 
> This is not a big deal, but we may consider supporting split and merge 
> operations that assume that the direction does not change after all.

I would consider this point and another: if you were to require that 
split and merge not "move" the curve then you could fairly easily test 
the precondition and have a rapid way to 'cut a point' into a halfedge 
if you've already got the split curve data and you'd have no geometry 
operations.

By comparison, moving the whole edge over (which is what I am doing - 
sort of a "bypass" operation) is dangerous...get the bypass wrong and 
the arrangement is hosed; computing whether a bypass is safe is 
computationally non-trivially - a lot worse than checking directedness. :-)

So I think you could argue that what I am using is sort of an "advanced 
op" - perhaps appropriate for arr_accessor, like set_vertex.  You could 
increase precondition testing and give arr_accessor access to something 
like _split_edge...

Question: is it a requirement of all curve() types that 
is_directed_right exist, or is that just a side effect of the cached 
segment traits?  In my case, updating the halfedge direction is pretty 
cheap because I have it anyway just from initing the cached curve (which 
has to do a geometry op to build the cache).

cheers
ben




--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: