CGAL users discussion list

["Scriven, David" <>]

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:

// A functor that returns true, iff the squared distance of a 2D point is > 810000 (i.e 900 squared);

struct dist2_gt_val {

    bool operator()(const NN_iterator2& it) { return ((*it).second > 810000);  }

};

// An iterator that only enumerates dD points with distance < 900 (squared)

typedef CGAL::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 2350 Health Sciences Mall,           fax: 604-822-2316 University of British Columbia, Vancouver, BC. V6T 1Z3, Canada