il.ac.idc.jdt

Class GridIndex

java.lang.Object

il.ac.idc.jdt.GridIndex

public class GridIndex
extends Object

Created by IntelliJ IDEA. User: Aviad Segev Date: 22/11/2009 Time: 20:10:04 Grid Index is a simple spatial index for fast point/triangle location. The idea is to divide a predefined geographic extent into equal sized cell matrix (tiles). Every cell will be associated with a triangle which lies inside. Therfore, one can easily locate a triangle in close proximity of the required point by searching from the point's cell triangle. If the triangulation is more or less uniform and bound in space, this index is very effective, roughly recuing the searched triangles by square(xCellCount * yCellCount), as only the triangles inside the cell are searched. The index takes xCellCount * yCellCount capacity. While more cells allow faster searches, even a small grid is helpfull. This implementation holds the cells in a memory matrix, but such a grid can be easily mapped to a DB table or file where it is usually used for it's fullest. Note that the index is geographically bound - only the region given in the c'tor is indexed. Added Triangles outside the indexed region will cause rebuilding of the whole index. Since triangulation is mostly always used for static raster data, and usually is never updated outside the initial zone (only refininf existing triangles) this is never an issue in real life.

Constructor Summary

Constructors

Constructor and Description
GridIndex(DelaunayTriangulation delaunay, int xCellCount, int yCellCount) Constructs a grid index holding the triangles of a delaunay triangulation.
GridIndex(DelaunayTriangulation delaunay, int xCellCount, int yCellCount, BoundingBox region) Constructs a grid index holding the triangles of a delaunay triangulation.

Method Summary

Modifier and Type	Method and Description
Triangle	findCellTriangleOf(Point point) Finds a triangle near the given point
void	updateIndex(Iterator<Triangle> updatedTriangles) Updates the grid index to reflect changes to the triangulation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GridIndex

public GridIndex(DelaunayTriangulation delaunay,
                 int xCellCount,
                 int yCellCount)

Constructs a grid index holding the triangles of a delaunay triangulation. This version uses the bounding box of the triangulation as the region to index.

Parameters:

delaunay - delaunay triangulation to index

xCellCount - number of grid cells in a row

yCellCount - number of grid cells in a column

GridIndex

public GridIndex(DelaunayTriangulation delaunay,
                 int xCellCount,
                 int yCellCount,
                 BoundingBox region)

Constructs a grid index holding the triangles of a delaunay triangulation. The grid will be made of (xCellCount * yCellCount) cells. The smaller the cells the less triangles that fall in them, whuch means better indexing, but also more cells in the index, which mean more storage. The smaller the indexed region is, the smaller the cells can be and still maintain the same capacity, but adding geometries outside the initial region will invalidate the index !

Parameters:

delaunay - delaunay triangulation to index

xCellCount - number of grid cells in a row

yCellCount - number of grid cells in a column

region - geographic region to index

Method Detail

findCellTriangleOf

public Triangle findCellTriangleOf(Point point)

Finds a triangle near the given point

Parameters:

point - a query point

Returns:

a triangle at the same cell of the point

updateIndex

public void updateIndex(Iterator<Triangle> updatedTriangles)

Updates the grid index to reflect changes to the triangulation. Note that added triangles outside the indexed region will force to recompute the whole index with the enlarged region.

Parameters:

updatedTriangles - changed triangles of the triangulation. This may be added triangles, removed triangles or both. All that matter is that they cover the changed area.