I guess the first stage of this process is to provide an efficient way of checking how close each particle is to the others in order to know if it forms part of a cluster.
This can be done by comparing each particle with all the others and measuring their distance of separation. However, this would be a very inefficient O(n
2) process and since your scenario involves dynamically changing particles, this would be impractically slow for more than a few 10s of particles.
Much better would be to use some kind of spatial indexing method that sorts your particles into groups before measuring distances. That way, only a subset of particle pairs need be compared during each iteration. There are many hundreds of spatial indexing methods available, some of which are quite complicated.
A relatively simple and effective one for the task you have would be to create a
HashGrid that superimposes a coarse grid over your particles. When measuring distances between particles, only those in the same coarse grid cell need be compared. An example Processing class to represent a hash grid is given below:
Quote:
// Divides a set of 2d spatial objects into a coarser grid for efficient spatial indexing.
// V1.1 Jo Wood, 17th June, 2008.
class HashGrid
{
// ------ Object variables ------
int numRows,numCols;
float maxX,maxY;
HashMap hm;
// Creates a grid capable of storing items located within (0,0) to (maxX,maxY).
// numRows and numCols determines the resoluton of the coarse grid.
HashGrid(float maxX, float maxY, int numCols, int numRows)
{
this.maxX = maxX;
this.maxY = maxY;
this.numCols = numCols;
this.numRows = numRows;
hm = new HashMap();
}
// Add an object at the given coorindates to the grid.
void add(Object obj, float x, float y)
{
// Put the same object in the centre and up to 2 of the 4 adjacent grid cells to
// avoid boundary problems.
float halfGridX = maxX/(numCols*2);
float halfGridY = maxY/(numRows*2);
addToGrid(obj,x+halfGridX,y);
addToGrid(obj,x-halfGridX,y);
addToGrid(obj,x,y+halfGridY);
addToGrid(obj,x,y-halfGridY);
}
// Private version of the add() method that does not add object to neighbouring grid cells.
private void addToGrid(Object obj, float x, float y)
{
if ((x < 0) || (y < 0) || (x>maxX) || (y > maxY))
{
// Do nothing when out of bounds.
return;
}
int coordHash = getCoordHash(x,y);
Vector objects = (Vector)hm.get(coordHash);
if (objects == null)
{
// Nothing currently stored in this grid cell.
objects = new Vector();
}
// Update list of objects stored in this grid cell.
objects.add(obj);
hm.put(coordHash,objects);
}
// Returns a list of objects that share the same grid cell as the one
// in which the given coordinates lie.
Vector get(float x, float y)
{
int coordHash = getCoordHash(x,y);
return (Vector)hm.get(coordHash);
}
// Clears out the contents of the grid.
void clear()
{
hm.clear();
}
// Calculates the hash of the grid cell in which the given coordinates lie.
private int getCoordHash(float x, float y)
{
// Bin coordinates into coarse (col,row) grid.
int col = round((numCols-1)*x/maxX);
int row = round((numRows-1)*y/maxY);
// Convert (col,row) coordinate into single unique hash number.
return row*numCols + col;
}
}
You can see an
example Processing sketch (with source) to allow 1000 Ants to wander around, turning red when they are close to other ants. There is plenty of scope to further optimise this class, but it should give you a start.
Pages: 1
particle grouping (Read 761 times)