4.11.3. Spatial Bins
[4.11. Geometric Paths]

Spatial queries are commonly performed upon dynamic particle paths. An example would be to report all particles that end within a specific bounding box or polygon. This can easily be determined by looking at the particle locations on the final timestep. More difficult however, are queries such as find all particles that pass through a specific polygon at any time. This type of a query would require looking at every particle location for every timesteps. This process can be sped up considerably by storing some extra data.

Because we want to take advantage of HDF5 functionality only supported when working with C and the XMS programs will be doing the queries, the spatial bins functionality will only be available in the C version of the library.

The proposed methodology is to divide the domain into a regular grid of spatial bins, and for each bin store the particles that travel through it and for each particle the timestep indices where the particle enters and leaves the bin. These indices would actually be the timestep before entering the bin and the timestep after leaving the bin so that reading these timestep indices for the particles will have all the segments that pass through any part of the bin. Since a particle may enter and leave a bin several times, there will be a variable number of pairs of entering/exiting timesteps.

This additional information will make it very efficient to perform spatial queries on the particles. At least initially this information will have to be computed outside of XMDF but can be stored and queried here. The advantage of saving this data back to the file is that it can be computed once and used many times over. The extra data is not stored in RAM.

Current implementation will only build 2D bins. This will be expanded to 3D bins if necessary. Three dimensional bins consume enough memory to delay their implementation if possible.

The minimum and maximum values for the grid (which should correspond to the minimum and maximum values for the particle paths), are used to define the bins.

Particles on the boundary of bins should have entries placed in the bins on both sides of the boundary. Likewise particles on a corner should have entries for all bins touching the corner.

A bin may reference a particle even if none of the timestep values are in a cell. This would happen if the straight line path between successive timesteps crosses over the cell.

RDJ - Add function prototypes to store/retrieve timesteps where particles enter/leave a bin.

C/C++

int xfDefineGrid(xid PartGroup, int nXBin, int nYBins, int *nPointsInBin, 
                 int **PointsInBin)
int xfWriteParticleBins(xid PartGroup, int nTimesteps, int *BinsTraversed)

FORTRAN

I'll get the C versions working then update the FORTRAN design in case changes need to be made...

Reading

These functions are used to read the spatial bins for making spatial inquiries on the geometric path group. In every case, the memory should already be allocated before calling the functions.

C/C++

int xfIsSpatialGridDefined(xid PartGroup, xbool *bDefined)
int xfGetNumCellsInXandY(xid PartGroup, int *nXCells, int *nYCells)
 
int xfGetNumParticlesInBin(xid PartGroup, int Bin, int *nParticles)
int xfGetParticlesInBin(xid PartGroup, int Bin, int nParticles,int *PartIndicies)
 
int xfReadBinsParticleVisits(xid PartGroup, int PartIndex, int nTimesteps,
                             int *BinsTraversed)

FORTRAN

I'll get the C versions working then update the FORTRAN design in case changes need to be made...