Finding all the points within a circle in 2D space
Solution 1
Will it serve my purpose?
For your 100x100, yes.
Can I make it faster?
Yes. For example, you can:
- Check only 1 quadrant and get other points because of symmetry.
- Skip the square root when calculating the distance.
Code:
for (x = xCenter - radius ; x <= xCenter; x++)
{
for (y = yCenter - radius ; y <= yCenter; y++)
{
// we don't have to take the square root, it's slow
if ((x - xCenter)*(x - xCenter) + (y - yCenter)*(y - yCenter) <= r*r)
{
xSym = xCenter - (x - xCenter);
ySym = yCenter - (y - yCenter);
// (x, y), (x, ySym), (xSym , y), (xSym, ySym) are in the circle
}
}
}
That's about 4x speed up.
JS tests for solutions presented here. Symmetry is the fastest on my computer. Trigonometry presented by Niet the Dark Absol is very clever, but it involves expensive mathematical functions like sin
and acos
, which have a negative impact on performance.
Solution 2
You can bypass the need for a conditional check:
for(x=center-radius; x<center+radius; x++) {
yspan = radius*sin(acos((center-x)/radius));
for(y=center-yspan; y<center+yspan; y++) {
// (x,y) is inside the circle
}
}
If needed, you can round(yspan)
.
Solution 3
You can get speed ups by computing as much outside of the loops as possible. Also there's no need to do the Pythagoras Theorem square root... just keep everything squared. One final speed-up can be made by only doing the math for one quarter of the circle (because it's symmetrical)... when a match is found you just replicate it for the other three quarters.
radiusSquared = radius*radius;
rightEdge = centerX+radius;
bottomEdge = centerY+radius;
for(x = centerX; x <= rightEdge; x++){
xSquared = x*x;
for(y = centerY; y <= bottomEdge; y++){
ySquared = y*y;
distSquared = xSquared+ySquared;
if(distSquared <= radiusSquared){
// Get positions for the other quadrants.
otherX = centerX-(x-centerX);
otherY = centerY-(y-centerY);
// Do something for all four quadrants.
doSomething(x, y);
doSomething(x, otherY);
doSomething(otherX, y);
doSomething(otherX, otherY);
}
}
}
Solution 4
For getting a list of all points within a circle you should use:
var radius = 100, r2 = radius * radius;
var circle = [];
for (var dx = -radius; dx <= radius; dx++) {
var h = Math.sqrt(r2 - dx * dx) | 0;
for (var dy = -h; dy <= h; dy++) {
circle.push([dx, dy])
}
}
See http://jsperf.com/circles/2 for profiling against the other solutions here.
Related videos on Youtube
Comments
-
Kraken over 1 year
I am representing my 2D space (consider a window), where each pixel is shown as a cell in a 2D array. i.e. a 100x100 window is represented by the array of same dimensions.
Now given a point in the window, if I draw a circle of radius
r
, I want to find all the points lying in that circle.I was thinking I'd check for the each point in the square region around the radius, with
side = 2*r
, if it lies in the circle or not. I'll use the normal distance formula maybe?Hence, maybe the following:
for (x=center-radius ; x<center+radius ; x++){ for (y=center-radius ; y<center+radius; y++) { if (inside) { // Do something } } }
Will it serve my purpose? Can I make it faster?
-
Niet the Dark Absol about 11 yearsMy solution's more than an order of magnitude faster ;)
-
BlackBox about 11 yearsMy code was under the impression he had to do it in fewest possible characters cough :D
-
Kraken about 11 yearsYou say for 100X100 it works. Will it not work for some other dimension?
-
Adam Stelmaszczyk about 11 yearsIt will always work. The question is, how fast. In dimension d=2 it's O(r^2), where r is radius. In d=3 it's O(r^3), we are looking for points in a sphere. Generally it's O(r^d). Your question was "will it serve my purpose", which I understand as "will it run so quickly that I will not feel it". I said yes, because for r = 100 and d = 2 on modern computers, even in JS, time will not be noticeable. However, for bigger r or d the time will be noticeable.
-
Kraken about 11 yearsOhh sorry, I meant if the dimension 100X100 was something else, i.e. 500X300 or anything.
-
Adam Stelmaszczyk about 11 yearsYes, it will work. The speed is indifferent to the size of grid. What matters is the size of radius. Algorithm's complexity is O(r^d). Only r (radius) and d (dimension) matters.
-
Admin almost 10 yearsAs an ES6 array comprehension
[ /* (x, y) (-x, -y) are in circle */ for (x of r) for (y of r) if ((x - center)*(x - center) + (y - center)*(y - center) < rad*rad)];
Try it in FF -
aze45sq6d about 6 yearsI assume, if you have diff coords for x-center and y-center that it changes to first for loop: center = xcenter, yspan: center = xcenter and second for loop center = ycenter?
-
Niet the Dark Absol about 6 yearsYup. You can even use a different
radius
in thefor
and thesin
to get an ellipse. -
Niet the Dark Absol over 5 years@ChandrapalSinghJhala See my comment directly above yours.
-
Sairam over 3 yearsThis didn't work for me and the performance went bad.
-
Qumber about 3 yearsJS Test link returns
500
.