CGAL users discussion list

[Sebastien Loriot <>]

I'm not sure to get everything correctly.

Are you working in the plane? You mention 2D surface and then
has_on_bounded_side() of Polygon_2.

If you are working in the plane and all the query points are available
at the beginning, a sweep should be the fastest algorithm.

Actually, if you sort all convex hull segments, then you simply have
to locate the point within the sorted segment. Then sort the selected
segments along the y-axis and find the two segments enclosing your query 
point.

Best,

Sebastien.

On 6/23/22 00:30, "Scriven, David" ( via 
cgal-discuss Mailing List) wrote:
> Following up on the earlier discussion - I have thousands of points on a 
> two-D surface and a number (hundreds) of convex hulls of various sizes. 
> My problem is to determine which points are in which hull.
>
>
> My solution has been to look for the nearest neighbours of the hull 
> centroid using the incremental neighbour search with a fixed distance:
>
>
> //Afunctorthatreturnstrue,iffthesquareddistanceofa2Dpointis>810000(i.e900squared);
>
> structdist2_gt_val{
>
> booloperator()(constNN_iterator2&it){return((*it).second>810000);}
>
> };
>
> //AniteratorthatonlyenumeratesdDpointswithdistance<900(squared)
>
> typedefCGAL::Filter_iterator<NN_iterator2,dist2_gt_val>NN_distance_iterator2;
>
>
> which was OK provided no dimension of the hull was greater than 900.
>
> I've recently been presented with data where many of the hulls are huge 
> although there are many small ones too.
> I wondered whether there was version of the incremental search that can 
> use a variable limit - i.e. that the squared distance could be defined 
> for each hull. The value would be the max. distance from the hull 
> centroid to the edge of the hull.
>
> Is there an easier way to do this?
>
>
> David Scriven, Ph.D.                 e-mail :  <>Dept Cellular & Physiological Sci. ph: 604-822-7812 <tel:604-822-7812> 
> 2350 Health Sciences Mall, fax: 604-822-2316 <tel:604-822-2316> 
> University of British Columbia, Vancouver, BC. V6T 1Z3, Canada
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss