CGAL users discussion list

[Andreas Fabri <>]

 wrote:
> I am running an application in which a polygon with holes gets divided into two parts, and I have to determine which holes go to which side. This can be done by checking if a point on the hole is within one of the halfs or another. 
>
> However, doing so with CGAL::bounded_side for each point will probably take 
> me O(n^2) for all holes (provided that there can be n holes). Is there a way 
> to do one check for all the points at once, using CGAL? (which will take O(n))
>
> Amir.

A kind of plane sweep would do it. Or use the triangulation as follows:

Put the two polygons in a constrained Delaunay triangulation, mark the
faces as being part of A or B or nothing.

Take one point per hole. Sort all those with spatial_sort, and
locate them in the triangulation, taking the resulting face as
hint for where to start the next point location.

andreas