1

Imagine lots of points like of order 10M.

Now I randomly draw a circle in a given space.

This circle will now enclose some points depending on the center and radius.

Now, I want to select all the points which are present inside this circle.

The brute force approach is very inefficient.

Is there a better way to solve this.

P.S- I am coding in python.

Thanks

Edit: Brute Force Approach:

Select a point from the space , calculate the distance from the center and if it is less than the radius, then it lies inside otherwise outside.

The brute force is, well I have to go thru all the points and this is problametic because in the next iteration I am going to again select a point in random and repeat above steps.So this is like O(n^2).. Can I do better?

frazman
  • 32,081
  • 75
  • 184
  • 269
  • What's the "brute force approach"? Are the points fixed ahead of time or are you looking to generate points inside the circle? Do you know anything about how the points are distributed? – Ted Hopp Nov 19 '12 at 16:07
  • brute force? you mean converting to polar coordinates and filtering by distance is too inefficient? i don't think it can be done better than O(n) :( – Aprillion Nov 19 '12 at 16:08
  • Hi. thanks for comments.. see edits.. Also, as in the edit.. this step will be repeated.. hence, it will turn out to be O(n^2).. :( – frazman Nov 19 '12 at 16:12
  • This might be related to http://stackoverflow.com/questions/481144/equation-for-testing-if-a-point-is-inside-a-circle – bn. Nov 19 '12 at 16:15
  • I am trying to implement DBSCAN method http://en.wikipedia.org/wiki/DBSCAN – frazman Nov 19 '12 at 16:17
  • 1
    The wikipedia article you link to says you can do better if you maintain an index that allows you to do the neighborhood query in O(log n). – mbeckish Nov 19 '12 at 16:27
  • A vp-tree seems appropriate. [Python code here](http://www.logarithmic.net/pfh-files/blog/01164790008/VP_tree.py). – A. Webb Nov 19 '12 at 17:15

1 Answers1

2

Arrange points in advance in some space partitioning structure.

For example, quad-tree. Traverse the tree. As each node corresponds to a square on the plane, you can quickly check if that square intersects with your circle (having at least one corner inside the circle or circle being entirely inside the square). If it does intersect, continue traversing down that node, if it does not intersect, skip all of its children, potentially eliminating a large number of individual checks against the points in that square.

chill
  • 16,470
  • 2
  • 40
  • 44