- Home /
(Scripting) Getting a circle of points in an array
Lets say you have a double array of any data type. You are given an x and y value, that represents a single value in this array, such as map[x,y]. Now, you want to do something to not only that point in the array, but to the points around in it in a circle.
There are several way I have achieved this, but none as quite good enough. The first method was to just loop through every value in the array and check if its distance from the center point was lower than a given value, if so, it was in the circle. However, the scale of the array that this is in is around 500x500, and I'd like to make that even bigger if I can. The issue is that 500x500 is 250,000. Looping through that and applying functions is death to my game, but has to be done somehow.
I have created a better method that runs only through the local points, by basically looping through a small square of width and height same as the diameter of the circle, which is 999x faster than before. Ex:
void Circle(int x, int y, int radius)
{
Vector2 center = new Vector2(x,y);
for (int i = x-radius; i < x+radius; i++)
{
for (int j = y-radius; j < y+radius; j++)
{
if (Vector2.Distance(center, new Vector2(i,j)) <= radius)
{
//Do Stuff
}
}
}
}
This will be done a lot, so even little improvements make a big difference. What I'm looking for is a way that doesn't loop through a square and compare distances, but instead produces all points in the circle directly. I'm not sure how it would be done, but I think it might be possible, and then would likely be more efficient.
Thank you so much. It's code worked for me. I've been doing it for a while. You saved my life :))
Answer by Bunny83 · Dec 01, 2016 at 04:55 PM
Well, if the radius is constant you can in deed create a list of all points that make up a circle since your center is made up by a whole number. It would be best to create an int version of a 2d vector:
public struct Vector2i
{
public int x;
public int y;
public Vector2i(int aX, int aY)
{
x = aX; y = aY;
}
}
Now just use a generic list and prepare your points:
List<Vector2i> offsets = new List<Vector2i>();
int threshold = radius * radius;
for (int i = -radius; i < radius; i++)
{
for (int j = -radius; j < radius; j++)
{
if (i*i + j*j <threshold)
offsets.Add(new Vector2i(i,j));
}
}
Btw: since each quadrant of a circle is equal, just flipped on x, y or both axis you could even do:
offsets.Add(new Vector3i(0,0));
for (int i = 1; i < radius; i++)
{
for (int j = 1; j < radius; j++)
{
if (i*i + j*j <threshold)
{
offsets.Add(new Vector2i(i,j));
offsets.Add(new Vector2i(-i,j));
offsets.Add(new Vector2i(i,-j));
offsets.Add(new Vector2i(-i,-j));
}
}
}
Though there shouldn't be much difference. The best performance gain is to avoid unnecessary method calls inside your loops. If you can you should inline as much as possible. That's best to avoid cachemisses. For that matter of fact it might even be faster to do:
offsets.Add(new Vector3i(0,0));
Vector2i vec = new Vector2i();
for (int i = 1; i < radius; i++)
{
vec.x = i;
for (int j = 1; j < radius; j++)
{
if (i*i + j*j <threshold)
{
vec.y = j;
offsets.Add(vec); vec.x = -vec.x; // i,j
offsets.Add(vec); vec.y = -vec.y; // -i,j
offsets.Add(vec); vec.x = -vec.x; // -i,-j
offsets.Add(vec); // i,-j
}
}
}
Though since you do this only once and then use the offsets list directly that shouldn't make a huge difference ^^.
Ins$$anonymous$$d of storing all points in the list you could also use "scanlines" by deter$$anonymous$$e the lowest and highest index for each row and only store those in a list. So the list would only contain as many elements as you have rows. For each row you can now use a nested for loop and use the $$anonymous$$ / max values for the range in the x-direction. But i doubt that would make any difference and is just more complicated to setup and use.
Thanks, but is this like your job or something? I see you all the time on here
Your answer
Follow this Question
Related Questions
Multiple Cars not working 1 Answer
Distribute terrain in zones 3 Answers
witch approach for an car race curve 1 Answer
Trouble with adding value using FieldInfo.SetValue(this, int + int) 1 Answer