Rectangle Clip Fast Paths

o17.5.2 lands the first owned constructive fast path through axis-aligned rectangle clipping.

Request Signals

  • clip_by_rect

  • rectangle clip

  • constructive fast path

  • clip performance

  • overlay first fast path

  • cccl

Open First

  • docs/architecture/clip-fast-paths.md

  • docs/architecture/segment-primitives.md

  • src/vibespatial/constructive/clip_rect.py

  • tests/test_clip_rect.py

Verify

  • uv run pytest tests/test_clip_rect.py tests/test_degeneracy_corpus.py

  • uv run vsbench run clip-rect --arg kind=line

  • uv run vsbench run clip-rect --arg kind=polygon

  • uv run pytest tests/upstream/geopandas/tests/test_geom_methods.py -k clip_by_rect

  • uv run pytest tests/upstream/geopandas/tools/tests/test_clip.py -k "test_clip_poly or test_clip_line_keep_slivers or test_clip_multipoly_keep_slivers"

  • uv run python scripts/check_docs.py --check

Risks

  • General polygon intersection is too broad for the first constructive fast path.

  • Forcing a slower owned host implementation onto GeoPandas would ship a performance regression.

  • Hole, multipolygon, and invalid-input behavior can drift if the fast path is not checked against the degeneracy corpus.

Intent

Choose the first constructive surface that is genuinely GPU-shaped and useful to GeoPandas, without overcommitting to a full overlay implementation.

Options Considered

  1. Full polygon or line intersection against arbitrary geometries. Too broad for the first landing and too much assembly before we have a GPU variant.

  2. Keep using Shapely only and postpone constructive kernels entirely. Safe on CPU, but it leaves no owned execution seam for Phase 5.

  3. Rectangle clip first. Bounds filtering, candidate compaction, and per-family clipping all map cleanly onto reusable primitives and the GeoPandas clip / clip_by_rect surfaces already expose it.

Decision

Use option 3.

The owned rectangle-clip engine now handles:

  • Point and MultiPoint

  • LineString and MultiLineString

  • Polygon and MultiPolygon

It uses:

  • owned buffer conversion

  • row bounds filtering

  • direct line clipping and ring clipping for candidate rows

  • row-level fallback for unsupported or invalid geometry cases

GeoPandas Adapter Policy

The repo now has an explicit adapter seam at GeometryArray.clip_by_rect, and the public clip(...) path opportunistically stays inside the owned/native boundary when the resulting family mix is representable there.

Current state:

  • the owned CPU path is correct and benchmarked

  • the owned GPU point-only path is now faster than Shapely on the benchmark harness and can re-enter from device-backed point arrays without materializing the full source batch

  • polygon families have a device-resident GPU clip path via Sutherland-Hodgman kernel with vectorized ring extraction and direct OGA construction

  • line families have a device-resident GPU clip path via Liang-Barsky kernel with CuPy/CCCL coordinate assembly (_build_line_clip_device_result)

  • both polygon and line GPU paths return Residency.DEVICE OwnedGeometryArrays

  • default public clip(..., keep_geom_type=False) now builds a row-preserving native result first and only exits to host for explicit semantic cleanup when the output cannot stay in the native family model

  • host normalization preserves owned backing for representable host-side results, so later area / length probes stay on the owned measurement path instead of silently dropping to Shapely

  • unsupported public outputs such as GeometryCollection slivers stay on the explicit compatibility path instead of being forced into the owned model

  • public ordering now matches GeoPandas again: sort=False preserves encounter order, and sort=True sorts by index

CCCL Mapping

The intended GPU path stays staged:

  • bounds filter over row envelopes

  • candidate compaction with DeviceSelect

  • per-family clip kernels over compacted rows

  • output restoration by row scatter

Rectangle clip is the right first constructive fast path because it preserves that staged structure instead of hiding everything inside a monolithic overlay kernel.

Consequences

  • Phase 5 now has a real owned constructive engine to optimize further

  • the owned point-only GPU path can keep clipped coordinate payloads on device across constructive chains

  • GeoPandas keeps current host performance while the adapter seam stays visible

  • later overlay work can reuse the same candidate/filter/restore structure