ID:155900
 
So I have been trying to figure this out and I haven't seen anything directly related to this in the forum-a lot of things that are close but not quite.

I am trying to create a proc that given a x,y value and a radius, it will return a list of all the coordinates within the circle (not just a ring but a filled circle). I can't use range or view because this does not apply to turfs. It is more of an abstraction using an array set up as array[x][y].

If anyone has any ideas or if I missed anything in the forum let me know.

I have tried adapting something I used in my graph program using polar coordinates:
Gr_Polar(var/radius as num, var/ang as num)
var/py = radius*sin(ang)
var/px = radius*cos(ang)
return list[px][py] //this is a global list


But this doesn't really give the best results since I have to round it which creates off center shapes.

If it is any help, I probably wont have a radius greater than 4.


The outline of a circle is the set of all points that are of distance R from its center, R being the radius. Any point with distance <R would be inside the circle.
In response to Toadfish (#1)
To expand on what Toadfish said, you can start by looping through all of the tiles within a square of the same radius. In the loop, you calculate each tile's distance from the center, and if it's less than the radius, it's "inside" the circle.

An easy optimization you can do once you have it working is to compare the distance-squared to the radius-squared, avoiding the expensive sqrt() call.
In response to DarkCampainger (#2)
Ok, but that would require looping through the whole array. Is there anyway to do this without having to loop through the whole array?

I guess I could just create a list of positions within the radius of the array which would give me a square and then run the circle check to make the circle. That would cut down on some of the looping though the array.
In response to Asielen (#3)
The simple solution is to do what you've just suggested - run through every point in the array in the square of the radius of the circle and check if they're inside bounds. I suggest trying that first.

If that proves too slow, here are some thoughts on a faster version:

You can work out the points inside a circle by working out the minimum and maximum X values for each Y value in the circle (because you can then draw a line from the min to the max and know that all those points are in the circle). We know the minimum and maximum Y values, and this is a discrete problem, so we can reduce the problem to "For any given Y pixel value for the circle, find the min and max X values".

The equation for a circle is x**2 + y**2 = R**2, we're finding X from Y and R, so x = +/- sqrt(R**2 - y**2).

So:

proc/CircleCoords(var/c_x, var/c_y, var/r)
. = list()
var/r_sqr = r*r
var/x
var/y
var/i

for(y = -r, y <= r, y++)
x = round(sqrt(r_sqr - y*y))
for(i = -x, i <= x, i++)
. += list(list(i + c_x, y + c_y)) // Double-list is a hack to append a list to a list


I suppose scratch the try-the-slow-version-first advice, it's not actually that tricky, and now you've got a working proc. :P. It's semi-tested. You may want to experiment with rounding behaviour - at the moment it only accepts pixels that are completely within the circle. You can alter that by fiddling how the X value is rounded inside the loop - adding 0.5 to it inside the round, for example, will take any pixel that is half or more covered, and adding 1 inside the round will take any pixel that is even touched by the circle.

Hope that helps.

EDIT: Oh, and if that's /still/ not fast enough, you can probably eliminate the sqrt() via borrowing some ideas from the http://en.wikipedia.org/wiki/Midpoint_circle_algorithm .
In response to Jp (#4)
Thanks! I will try this out. I got the easy way working but it could be faster.