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?

  • 1
    Under the hood, GISes use many specialized data structures, including various forms of quadtrees, DCELs, etc., which are described in computational geometry textbooks. Are you asking about these implementation details or are you inquiring about methods that might be employed by users within scripting languages?
    – whuber
    Jul 23 '12 at 13:03
  • Thanks, I think I need to read the textbooks. The point of my question was how those data structures can be pre-computed ahead of time. Do any pre-computed implementations exist? Jul 23 '12 at 13:46
  • Matthew, that's a great question. A truly performance-oriented GIS would offer options to users to precompute data structures for repeated application. As it stands, software advertising itself as "GIS" usually offers such precomputation only in the form of "spatial indexes" whereas more general-purpose software that can also do GIS analysis, such as Mathematica (or to some extent R) will offer the user far more control over such things.
    – whuber
    Jul 23 '12 at 14:14
  • I think the problem is based on the "fractal nature" of 2d objects and the uncertain and unbalanced distribution information density.
    – huckfinn
    Jan 29 '14 at 9:06

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.