Alternative indexing methods for point set operations

Question

It is common to use a bounding box spatial index to improve performance when working with a large number of features. Where operations are performed against individual geometries with a large number of vertices do any similar optimization strategies exist?

For example, do any data structures exist that can speed up point in polygon, or union operations?

Answer 1

OK for Point in Polygon only:

I think the problem is based on the "fractal nature" of 2d objects and the uncertain and unbalanced distribution of spatial information. If you have an regular grid, it is easy to calc a position or relation of a cell. But an isoline of a terrain model may have uncomplicated parts at on side and mathmatically complicated ones on the other side (morphologically active parts lke ridges, valleys...).

Indexing tries to handle two things:

1. A fast routine that gives you a set buckets in which you collect objects that you can spatially distiguish (the buckets!). And BBoxes are easy to calculate and to handle.

2. A set of relations (overlap, touch) to distinguish or relate the spatial stuff (the objects).

Unfortunally will BBoxes give you no clue, how many points are in each BBox, how the objects are shaped (holes, convex, ...) and how the info is locally distributed (90% of the points in the upper left corner of the BBox). So you may find fast operation members on the object level and loose many time in the relation building of the test.

To use a more irregular approach, IMO triangulation in combination with and quadtrees is on of the strategies, where you can bring the bucketing and the relation building part of an index closer together (bucketing == relation building).

For the Point-in-Polygon-Test example it is possible to build an irregular cache by using:

1. !constrained delaunay triangulation of your poly cover, with additional border mesh points for outside-of-the cover detection
2. put this into quadtree indexing scheme with not more than N triangles per box (fractal buckets)
3. find the triangle set which the point belongs to - the leaf in the quadtree
4. find the triangle in which the point lies (the test part over max. N triangles)
5. and ask for the polygon ID's of the triangle vertices
6. if the ID is unique the point belongs to the polygon, if not it is outside

The cost to build the tin and the quadtrees are very high and difficult to calculate and the quadtree has to balance large and small triangles (triangles that will not fit in smaller subtree boxes).

Some Tools and Links:

Triangle - Constraint polygon triangulation

Quadtrees - With source examples

Stony Brook Repository - Data structures and diskrete geometry