turf icon indicating copy to clipboard operation
turf copied to clipboard

turf-boolean-contains + turf-boolean-within: Fix line in polygon

Open samuelarbibe opened this issue 10 months ago • 0 comments

This PR fixes a false-positive when running boolean-contains (or boolean-within) of lineString inside a polygon, as demonstrated in #2441.

The current implementation of boolean-contains checks if all the midpoints of the line segments are inside the polygon, and results in a false-positive in the following cases:

Line midpoint in Polygon Line midpoint in Polygon

This PR proposes the following logic:

  1. The line and polygon's bboxes must overlap. (optimization)
  2. All line points must be contained by the polygon.
  3. If the line intersects with polygon - all segments must be contained by the polygon. At least one of them should be fully contained by the polygon. (optimization - midpoint is sufficient)

This "waterfall" approach makes sure no extra computation is performed - unless necessary. Only quirky cases will require the extra computation of step 3 (In most cases, a single iteration of step 3 will suffice). The only exception is that the line's points are checked to be contained instead of the midpoints - but it returns false-positives for pretty basic cases, so I find this to be a reasonable compromise.

A test case for the second image has been added.

samuelarbibe avatar Feb 27 '25 10:02 samuelarbibe