Finding a (Buffon’s) needle in a hierarchical triangular haystack

Ashton Shortridge

NCGIA, Department of Geography
University of California
Santa Barbara, California

Email: ashton@geog.ucsb.edu

Link to full paper

This paper develops a method for determining the probability for a line to intersect an equilateral triangular tile. Such tiles comprise global data structures like the quaternary triangular mesh (QTM), and such intersections are fundamental spatial operations. Knowledge of the probability of intersection has implications for the analysis of data stored in global data structures.

There are a number of ways in which the surface earth can be decomposed into a set of finite elements. One method, termed the quaternary triangular mesh, begins by projecting the earth on to an octahedron. Each facet of the octahedron is an equilateral triangle; level 0 in the hierarchy is the set of eight facets. Each triangle can be subdivided into four equilateral triangles by connecting the center points of each side; these triangles comprise level 2. Any triangle within this system can be recursively decomposed to increasingly higher (finer) level levels in the hierarchy.

The quaternary triangular mesh has several advantages as a method of structuring global spatial information. Triangles at higher levels nest congruently within coarser, lower level triangles. Data structure density may vary with data density, since the number of levels can be extended in data-rich locations. The level of a triangle is implicit in its index number, making it straightforward to determine the precision of the data. Efficient spatial operators have been developed for the QTM, making it a useful structure for very large data sets.

Intersection is a fundamental operation for any spatial data structure. Usually intersection is calculated deterministically, since feature locations are typically known prior to performing the operation. However, there is utility in knowing the probability of intersection without reference to feature-specific locations. Buffon's Needle-type solutions from the field of geometric probability provide a framework for deriving probabilities for a number of common GIS intersections, including line-line, line-square, and line-rectangle. Knowledge of intersection probabilities may be valuable for applications involving global QTMs, including estimating complexity and time required to process a distance operation and identifying optimal resolutions in the hierarchy for specific operations.

This paper reports on the extension of Buffon’s Needle to the equilateral triangle case. More formally, consider the earth’s surface modeled as a quaternary triangular mesh at some level n. This surface consists entirely of a repeatable pattern of nested equilateral triangular tiles, such that all locations fall in one and only one tile. A needle -- a line segment of length l -- is dropped randomly onto the surface. What is the probability that the needle intersects a tile boundary? The solution for this problem is presented and its utility is discussed.