CODEWITHSUNDEEP
c#2dpoint
David Rutten
David Rutten

Reputation: 4806

Finding Remote Points in 2D

I have a set of points on the infinite (well, double precision) 2D plane.

Given the convex hull for this set, how can find some points on the inside of the convex hull that are relatively far away from all the points in the input set?

In the image below, the black points are part of the original set and the hatched area represents the space taken up by all the points if we "grow" them with radius R.

The orange points are examples of what I'd like to get. It doesn't really matter where exactly they are, as long as they are relatively far away from all the black points.

Furthest Point Search http://en.wiki.mcneel.com/content/upload/images/point_far_search.png

Update: Using a delaunay 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

Upvotes: 2

Views: 450

Answers (2)

tbischel
tbischel

Reputation: 6477

This is a good example of a problem that may be solved using KD-Trees... there are some good notes in Numerical Recipes 3rd Addition.

If you are trying to find point locations that are relatively isolated... maybe the center of the largest quad elements would be a good candidate.

The complexity would be O(n log^2 n) for creating the KD-Tree... and creating a sorted list of quad sizes would be O(n Log n). Seems reasonable for even a large number of points (of course, depending on your requirements).

Upvotes: 1

richardtallent
richardtallent

Reputation: 35374

This is a naive algorithm:

  1. Get the list of points within the convex shape.
  2. Of those, find the minimum distance to any other point.
  3. Rank all points by their respective R values
  4. Select the top x points.

For (2), thinking of this as a radius search still means you end up calculating the distance from each point to each other point, because finding out whether a point lies within a given radius of another point is the same thing as finding the distance between the points.

To optimize the search, you can divide the space into a grid, and assign each point to a grid location. Then, your search for (2) above would first check within the same square and the surrounding 8 squares. If the minimum distance to another point is within the same square, return that value. If it is from one of the 8 and the distance is such that a point outside the 9 could be closer, you have to then check the next outline of grid locations outside those 9 for any closer than those found within the 9. Rinse/repeat.

Upvotes: 1

Related Questions