Finding Distant Points in 2D
I have a set of points on an infinite (okay, double precision) 2D plane.
Given the convex hull for this set, how to find some points on the inner surface of the convex hull that are relatively far from all points of the input set?
In the image below, the black points are part of the original set, and the shaded area represents the space occupied by all the points if we "grow" them with a radius R.
The orange dots are examples of what I would like to receive. It doesn't matter where exactly they are, as long as they are relatively far from all the black points.
Search for the farthest points http://en.wiki.mcneel.com/content/upload/images/point_far_search.png
Update. Using delaunay's algorithm to find large empty triangles seems to be a great approach for this: Delaunay Solution http://en.wiki.mcneel.com/content/upload/images/DelaunaySolutionToInternalFurthestPoints.png
source to share
This is a good example of a problem that can be solved with KD-Trees ... there are some good notes in Numerical Recipes 3rd supplement.
If you're trying to find point locations that are relatively isolated ... perhaps the center of the largest quad cores would be a good candidate.
The complexity would be O (n log ^ 2 n) to create a KD-Tree ... and creating a sorted list of squares would be O (n Log n). Seems reasonable even for a large number of points (depending on your requirements, of course).
source to share
This is a naive algorithm:
- Get a list of points in a convex shape.
- Find the minimum distance to any other point from them.
- Rank all points by their respective R values
- Select the top x points.
For (2), thinking of it as looking for a radius still means that you end up calculating the distance from each point to each other's point, since figuring out if a point is within a given radius of another point is the same as and finding the distance between points.
To optimize your search, you can divide the space into a grid and assign a grid location to each point. Then your search (2) above will first check inside the same square and the surrounding 8 squares. If the minimum distance to another point is within one square, return that value. If it is one of 8 and the distance is such that a point outside 9 may be closer, you should then check the next contour of grid locations outside of these 9 for any closer than those within 9. Flush / repeat.
source to share