Monotone Chain

[cookiedan42]

Overview

Montone Chains are a way of preprocessing an array of coordinates so that intersections can be efficiently calculated using binary search, and looks to be a primitive used in JTS and GEOS for some internal operations

I built a proof of concept #1467 which uses &[Coord] to an existing geometry's backing Vec(s) as the backing data and implemented Intersects for existing geometries.
Overall there's a significant speedup on larger geometries in Intersects and ContainsProperly features where I replaced the brute force linestring-linestring intersections, but slowdown in smaller geoms. Haven't done the benching to find the crossing point, so the current threshold const is arbitrary

Discussion points

1. Integration

Option 1: Monotone Geometry analogous to Prepared Geometry (leaning toward this option)

struct MonotoneLineString{
  geom:LineString
  chain: MonotoneChain
}

struct MonotoneMultiLineString{
  geom:MultiLineString
  chain: Vec<MonotoneChain>

  // or maybe Vec<MonotoneLineString>?
}

struct MonotonePolygon{
  geom:Polygon
  exterior: MonotoneChain
  interiors:Vec<MonotoneChain>
}

• Make the choice to use Monotone-based geometries and algorithms explicit
• Possible to delegate to base geometry for anything not implemented
• Easier to reuse already constructed Monotone-based geometry multiple times

However

• Not all base geometries have a useful Monoton-based equivalent
• Adds cognitive overhead when choosing to convert into this type

Option 2: Integrate into existing methods

• Requires tuning of thresholds to switch between the different approaches to not cause performance regression
• pay the conversion overhead every invocation
• most "discoverable"
• most compatible with Geometry and GeometryCollection based workflows

Option 3: Independent Function

• least disruptive
• pay the conversion overhead every invocation

I'm personally leaning toward option 1, with selective use of option 2 when benefit is clear

2. Naming

1. How should this new class of structs be named? MonotoneMultiLineString is quite a mouthful
2. How to disambiguate MonotoneChain concept of monotone from the existing MonoPoly which uses a different concept of Monotonic Geometry

References:

[cookiedan42]

Headlining Benchmarks

MultiPolygon intersects time:   [24.313 ms 24.356 ms 24.412 ms]
                        change: [-70.216% -70.098% -69.978%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe

complex polygon contains_properly polygon (Trait)
                        time:   [112.49 µs 112.80 µs 113.16 µs]
                        change: [-57.389% -57.207% -57.024%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
  2 (2.00%) low mild
  3 (3.00%) high mild

[urschrei]

How does this integrate (if at all) with https://github.com/georust/geo/blob/main/geo/src/algorithm/monotone/mod.rs?

[cookiedan42]

I don't think there's any relation
The existing MonoPoly looks to be for slicing up (Multi)Polygons for fast Point in Polygon checks
MontoneChain is more LineString related

[michaelkirk]

I'm personally leaning toward option 1, with selective use of option 2 when benefit is clear

That's my instinct. Thanks for laying out some alternatives.