Fastest way to get all the points within a certain range

Question

I'm trying to figure out what's the fastest way to retrieve all the points/coordinates that are surrounding a given coordinate within a certain range in a 2D array.

I'm currently looping through the X/Y and adding all the points to a list but it turns out to be very slow when the range starts getting increased. Is there any other way of achieving this more efficiently than how I'm currently doing it?

My current code:

public static List<coords> GetCoordinates(coords Position, int nRange)
    {
        List<coords> inRange = new List<coords>();
        for (int i = Position.X - nRange; i <= Position.X + nRange; i++)
            for (int j = Position.Y - nRange; j <= Position.Y + nRange; j++)
                inRange.Add(new coords() { X = i, Y = j });
        return inRange;
    }

The fastest way is not to list all the points, and if you need to calculate if something is the range, just use some `if` statements. Depending on the problem you are trying to solve — TheGeneral, Jun 12 '19 at 03:44
It's an `O(n^2)` algorithm, it is expected to be slow for large n. Why do you need to do this? Maybe the original problem can be solved in a different way. — seg, Jun 12 '19 at 03:49
Right, without context it's difficult to say, but chances are you would be better served by leveraging a library that would already have some optimized methods for you to use. e.g. if you're working with GeoJSONs then use GeoJSON.Net.Contrib.MsSqlSpatial which comes with methods for seeing if points/2d areas intersect with others, etc. — Mark Z., Jun 12 '19 at 03:55
This function is called in 3-4 different situations but in all of them the points retrieved will be subject to some `if` statements to see which of them is still available after those checks. Example, person A is at coordinate x,y and he wants to jump to a different coordinate within a range of 3 that doesn't have anyone in it already. I get the list of all the coordinates within the given range and then remove the coordinates that already contain someone in it and finally pick a **random** coordinate of those that's still left in the list. — Noobzilla, Jun 12 '19 at 04:25
I still think you are doing things backwards and slower, if you have a list of people in a range, enumerate them when you need it, and do a range check using your position. — TheGeneral, Jun 12 '19 at 04:35
Agree with TheGeneral, you don't need to create a list of all coordinates in order to do this, just pick random x and y within the range until you find an empty spot. — seg, Jun 12 '19 at 05:36

score 3 · Answer 1 · answered Jun 12 '19 at 05:59

1st step: Capitalize your variables correctly. You'll get a 50% speed boost by pascal-casing your classes, and camel-casing your parameters:

public static List<Coords> GetCoordinates(Coords position, int range)

OK, I lied about the execution speed boost, but the readability boost is real.

2nd step: Ensure that Coords is a struct, to remove pressure from the garbage collector:

public struct Coords { public int X; public int Y; }

3nd step: Preallocate the space required for the List<Coords>, to avoid multiple resizings of the internal array.

var inRange = new List<Coords>((range * 2 + 1) ^ 2);

Alternatively don't preallocate anything and return an iterator instead of a list:

public static IEnumerable<Coords> GetCoordinates(Coords position, int range)
{
    for (int i = position.X - range; i <= position.X + range; i++)
        for (int j = position.Y - range; j <= position.Y + range; j++)
            yield return new Coords() { X = i, Y = j };
}

Another approach would be to return a random Coords within range, that satisfies a condition:

public static Random _random = new Random();
public static Coords GetRandomCoordinates(Coords position, int range,
    Func<Coords, bool> condition)
{
    while (true)
    {
        var coords = new Coords()
        {
            X = _random.Next(position.X - range, position.X + range + 1),
            Y = _random.Next(position.Y - range, position.Y + range + 1)
        };
        if (condition(coords)) return coords;
    }
}

...and use it like this:

var result = GetRandomCoordinates(position, range,
    (coords) => !players.Any(player => player.X == coords.X && player.Y == coords.Y));

This is microoptimizations, likely there's a completely different way to go about this that would yield MUCH better results, such as K-D tree structures, cover trees, R-trees, etc. that organize the coordinates better than just a linear list. — Lasse V. Karlsen, Jun 12 '19 at 07:08
@LasseVågsætherKarlsen agreed. But I guess that OP's intention is to speed up his program without sacrificing the simplicity of his design. — Theodor Zoulias, Jun 12 '19 at 07:23

shingo · Answer 2 · 2019-06-12T06:20:25.830

If you've already known the total size, use a fixed array is much faster

int width = nRange + nRange + 1;
coords[] inRange = new coords[width * width];

And cache the end value for the for loop

int endX = Position.X + nRange;
int endY = Position.Y + nRange;
for (int i = Position.X - nRange; i <= endX; i++)
     for (int j = Position.Y - nRange; j <= endY; j++)

Benchmark

coords is class

 nRange          |           1000               |           5000            
-----------------+------------------------------+---------------------------
 Method          |   List           Array       | List          Array       
-----------------+------------------------------+---------------------------
 AVG(ms)         |   312.90858      254.00218   | 8201.48866    7634.8847   
 MAX             |   321.8542       259.0914    | 8498.696      7914.6034   
 MIN             |   300.2323       248.8317    | 7908.7473     7529.3754   
 STDEV           |   9.564255412    3.654335875 | 220.2477895   159.5085045

coords is struct

 nRange          |            1000              |           5000               
-----------------+------------------------------+------------------------------
 Method          |   List           Array       |  List            Array       
-----------------+------------------------------+------------------------------
 AVG(ms)         |   56.68224       14.2345     |  1454.1773       296.05854   
 MAX             |   57.3408        15.4369     |  1472.1977       298.0693    
 MIN             |   56.2184        12.752      |  1444.9573       293.7728    
 STDEV           |   0.468124121    1.081463106 |  10.57876523     1.925248377

This is not entirely true, a list uses an array internally, [which doubles in size each time it is full](https://stackoverflow.com/questions/14913640/which-algorithm-is-used-in-listt-to-dynamically-allocate-memory), therefore appending [can be seen as an `O(1)` operation](https://stackoverflow.com/questions/41155209/resizable-array-and-amortized-runtime). While your approach will be faster, the difference for large n is minimal. — seg, Jun 12 '19 at 04:04
@tmlye, I do some benchmark and the conclusion is if coords is struct, use array is more than 70% faster, I can say it's a large improvement. — shingo, Jun 12 '19 at 06:30
sorry, I didn't realise coords is a struct. Thank you for doing the benchmarks! — seg, Jun 13 '19 at 01:18

Fastest way to get all the points within a certain range

2 Answers2