org.jzy3d.plot3d.builder.delaunay.jdt
Class GridIndex

java.lang.Object
  org.jzy3d.plot3d.builder.delaunay.jdt.GridIndex

public class GridIndex
extends java.lang.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

GridIndex(Delaunay_Triangulation delaunay, int xCellCount, int yCellCount)
Constructs a grid index holding the triangles of a delaunay triangulation.

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

Method Summary

Triangle_dt	findCellTriangleOf(Point_dt point) Finds a triangle near the given point
void	updateIndex(java.util.Iterator<Triangle_dt> updatedTriangles) Updates the grid index to reflect changes to the triangulation.

Methods inherited from class java.lang.Object

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

Constructor Detail

GridIndex

public GridIndex(Delaunay_Triangulation 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(Delaunay_Triangulation 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_dt findCellTriangleOf(Point_dt 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(java.util.Iterator<Triangle_dt> 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.