CGAL users discussion list

[Winnie Hellmann <>]

Thanks for the replies! Sorry for the long delay - I had been on vacation.

On 05.10.2011 19:23, Ben Supnik wrote:
> But you can figure out what face you are in (or what edge/vertex you are
> on) from this or from arr_walk_along_a_line_point_location - each should
> run in linear time, more or less.
Actually, the landmarks location and the walk along line location failed 
for me in some cases when the point was outside the convex hull. In the 
documentation I could not find anything that explains this behavior and 
if it is undesired, I would try to come up with a minimal example.

> So are you saying that you have the contours of the polygon in an
> arrangement but you do not have any of the containment information?
I do have an Arrangement_2 which consists of non-overlapping paths, i.e. 
closed edge chains, and one Point_2, which is not inserted in the 
Arrangement_2 because I assumed that insertion and deletion of a point 
in Arrangement_2 is more than linear complexity (please correct me if 
I'm wrong - I did not find anything about that in the documentation).

> If you have not saved containment information, I think that (for well
> formed general polygons you can figure out if the face you fall in is a
> 'hole' by comparing the twin of each edge on its outer CCB to the
> unbounded face. This means you'll be double-linear time - once for the
> location, and again for the resolution of whether you're in a hole or not.
Thanks! I really like that approach - assuming that location is linear 
complexity. Would a comparison like arr.unbounded_face() == e.face() be 
sufficient for that check? I.e. is Face_handle meant to be equal to all 
other handles pointing to the same face?

> You could in theory do slightly better by writing your own
I would rather want to use existing algorithms in CGAL, because of 
stability / required testing time.

> There are a bunch of ways to get more speed...you can tag your faces as
> holes or not in linear time and then retain that on the arrangement, and
> batched queries will beat individual ones if that is useful.
Tagging the holes was one of my first ideas, but actually the 
Arrangement_2 structure is given - so I can't add tags/additional data 
to faces.

On 06.10.2011 18:47, Efraim Fogel wrote:
> If you shoot, say upwards, then you get the unbounded face if there is 
> nothing above the query point.
But only if the query point is not on an edge - because then the ray 
would not shoot that edge.

Thanks in advance for any further help,
Winnie