Trixel buffer logic for I/O bound point in N-polygon inclusion tests of massive bathymetric data
João Fradinho Oliveira, Marek K. Ziebart, J. C. Iliffe, James F. Turner, Stuart Robson · Digital Library (University of West Bohemia) · 2013
Trixel Buffers is a new spatial data-structure for fast point in multiple polygon inclusion queries. The algorithm utilizes a pre-processing step in which the inside/outside status of a quadtree's leaf triangles without polygon geometry is pre-computed automatically; at run-time point queries lying within these triangles simply inherit their inclusion status. If a point query lies in a leaf triangle enclosing polygon vertices or crossing edges, a ray is fired from the point towards the triangle center whose polygon inclusion properties has also been pre-computed: rules are then applied to the intersection count and center-point properties to infer the polygon inclusion status. Our main contribution is that rays need not be followed until the polygon limits, and consequently the algorithm is I/O bound with shallow trees. It took 1h36m rather than days of using a standard ray test to determine the multiple polygon (~270,000 line segments) inclusion of 1.75 billion points on a 2.5GHz DuoCore computer.