Sign in to follow this  
kirby900

circle containing greatest number of points

Recommended Posts

kirby900    102
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
alvaro    21263
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
kirby900    102
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
Atrix256    539
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
kirby900    102
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
Antheus    2409
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
jwezorek    2663
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
kirby900    102
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
alvaro    21263
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
Lutz    462
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
Lutz    462
Quote:
Original post by irreversible
One thing you might consider as a speed optimization is substituting the actual distance calculation with a less accurate heuristic, such as Carmack's inverse or the Manhattan distance metric. To be accurate, you'd still need to calculate the actual Euclidean distance if the result is inconclusive.

You never have to take the sqrt, you can always stay squared:
sqrt((x1-x2)^2 + (y1-y2)^2) < 0.5*r   <==>   (x1-x2)^2 + (y1-y2)^2 < 0.25 * r^2
Apart from that, I was always wondering whether there's still a point in Carmack's inverse today. That method was apparently developed in the early 1990 and used in Quake 3 in 1999, but that's more than 10 years ago. Today, FPUs are much more optimized and I'm wondering whether you don't loose more cycles tinkering with the imprecisions of the method than you actually win. Anyone tested this? Today, memory access and cache coherence is the real bottleneck in most apps.

Share this post


Link to post
Share on other sites
taz0010    277
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.

Share this post


Link to post
Share on other sites
alvaro    21263
Quote:
Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.

There's a SSE instruction that computes an approximated reciprocal of the square root (see rsqrtps). This probably means that Carmack's trick is now implemented in hardware.

Share this post


Link to post
Share on other sites
djz    215
Quote:
Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.


I use distance calc extensively in my Boids simulator and profiled the Carmack trick, this one and the regular calculation. The 'optimizations' were actually slower than just running the distance calc.

Share this post


Link to post
Share on other sites
kirby900    102
As a newbie to gamedev.net, I'm delighted that see that postings receive such interest and attention. Something tells me I'm gonna like it here. :-)

Share this post


Link to post
Share on other sites
cache_hit    614
Quote:
Original post by alvaro
Quote:
Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.

There's a SSE instruction that computes an approximated reciprocal of the square root (see rsqrtps). This probably means that Carmack's trick is now implemented in hardware.


With the only catch being that it isn't actually Carmack's ;-) It's only famous because of him, but it's not actually his.

Share this post


Link to post
Share on other sites
alvaro    21263
Quote:
Original post by cache_hit
Quote:
Original post by alvaro
Quote:
Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.

There's a SSE instruction that computes an approximated reciprocal of the square root (see rsqrtps). This probably means that Carmack's trick is now implemented in hardware.


With the only catch being that it isn't actually Carmack's ;-) It's only famous because of him, but it's not actually his.


Oh, I know. I am referring to it as "Carmack's trick" because that's the name that was used elsewhere in the thread. Sorry I seem to have added to the myth that it's Carmack's code. There is a kinda inconclusive article about the origin of the code here, which leaves me without a good name for it. Any suggestions?

Share this post


Link to post
Share on other sites
Lutz    462
FWIW, I did a quick test and the fast inverse sqrt was indeed faster than 1/sqrt. Tested it on a quadcore 2 something MHz Intel.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this