Jump to content
  • Advertisement
Sign in to follow this  
kirby900

circle containing greatest number of points

This topic is 3015 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Greetings, all. Here's my situation: I have a set of points bounded by a circle of radius r. My goal is to identify within this circle a region bounded by another circle of of radius 0.5r that contains the greatest number of points -- with an understanding that there might be multiple circles that would enclose the same number of points. From some of the Google searches I've tried thus far, this seems to be a type of "cluster analysis" problem. I invite any input on how best to achieve the goal.

Share this post


Link to post
Share on other sites
Advertisement
For every pair of points in the set that are not farther than r apart, look at the two circles of radius 0.5*r that pass through those two points. Pick the circle that contains the most points among all those. The algorithm is O(n^3). If n is not too big, you could just do that.

Share this post


Link to post
Share on other sites
That's an approach I had not considered. The number of points is small enough to make the approach feasible, but the method described allows for the smaller circle to lie partially outside the larger circle. I apologize for not mentioning this constraint initially, but I want to ensure that the smaller circle lies completely within the larger circle, allowing for the possibility of the circles touching at one point.

Share this post


Link to post
Share on other sites
As a speed optimization, you could always pre-process the points into a grid so that when you count how many points are in a circle you only consider the points in the grid squares which the circle touches at all.

Also if a circle completely contains a grid square you can then just add the count of points inside the grid without having to test each point against the circle (:

Share this post


Link to post
Share on other sites
The number of points to be evaluated will be so small (probably no more than 15 or so) that a grid optimization might not offer much benefit. Still, it's a handy tip.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
For every pair of points in the set that are not farther than r apart, look at the two circles of radius 0.5*r that pass through those two points. Pick the circle that contains the most points among all those.


Are you sure that optimal solution will contain two points on the edge?

Quote:
but I want to ensure that the smaller circle lies completely within the larger circle,


When you have two points, you can check if the circle they define lies within the outer circle.

Share this post


Link to post
Share on other sites
Quote:

From some of the Google searches I've tried thus far, this seems to be a type of "cluster analysis" problem. I invite any input on how best to achieve the goal.

Clustering algorithms aren't going to help you if you want the optimal solution. If you're looking for a "good" solution then clustering algorithms would be of some value if you were talking about more points.

For fifteen points, there's no reason not to find an exact solution by brute force. The algorithm that Alvaro proposes upthread will work, I think, if you modify it to be aware of the constraint that it can't return a circle that intersects the bounding circle. There are cases in which the circle that it would return without that constraint contains more points than the one it will return with it.

Anyway I say "I think" in the above because for the algorithm to return an optimal circle it is required that there is always a 0.5r radius circle that passes through two points and contains the maximum possible number of points. I can't think of a counter-example to this, but I also can't prove that it is true.

Share this post


Link to post
Share on other sites
I'm after a "good enough" solution -- meaning that I want the inner circle containing a maximum number of points (recognizing that there may be more than one), but it doesn't need to be a minimum bounding circle around the points.

I'll try the brute force approach using alvaro's proposed algorithm and add a check whether the center of the larger circle is bounded by the smaller circles. This seems like a straightforward way to ensure that the smaller circle lies within the larger circle. Thanks, alvaro, for the algorithm and thanks to all other contributors. I'll keep monitoring the thread in case anyone else cares to pitch an alternative idea.

Share this post


Link to post
Share on other sites
In the problem as I originally understood it, I am certain that an optimal circle exists that contains two on its border. Just consider any optimal circle and move it a little bit, until one of the points inside touches the border. Then pivot around that point until another point touches the border. No points have gone in or out of the circle as I moved it, so the new circle is also optimal, and it contains two points in its border. So it is safe to just search among circles with that property.

With the additional constraint of the smaller circle being contained int the larger one, I think it should be enough to check circles that contain two points and are contained in the larger circle, plus circles that contain one point and are tangent to the large circle. I think a similar argument to the one above justifies this, but it's really late and I might not be thinking straight. I'll think about it some more tomorrow.

Share this post


Link to post
Share on other sites
This is a very nice problem and alvaro is right.

You start off with an optimal circle. Since the bounding circle is of radius r and the optimal circle is of radius 0.5r, you can always move the optimal circle around inside the bounding circle until you touch one other point*. If you touch several points, pick a random one. Rotate the circle around that point until you a) touch another point or b) touch the bounding circle. The circle you end up with either touches 2 points or 1 point and the bounding circle. It is still optimal since no point left the circle.

Hence, the algorithm works as follows:
1) For every pair of points A and B closer than r, check the two circles through A and B. Ignore circles not inside the bounding circle.
2) For every point whose distance to the bounding circle is smaller than 0.5*r, check the two circles through that point tangent to the bounding circle.
Still O(n^3). Part 2) is even O(n^2).

*To see this, imagine the diameter through the centers of the two circles. Move the optimal circle along this diameter all the way to one side until it touches the bounding circle, then all the way to the other side until it touches the other side of the bounding circle. Since the radius of the circle you moved is 0.5*r and the radius of the bounding circle is r, the two extreme circles don't overlap - their intersection is empty. But since there was at least one point in the optimal circle, you must have "lost" at least one point while moving the optimal circle around.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!