PaperlayerView exact revision on arXiv

Source-linked AI summary

Indexing the Sphere with the Hierarchical Triangular Mesh

Alexander S. Szalay, Jim Gray, George Fekete, Peter Z. Kunszt, Peter Kukol, Ani Thakar

arXiv:cs/0701164v1cs.DBcs.DS

TL;DR

Spherical catalog queries can involve complex regions and costly computations. The paper presents a recursive triangular mesh index for spherical data and region covers, with performance reported as acceptable for astronomical databases containing several hundred million objects.

  • Problem

    Spherical catalog queries can involve complex regions that require complicated spherical trigonometry.

    Source: §1 · p. 2

  • Method

    The HTM recursively subdivides the sphere into triangular cells and maps points and region covers to hierarchical IDs and database ranges.

    Source: §2.3 · p. 5, §4.5 · p. 18

  • Results

    The algorithms' performance was acceptable in astronomical databases containing several hundred million objects.

    Source: §7 · p. 22

  • Takeaways & Limitations

    The HTM supports spherical partitioning and database range queries for datasets with inherent spherical locations.

    Source: §7 · p. 22

    For rare, complicated setups, the triangle classification may be wrong, and determining whether a triangle is outside may not justify the computational effort.

    Source: iii) Mixed Convexes · p. 17

Abstract

from arXiv · show

We describe a method to subdivide the surface of a sphere into spherical triangles of similar, but not identical, shapes and sizes. The Hierarchical Triangular Mesh (HTM) is a quad-tree that is particularly good at supporting searches at different resolutions, from arc seconds to hemispheres. The subdivision scheme is universal, providing the basis for addressing and for fast lookups. The HTM provides the basis for an efficient geospatial indexing scheme in relational databases where the data have an inherent location on either the celestial sphere or the Earth. The HTM index is superior to cartographical methods using coordinates with singularities at the poles. We also describe a way to specify surface regions that efficiently represent spherical query areas. This article presents the algorithms used to identify the HTM triangles covering such regions.

1. Introduction

Spherical catalogs require queries over complex regions, but common coordinate-based approaches make these computations difficult. The paper introduces a universal, recursive triangular index that supports cross-dataset identifiers and adapts subdivision to data density.

1. Introduction

  • Spherical catalog queries often constrain locations to complex regions that require complicated spherical trigonometry.The paper frames this as a challenge for science and commercial applications using spherical coordinates.Source: §1 · p. 2
  • The proposed index maps spherical regions to unique identifiers that can serve as area identifiers and indexing keys across datasets.Its comparisons replace transcendental functions with a few multiplications and additions.Source: §1 · p. 2
  • Recursive triangular subdivision keeps triangle areas roughly within a factor of two while allowing deeper subdivision in high-density regions.This supports organizing uneven distributions into equal-sized bins and avoids the pole singularities of usual spherical-coordinate projections.Source: §1 · p. 2
  • Related approaches include icosahedron-based meshes, equal-area Discrete Global Grids, and HTM implementations with different numbering schemes.The paper also situates its approach among work on quad trees, geometric indexing, and relational-database integration.Source: §1 · p. 2

2. The Hierarchical Triangular Mesh

The HTM recursively partitions the sphere into named spherical triangles, providing a spatial index whose trixels have bounded but nonidentical sizes. The section describes its construction, encoding, and geometric properties.

2.1. Using Cartesian Coordinates

  • Using 3D vectors and volumes containing surface regions avoids transcendental calculations in point-in-polygon tests, reducing them to arithmetic and comparison.Source: §2.1 · p. 3

2.2. Starting the Subdivision

  • Figure 1 traces the octahedron's eight-face start to level 5 (8,192 triangles); roots use S/N plus clockwise face numbering.Source: Figure 1 · p. 3, §2.2 · p. 3

2.3. Recursive Subdivision of the Sphere

  • Each triangle is split into four by edge midpoints, recursively naming children by appending their number; this defines HTM and supports depth-specific point indexing.The recursion can continue to any desired depth, with depth 0 denoting the whole sphere.Source: §2.3 · pp. 4–5

2.4. Naming and Location

  • Trixel names encode depth and location; catalog HtmIDs serve as keys, with 64-bit capacity to depth 31 but transcendental-function breakdown at depth 26.Surveys use 21-deep HtmIDs to name distinct objects.Source: §2.4 · p. 5

2.5. Properties and Statistics of the HTM

  • At depth 7, arc-length scatter is 15% and mean arc length is about 1.23 times canonical size; beyond depth 7 area variance is 24%, with max/min area ratio about 2.Inner angles remain between π/4 and π/2; area differences arise from center versus corner trixel shapes, while curvature becomes negligible beyond depth 7.Source: §2.5 · pp. 5–6, Figure 3 · p. 6

3. Defining the Geometry

The geometry framework represents spherical areas using halfspaces, intersections of halfspaces called convexes, and unions of convexes called regions. Because a convex can form multiple disconnected patches on the sphere, its component halfspaces affect its shape and handling.

3. Defining the Geometry

  • The geometry primitives are intended to support intersecting spherical areas with HTM trixels and classifying trixels as inside, outside, or partially overlapping a region.The paper describes the geometry primitives as a foundation for computing an HTM cover.Source: §3 · p. 6

3.1. Halfspaces

  • A halfspace is specified by a vector pointing into it and the distance to its bounding plane; negative-distance halfspaces cover more than half the sphere and are called holes.The paper gives examples of halfspaces defining caps with opening angles of 30° and 150°.Source: §3.1 · p. 6

3.2. Convexes

  • A convex is the intersection of halfspaces, but its spherical intersection can be disconnected into multiple patches.For example, a cube with face offsets of -0.6 produces eight triangular patches near its vertices.Source: §3.2 · p. 7, Figure 4 · p. 7
  • Convexes made only of positive and zero halfspaces always form one connected patch; atypical multi-patch convexes involve at least one negative halfspace.The sign assigned to a convex is used later when computing intersections with the HTM.Source: §3.2 · p. 7

3.3. Regions

Regions are unions of convexes, allowing complex spherical areas to be represented for intersection with HTM trixels. The section also describes quick simplifications that reject empty convexes and remove redundant halfspaces.

3.3. Regions

  • A region is a union of convexes, equivalent to a disjunctive normal form of halfspaces, and can represent complex spherical areas for intersection with HTM trixels.The paper presents generic region–trixel intersection as a basis for an indexing tool.Source: §3.3 · pp. 7–8

3.4. Trivial Simplifications

  • Duplicate halfspaces are reduced to one, exact complementary pairs make a convex NULL, and a whole-sphere halfspace can be dropped unless it is the convex’s only halfspace.A halfspace with d > 1 makes the convex NULL.Source: §3.4 · p. 8

Recognizing the NULL Convex

Eliminating Redundant Halfspaces

  • When β>α and β-α≤γ, the β halfspace is redundant and can be dropped.The test compares each pair’s relative angle with the difference in opening angles.Source: Figure 5 · p. 8, Eliminating Redundant Halfspaces · p. 9
  • Pairwise redundancy checks take O(N^2); the paper says this is inexpensive because N is typically 5 and generally below 100.Halfspaces are sorted by size so the smallest are compared with the largest first, eliminating obvious cases early.Source: Eliminating Redundant Halfspaces · p. 9

3.5. Computing the Vertices (Roots) of a Convex

The method finds candidate sphere intersections of halfspace planes, filters them against the remaining halfspaces, and uses the surviving visible roots as convex vertices. The resulting root information supports removing redundant halfspaces and computing patches.

3.5. Computing the Vertices (Roots) of a Convex

  • Finding visible roots takes O(N^2); with N typically 5 and bounded by 100, the paper considers this feasible, and uses visible roots to discard redundant halfspaces and compute patches.The method also uses visible roots to compute other convex properties.Source: §3.5 · p. 9
  • Two halfspace planes define a line whose intersections with the unit sphere are candidate roots; parallel planes are excluded from this calculation.The line is expressed using a component parallel to the cross product of the plane normals.Source: §3.5 · pp. 9–10
  • The method considers only the positive root for one ordering of the normals, since reversing the normals’ order yields the other root.The cross product changes sign when the normals are interchanged.Source: Figure 6 · p. 9, §3.5 · p. 10
  • A convex with N halfspaces has at most N(N-1) candidate roots; roots that fail any other halfspace are bad, and the remaining good roots are its vertices.A pair of halfspaces can define 0, 1, or 2 points on the sphere.Source: §3.5 · pp. 9–10

3.6. Necessary Halfspaces and Masking Circles

The method starts with halfspaces contributing to good roots, then adds masking circles to exclude bad roots created by that reduced set. It removes other redundant halfspaces and tests nonintersecting circles to determine which holes remain visible.

3.6. Necessary Halfspaces and Masking Circles

  • The initial necessary-halfspace set contains halfspaces contributing to good roots, but may create bad roots that must be masked by additional halfspaces.Each good root contributes two halfspaces to the initial set.Source: §3.6 · pp. 10–11
  • The algorithm repeatedly adds the halfspace that eliminates the most unmasked bad roots, stopping when none remain; these added halfspaces are masking circles.Once closed, the set correctly masks all intersections of its circles.Source: §3.6 · p. 11

Removing Additional Halfspaces

  • After masking, other halfspaces related to roots are redundant; among nonintersecting holes, the method keeps visible ones and removes the rest.Holes fully outside the convex can be removed by testing whether their anti-center lies outside it.Source: §3.6 · p. 11, Removing Additional Halfspaces · p. 11

Determining if a Halfspace Is Visible

  • A nonintersecting circle lies wholly inside or outside the convex, so the method tests an arbitrary perimeter point to determine which case holds.The paper chooses a point west of the circle’s center and precomputes it for reuse.Source: Determining if a Halfspace Is Visible · p. 11

Visible Halfspaces

3.7. Determining Arcs and Patches

The section turns visible roots into ordered arcs and assembles those arcs into closed patches, including cases where a halfspace has multiple root pairs. Root ordering resolves the ambiguous connections; traversal then identifies rooted patches and unrooted holes.

3.7. Determining Arcs and Patches

  • A visible-roots table records each root’s position and defining halfspaces, but a halfspace with multiple root pairs requires extra computation to determine its arcs.For example, all four roots in the illustrated case relate to halfspace 1, so their pairing is ambiguous.Source: §3.7 · p. 12
  • Ranking roots counterclockwise in the halfspace plane resolves ambiguous pairings and identifies which roots connect to form visible arcs.In the example, the ordering (b,c,d,a) identifies [1:c,d] as an arc.Source: §3.7 · p. 12

Assembling Arcs into Patches

  • To form closed patches, follow each arc’s endpoint to the next arc’s start until returning to the initial root, while preserving the output order needed for visualization.The output order is bounding circles, rooted halfspaces, then unrooted holes.Source: Assembling Arcs into Patches · p. 13, Rooted Halfspaces · p. 13

Unrooted Holes

  • Following rooted patches, output enclosed unrooted holes in the bounding-circle form, using the westward point as both arc endpoints.Source: Unrooted Holes · p. 13

3.8. Simplification Using the Arcs

Once the arcs are ordered, their parent halfspaces identify which constraints contribute to the convex; redundant halfspaces can then be removed.

3.8. Simplification Using the Arcs

  • The ordered arcs identify the contributing parent halfspaces, allowing redundant constraints to be removed while retaining the arc list for visualization.Source: §3.8 · p. 13

4. Spatial Queries: Intersecting with the HTM

The spatial-query algorithm classifies HTM trixels as full or partial relative to a region, then recursively refines partial trixels to produce a cover. It handles different convex configurations with geometric intersection tests and translates the resulting trixels into ranges for indexing.

4.1. Intersecting a Trixel with a Halfspace

  • For a halfspace, corner tests identify full or partial trixels, while cases with all corners outside require further intersection tests before ruling the trixel out.A positive halfspace containing all three corners makes the trixel full; mixed inside/outside corners make it partial.Source: §4.1 · pp. 13–14

4.2. The Intersection of a Halfspace with an Edge of a Triangle

  • For edge crossings, parameterize the shorter great-circle segment and solve a quadratic in s; roots in (0,1) identify intersections.Source: §4.2 · p. 15

i) Positive and Zero Convexes

  • For positive and zero convexes, the halfspace decision tree applies, with each halfspace tested to determine whether the trixel is partial or outside.Source: i) Positive and Zero Convexes · p. 16

ii) Negative Convexes

  • For negative convexes, test for holes within an all-corners-inside trixel and for boundary intersections; complicated edge-intersection patterns are conservatively marked partial.Source: ii) Negative Convexes · p. 16

iii) Mixed Convexes

  • Mixed convexes combine positive- and negative-convex tests; uncommon, complicated cases are usually marked partial because resolving them can cost more computation.Source: iii) Mixed Convexes · pp. 16–17

4.4. Terminating the Recursion

  • Recursion splits partial trixels into four children and stops at a tunable maximum depth or when child and sibling classifications meet heuristic stopping conditions.The initial heuristic stopped too early when its last condition triggered often, so that condition was deferred until a minimum depth.Source: §4.4 · p. 18, Heuristic test · p. 18

4.5. Translating Trixels to HTM Ranges

  • For database use, trixels are represented at a fixed depth—21 in this implementation—and a shallower trixel maps to a contiguous range of deeper-level addresses.A region containing trixels at multiple levels can be represented as a set of (low, high) intervals.Source: §4.5 · p. 18
  • When too many ranges remain, merging intervals across gaps reduces their count but adds trixels outside the computed cover; this overshoot is preferred to any undershoot.Overshoot requires finer-grain analysis during spatial searches, whereas undershoot would leave region areas unsearched.Source: §4.5 · p. 18

5. Bounding Circles and Convex Hulls

The section adds geometric tools for bounding and measuring spherical regions and for computing convex hulls. Its methods account for small-circle boundaries as well as great-circle geometry.

Computing the Bounding Circles

  • Bounding circles screen patch pairs for overlap; positive small-circle protrusions add an arc midpoint, and the smallest valid candidate circle is selected.Source: Computing the Bounding Circles · p. 19

Computing the Area

  • For polygon area, replace small-circle arcs with great-circle connections and add signed semilune areas, computed as the difference between two spherical triangles.Source: Computing the Area · p. 20
  • The area of a patch is assembled from its great-circle triangles and arc semilunes, then summed over the region’s patches.Source: Computing the Area · p. 21

Computing the Arc Length

  • Small-circle arc lengths are computed in the small circle’s coordinate system by taking the difference between endpoint azimuths.Source: Computing the Arc Length · p. 21

Convex Hulls

  • The convex-hull method requires points to fit within a hemisphere, projects them onto a tangent plane, and reduces the problem to a planar hull computation.The planar algorithm used is Andrews.Source: Convex Hulls · p. 21

6. Implementation and Performance

The C# implementation with SQL Server 2005 substantially outperformed the earlier C++ implementation, while region-cover granularity depends on the tradeoff between lookup costs and saved distance tests. The appropriate subdivision depth also varies with object density.

6. Implementation and Performance

  • The original C, C++, and Java algorithms were adapted as C++ external stored procedures for SQL Server 2000, then rewritten in C# using SQL Server 2005's CLR binding.The C++ implementation was used in the Sloan Digital Sky Survey.Source: §6 · p. 21
  • C# with SQL Server 2005 improved performance over C++ with SQL Server 2000 by 50× for scalars and 6× for table-valued functions.Table 4 reports CPU costs for the implementations, using complex Sloan Digital Sky Survey regions for fHtmcoverRegion().Source: §6 · p. 21, Table 4 · p. 21
  • For SQL Server 2005's B-tree, a range lookup costs about five distance tests, so a discarded sub-trixel needs at least 10 objects to break even.Smaller trixels better approximate region boundaries but require more range lookups.Source: §6 · p. 22
  • The depth rule is A >12R/D; at R=5, SDSS density of about 40 objects/arcmin2 favors depth 13, while USGS density of 0.01 objects/arcmin2 favors depth 9.Object density therefore guides the finest useful trixel granularity.Source: §6 · p. 22

7. Summary

The HTM combines spherical partitioning with database indexing and recursively covers generalized spherical polygons. Its algorithms performed acceptably on astronomical databases containing several hundred million objects.

7. Summary

  • The HTM implements spherical partitioning using a spherical quadtree mapped onto a SQL Server B-tree index.This supports spatial partitioning in a relational database.Source: §7 · p. 22
  • Halfspace-based descriptions of generalized spherical polygons allow recursive computation of a trixel cover that converts into database range queries.The cover provides the region representation used for querying.Source: §7 · p. 22
  • The algorithms performed acceptably on astronomical databases containing several hundred million objects.Source: §7 · p. 22
Loading cs/0701164v1…