Package il.ac.idc.jdt

Class 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 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.