predicates

orb-predicates

Spatial relationship predicates for orb geometry types.

This package implements the standard OGC/DE-9IM spatial predicates for determining topological relationships between geometries.

Features

• Implements the complete OGC/DE-9IM predicate set (Within, Contains, Covers, CoveredBy, Intersects, Disjoint, Touches, Crosses, Overlaps).
• Supports every orb geometry type (including orb.Collection and orb.Bound) for any combination of A/B inputs.
• Validated against thousands of official JTS Topology Suite XML test cases that live under testdata/jts.
• Ships with extensive Go unit tests that describe the tricky edge cases you typically run into when working with GIS data.
• Includes comprehensive benchmarks for performance testing across all geometry types and sizes.
• Optimized with bounding box early-exit and efficient algorithms for real-world performance.

Installation

go get github.com/tingold/orb-predicates

Predicates

Supported Geometry Types

All predicates support the following orb geometry types:

• orb.Point
• orb.MultiPoint
• orb.LineString
• orb.MultiLineString
• orb.Ring
• orb.Polygon
• orb.MultiPolygon
• orb.Collection
• orb.Bound

Usage

package main

import (
    "fmt"

    "github.com/paulmach/orb"
    predicates "github.com/tingold/orb-predicates"
)

func main() {
    // Define a polygon
    poly := orb.Polygon{
        orb.Ring{
            orb.Point{0, 0},
            orb.Point{10, 0},
            orb.Point{10, 10},
            orb.Point{0, 10},
            orb.Point{0, 0},
        },
    }

    // Points to test
    pointInside := orb.Point{5, 5}
    pointOutside := orb.Point{15, 15}
    pointOnEdge := orb.Point{5, 0}

    // Within / Contains
    fmt.Println(predicates.Within(pointInside, poly))   // true
    fmt.Println(predicates.Contains(poly, pointInside)) // true

    // Intersects / Disjoint
    fmt.Println(predicates.Intersects(pointOnEdge, poly)) // true
    fmt.Println(predicates.Disjoint(pointOutside, poly))  // true

    // Touches
    fmt.Println(predicates.Touches(pointOnEdge, poly)) // true

    // Line crossing polygon
    line := orb.LineString{
        orb.Point{-5, 5},
        orb.Point{15, 5},
    }
    fmt.Println(predicates.Crosses(line, poly)) // true
}

Working with Different Geometry Combinations

// Polygon-Polygon relationships
smallSquare := orb.Polygon{
    orb.Ring{
        orb.Point{2, 2},
        orb.Point{4, 2},
        orb.Point{4, 4},
        orb.Point{2, 4},
        orb.Point{2, 2},
    },
}

largeSquare := orb.Polygon{
    orb.Ring{
        orb.Point{0, 0},
        orb.Point{10, 0},
        orb.Point{10, 10},
        orb.Point{0, 10},
        orb.Point{0, 0},
    },
}

fmt.Println(predicates.Within(smallSquare, largeSquare))   // true
fmt.Println(predicates.Contains(largeSquare, smallSquare)) // true
fmt.Println(predicates.Covers(largeSquare, smallSquare))   // true

// Overlapping polygons
overlapping := orb.Polygon{
    orb.Ring{
        orb.Point{5, 5},
        orb.Point{15, 5},
        orb.Point{15, 15},
        orb.Point{5, 15},
        orb.Point{5, 5},
    },
}

fmt.Println(predicates.Overlaps(largeSquare, overlapping)) // true
fmt.Println(predicates.Intersects(largeSquare, overlapping)) // true

Testing

Run the complete unit test suite:

go test ./...

Benchmarks

The package includes comprehensive benchmarks for all predicates across different geometry sizes and combinations.

Running Benchmarks

# Run all benchmarks
go test -bench=. -benchmem

# Run specific predicate benchmarks
go test -bench=Within -benchmem
go test -bench=Intersects -benchmem

# Run benchmarks with longer duration for more accurate results
go test -bench=. -benchmem -benchtime=1s

Benchmark Categories

The comprehensive benchmark suite includes over 80 benchmarks covering:

• Point vs Polygon: Small (5 vertices), medium (50), large (500), and very large (2000) polygons with points inside, outside, and on boundaries
• LineString vs Polygon: Lines inside, crossing, and outside polygons of various sizes
• Polygon vs Polygon: Contained, overlapping, disjoint, and touching polygons
• MultiPoint operations: Small (10), medium (100), and large (500) multipoints against polygons
• MultiPolygon operations: Point containment and polygon intersection
• LineString vs LineString: Small (10), large (100), and very large (500) linestrings, both intersecting and disjoint
• Ring operations: Ring-to-ring intersection and containment
• Collection operations: Mixed geometry collections against polygons
• Bound operations: Point, polygon, and linestring operations with bounds
• Worst-case scenarios: Points on boundaries, nearly collinear segments, and degenerate polygons
• Helper functions: Low-level geometric operations including segment intersection, point-on-segment checks, and bounding box overlap

Performance Characteristics

Performance scales approximately linearly with vertex count for most operations.

Performance Optimizations

The package includes several optimizations for improved performance:

• Bounding box early-exit: All predicates check bounding box overlap first to quickly reject disjoint geometries
• Optimized helper functions: Internal functions like lineStringsIntersect, ringsIntersect, ringBoundariesIntersect, and lineStringIntersectsRing include bounding box rejection for fast early-exit on disjoint geometries
• Smart sampling for MultiPolygon containment: Uses efficient vertex-proximity checking (50 samples + targeted checks near polygon vertices) instead of dense sampling (up to 10,000 samples) when checking if linestrings are within multipolygons, providing significant performance improvements while maintaining accuracy
• Efficient bounds overlap checking: Dedicated helper functions (ringBoundsOverlap, lineStringBoundsOverlap, lineStringRingBoundsOverlap) for optimized bounding box checks

JTS compatibility suite

TestJTSPredicates replays the official JTS Topology Suite XML fixtures located in testdata/jts and verifies that Intersects, Contains, Within, Covers, CoveredBy, Crosses, Overlaps, Touches, and Disjoint all mirror JTS behaviour.

go test ./... -run JTSPredicates -v

Need a quick overview of what those XML files contain? TestJTSSummary prints counts for each predicate so you can tell whether a new fixture increases coverage:

go test ./... -run JTSSummary -v

The XML files are copied from the JTS repository (see testdata/jts) and can be extended by dropping additional fixtures into that directory.

Using Bounds

bound := orb.Bound{
    Min: orb.Point{0, 0},
    Max: orb.Point{10, 10},
}

point := orb.Point{5, 5}
fmt.Println(predicates.Covers(bound, point)) // true

Predicate Semantics

Within vs Covers

• Within: The interior of A must intersect the interior of B. Boundary-only contact is not sufficient.
• Covers: Every point of B must be in A (interior or boundary). A geometry entirely on the boundary of another is covered but not within.

Intersects vs Touches

• Intersects: Any shared point counts.
• Touches: Only boundary contact; interiors must not intersect.

Crosses vs Overlaps

• Crosses: For geometries of different dimensions (e.g., line crossing polygon) or lines crossing lines where the intersection is a point.
• Overlaps: For geometries of the same dimension that share area/length but neither contains the other.

License

See LICENSE file.