CODEWITHSUNDEEP
arraysalgorithmparticles
hayk
hayk

Reputation: 468

Finding particles in the same cell on a 2d grid

It's a sort of an algorithmic question, without a bond to any of the particular languages.

Let's say I have Np point particles with continuous (read double) x, y coordinates on a 2d plane. The 2d plane is divided into N ⨉ N cells.

For each particle I want a quick way (faster than O(Np^2)) to find other particles in the same cell. Also, I don't want to go too far in memory usage, so I don't want another N ⨉ N + Np array to store.

I "invented" a tricky way to realize this, but I'm asking this question just in case there's a canonical way of doing this.

Upvotes: 2

Views: 219

Answers (4)

Ivan Gritsenko
Ivan Gritsenko

Reputation: 4236

Here is a solution with O(Np * log(Np)) time and O(Np) memory:

Initialize a dynamic DS container with {row,col} tuple as a key \
    and a list of particles as a value
Iterate over each particle
    Find {row, col} tuple for current particle
    Find a value-list in container by {row, col} key
    If there is no value in container for a value by this key
        Then initialise a new particle list
    Append current particle to a value-list

Container may be implemented as a balanced binary tree, which will give log(Np) multiplier to overall time complexity.

Another way to solve with O(Np + N) time and O(N) memory solution:

Initialize a simple lookup array byRow of size N, \
    it will contain a list of particles in each cell
Iterate over each particle
    Place the particle in corresponding cell of lookup array byRow by its ROW
Initialize another lookup array byCol of size N, \
    it will contain a list of particles in each cell as well
Iterate over each cell of lookup list byRow 
    Iterate over each particle of the list in byRow[cellRow]
        Place the particle in corresponding cell of byCol by its COL
    Iterate over each particle of the list in byRow[cellRow]
        \\ Now you have a list of other particles in the same NxN cell
        \\ by looking at byCol[particleCol]
        If byCol[particleCol] is not cleared
            Print byCol[particleCol] list or put into other global storage and use later \
        Clear byCol[particleCol] list

The idea is very simple. First you group particles by row storing them in lists of byRow array. Then for particles of every list of byRow array you make the same grouping by column. Each time you are reusing byCol array. So overall memory complexity is O(N). Even we have two loops nested one in other we still have O(Np + N) time complexity because no inner step will be executed more than Np times.

Edit: Time complexity is O(Np + N) to be precise.

Upvotes: 1

yuri kilochek
yuri kilochek

Reputation: 13486

The canonical way to do this is to use a spatial indexing data structure, e.g. a kd-tree, with O(Np*log(Np)) construction time, O(Np^(1−1/K)+Mp) axis-aligned range (which is your cell) query time (K=2 dimensions, Mp points reported), O(Np) space.

Upvotes: 1

Malcolm McLean
Malcolm McLean

Reputation: 6404

There's no real answer other than to have a list of particles attached to each cell. Which is another N x N + p data structure. However memory is cheap and you should be able to afford it.

Upvotes: 0

snow_abstraction
snow_abstraction

Reputation: 452

Construct a list (or array) of sorted tuples of (used cell id, a list of particles in that cell) sorted by the cell id. The cell id could just be its (x, y) coordinates. The space complexity is O(Np). Constructing it should take O(Np log(Np)) time. Looking up the particles in the same cell is then O(log(Np)) via standard binary search.

To replace log(Np) by 1 in these complexity estimates to get O(Np) construction time and O(1) look-up, replace the sorted list with a hash table.

Upvotes: 0

Related Questions