CGAL users discussion list

[Efraim Fogel <>]

The following might be something to start with. Perform any sequence of
Boolean set operations, but use General_polygon_set_2. Extract the
underlying arrangement and perform a point location on the arrangement,
or even a batched point location in case you have several points.

Andreas Fabri wrote:
> 
>  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


-- 
  ____  _        ____             _
 /_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                        _/