Spatial join: pairs of two indexes by a joint walk, envelopes only
SpatialIndex<T> gets two methods that ADR 0014 left out as a separate topic: Join (all pairs of an item of one index and an item of another whose envelopes meet) and SelfJoin (all pairs of different entries within one index). Both walk the trees together, so that a pair of subtrees whose envelopes do not meet is skipped as a whole. As in ADR 0014 this is a pre-filter on envelopes only: the exact test on the geometries stays with the caller (.Where(p => p.Left.Intersects(p.Right))), and there is no predicate shortcut. The structure stays immutable and thread-safe, and SelfJoin is the main gain: it returns every overlapping pair once, which a loop of queries cannot.
German version: 0021-spatial-join-doppelbaum-nur-vorfilter.de.md
Consequences
- Placement: instance methods of
SpatialIndex<T>inSpatialNET.Extensions(the class becomespartial). No new package. For the package validation this is an addition only. - API:
Join<TOther>(SpatialIndex<TOther> other, double distance = 0)returnsIEnumerable<(T Left, TOther Right)>;Join<TOther>(other, ICollection<(T, TOther)> results, double distance = 0)adds the pairs to a collection that the caller owns and does not clear.SelfJoin(double distance = 0)returnsIEnumerable<(T First, T Second)>: every unordered pair of different entries once. Never an entry with itself, never both(a, b)and(b, a); which of the two isFirstis not specified. Entries with an equal payload are different entries and pair up.Joinwith the index itself is allowed and returns every ordered pair, including each entry with itself; that is the plain definition of a join, andSelfJoinis the call for the unique pairs.
- Distance:
distance(finite, not negative) widens the envelopes of one side by that amount before they are compared, so the pair is returned if the gap between the envelopes is at mostdistancein both axes. This is still only an envelope test and no distance predicate, like "within distance d" in ADR 0014. A negative,NaNor infinite value throwsArgumentOutOfRangeException(ADR 0012). - Result: every qualifying pair exactly once, in no particular order, like
Query. A caller that needs an order sorts. Empty indexes give no pairs.nullthrowsArgumentNullException. The enumeration is lazy and can be repeated. - Thread safety: both indexes are immutable, and a join uses only local state. Any number of threads may join the same instances, also at the same time.
- Algorithm: a stack of pairs of nodes, starting with the two roots. A pair is dropped if the envelopes do not meet (widened by
distance); two leaves are compared entry by entry; otherwise the children are paired. ForSelfJoinonly pairs(x, y)withx ≤ yare visited, so each unordered pair of nodes is walked once and, inside one leaf, entryiis paired only withj > i. - Measured:
SpatialJoinBenchmarks(one-shot--quick-join; the second set is the first one shifted slightly) shows that the gain is real but modest and depends on the data. For 100,000 evenly spread itemsJointakes 46 ms against 100 ms for a loop ofQuerycalls (2.2 times faster), andSelfJoin22 ms; for 1,000 items, or for 100,000 items in dense clusters, where the number of pairs dominates (1.4 million),Joinis on a par with the loop (168 ms against 187 ms). SoJoinis a convenience with a speed-up for large, evenly spread sets;SelfJoinis the method that offers something new. - Tests (ADR 0008): oracles are brute force over all pairs and a loop of NTS
STRtreequeries (with the envelope widened by the distance). Property tests (CsCheck) cover random sets of points, lines and rectangles on a coarse grid (many touching and equal envelopes) with different node capacities for the two sides, distances including 0, the collection overload,SelfJoin(each pair once, never with itself), a join with the index itself, equal payloads, different payload types, empty andnullinput, invalid distances and parallel joins. Fixtures do not apply because the index has no geometry result. - Playground and documentation: the playground is not affected (instance methods of a data structure, like
Query); a section in the concept page of the spatial index showsJoinfollowed by an exact.Where.
Considered Options
- A predicate shortcut such as
Join(other, predicate)orIntersectingPairs()(rejected: a second API for predicates, as in ADR 0014;.Whereis enough and shows what the exact test is) - Extension methods on
IEnumerableof geometries that build the indexes (rejected: the caller usually has the indexes already, and building them isToSpatialIndex()) - Returning pairs in a defined order (rejected: sorting costs for every caller, and
Queryis unordered too; ordered output is a one-liner) SelfJoinreturning ordered pairs (rejected: every pair would occur twice, which is exactly what makes the loop of queries unsuitable)- Excluding an entry's equal-payload twins from
SelfJoin(rejected: two entries are two entries; a caller that wants to ignore twins filters on the payload) - A join that applies an exact distance (rejected: that is a geometry predicate, ADR 0014;
distanceonly widens envelopes) - A parallel join (rejected for now: the measured gain is modest, and determinism and simplicity come first)