PolygonGeometry.contains not using existing bounding box

[kodebach]

The PolygonGeometry.contains function already checks the bounding box before checking the exact polygon. This is a good optimization. However, the bounding box is recomputed every time, even if the PolygonGeometry object already has a bbox set. That negates much of the optimization

spatial-k/turf/src/commonMain/kotlin/org/maplibre/spatialk/turf/booleans/contains.kt

Lines 35 to 55 in 53208b0

	public fun PolygonGeometry.contains(pos: Position, ignoreBoundary: Boolean): Boolean {
	val bbox = this.computeBbox()
	// normalize to multipolygon
	val polys =
	when (this) {
	is Polygon -> listOf(this.coordinates)
	is MultiPolygon -> this.coordinates
	}
	return pointInPolygon(pos, bbox, polys, ignoreBoundary)
	}
	private fun pointInPolygon(
	pos: Position,
	bbox: BoundingBox,
	polys: List<List<List<Position>>>,
	ignoreBoundary: Boolean,
	): Boolean {
	// Quick elimination if the point is not inside the bbox
	if (!inBBox(pos, bbox)) {
	return false
	}

Line 36 should instead be:

val bbox = this.bbox ?: this.computeBbox()

Repeated calls to contains will still not remember the computed bounding box (not possible with a data class), but at least users can do

val polygonWithBbox = polygon.withComputedBbox()
polygonWithBbox.contains(point1)
polygonWithBbox.contains(point2)

to avoid recomputation.

[sargunv]

I guess this could return the wrong value if the provided bbox is incorrect, but that's probably acceptable.

Curious, what does turf.js do?

[kodebach]

Curious, what does turf.js do?

https://github.com/Turfjs/turf/blob/5a34d08b07930f0ebf0f1c83307d4910fb7a717a/packages/turf-boolean-point-in-polygon/index.ts#L39-L79

They just take the pre-computed bounding box as-is and don't even attempt to compute a new one, which might be the best approach, since calculating the bounding box might take a non-trivial amount of the total run time. I haven't benchmarked that, but it could actually be more expensive than the point-in-polygon test itself.

At a quick glance, the point-in-polygon test iterates over all the points of the (multi-)polygon in pairs (with some early returns). So processes every position at most twice, but in a loop that has at most as many iterations as their are positions.

computeBbox must necessarily iterate over every single point to get the min/max lat/lon, but before it does that, it also calls flattenCoordinates, which might build multiple intermediate Lists.

For a more efficient flattenCoordinates and computeBbox I'd suggest:

public fun GeoJsonObject.allPositions(): Sequence<Position> {
    return sequence {
        when (this@allPositions) {
            is Point -> yield(coordinates)
            is MultiPoint -> yieldAll(coordinates)
            is LineString -> yieldAll(coordinates)
            is MultiLineString -> coordinates.forEach { yieldAll(it) }
            is Polygon -> coordinates.forEach { yieldAll(it) }
            is MultiPolygon -> coordinates.forEach { polygon -> polygon.forEach { yieldAll(it) } }
            is GeometryCollection<*> -> geometries.forEach { yieldAll(it.allPositions()) }
            is Feature<*, *> -> geometry?.let { yieldAll(it.allPositions()) }
            is FeatureCollection<*, *> -> features.forEach { yieldAll(it.allPositions()) }
        }
    }
}

public fun GeoJsonObject.flattenCoordinates(): List<Position> = allPositions().toList()

public fun Geometry.computeBbox(): BoundingBox = computeBbox(this.allPositions())

public fun computeBbox(coordinates: List<Position>): BoundingBox = computeBbox(coordinates.asSequence()) 
public fun computeBbox(coordinates: Sequence<Position>): BoundingBox {
    val coordinates =
        coordinates.fold(
            doubleArrayOf(
                Double.POSITIVE_INFINITY,
                Double.POSITIVE_INFINITY,
                Double.NEGATIVE_INFINITY,
                Double.NEGATIVE_INFINITY,
            )
        ) { result, (longitude, latitude) ->
            require(longitude.isFinite() && latitude.isFinite()) {
                "coordinates must be finite but got ($longitude, $latitude)"
            }
            if (result[0] > longitude) result[0] = longitude
            if (result[1] > latitude) result[1] = latitude
            if (result[2] < longitude) result[2] = longitude
            if (result[3] < latitude) result[3] = latitude
            result
        }
    require(coordinates[0].isFinite()) { "coordinates must not be empty" }
    return BoundingBox(coordinates[0], coordinates[1], coordinates[2], coordinates[3])
}

That way we process all positions exactly once and don't allocate any intermediate lists.

[sargunv]

All sounds reasonable to me