analytics

Friday, February 13, 2015

Binary nearest neighbor for hull

Suppose you have some points, have found the centroid, and the bounding circle to the farthest point C(1)...

Now find the point halfway around the circle C(1/2) from the farthest point and the nearest neighbor from the point collection to that point...
Now further subdivide the circle to C(1/4) and C(3/4) and find the nearest neighbors...
Continue but here when the nearest neighbor is a point that's already been selected by one of the two blue points sudivided, the point on the circle is colored red...

Subdivide only between two points on the circle colored blue...
And continue until there are no more adjacent blue points on the circle...
Now the points ordered clockwise are a hull, but might not be convex. .


No comments:

Post a Comment