BooleanContains should return false when the Outer contains all the verticies of the Inner, but their borders intersect.

[chriserickson]

Given two polygons, Outer and Inner, we are checking that booleanContains(outer, inner) should return the correct result.

Consider the case where Outer contains all of the verticies of Inner, but their boundaries intersect. booleanContains incorrectly returns false in such a scenario.

Here is a picture of an example case:

As well as a unit test showing the failing case.

import booleanContains from "@turf/boolean-contains"

describe('booleanContains', () => {

  it('Contains should be false when borders intersect but all verticies are contained', () => {

    // Outer: A 2 x 2 square with the top-right quadrant removed.
    const outer = {
      type: "Polygon",
      coordinates: [[
        [0, 0],
        [0, 2],
        [1, 2],
        [1, 1],
        [2, 1],
        [2, 0],
        [0, 0]
      ]]
    };

    // Inner: A triangle with all 3 verticies inside outer, but one segment intersecting the border of outer
    const inner = {
      type: "Polygon",
      coordinates: [[
        [.1, .1],
        [.1, 1.9],
        [1.9, .1],
        [.1, .1]
      ]]
    }

    expect(booleanContains(outer, inner)).toBe(false) // Returns true
  })
});

Result:

  ● booleanContains › Contains should be false when borders intersect but all verticies are contained

    expect(received).toBe(expected) // Object.is equality

    Expected: false
    Received: true

      89 |     }
      90 | 
    > 91 |     expect(booleanContains(outer, inner)).toBe(false)
         |                                           ^
      92 |   })
      93 | });
      94 | 

[chriserickson]

Note, in the picture, there are only 3 verticies, the lighter-gray verticies are midpoints and there for editing.

[stebogit]

Hey @chriserickson,
this the definition of "contains" from the module's description (see readme file):

The interiors of both geometries must intersect and, the interior and boundary of the secondary (geometry b) must not intersect the exterior of the primary (geometry a).

Thus I believe the output you get is actually correct.

[chriserickson]

Hi @stebogit,

Thanks for the quick reply!

I did read the definition, and I don't understand how this doesn't cover my reported case:
"the interior and boundary of the secondary (geometry b) must not intersect the exterior of the primary (geometry a)"

In this case, the boundary of the second geometry intersects the exterior of the first geometry. Although I'm not sure of the semantic difference between "boundary" and "exterior".

In any case, I'd argue that it is incorrect logically and intuitively. It does not actually contain the second polygon, I don't think anybody would expect contains to return false. Moreover, other libraries, such as JTS and/or a database implementation of ST_Contains return a "true" in this case.

[stebogit]

Sorry @chriserickson, my bad.
I see now the issue and it does look like a bug, thanks for reporting it.
However we (i.e. @rowanwins) are in the middle of a quite substantial rework of the library, so it might take a while until this issue will get addressed.

[stebogit]

@chriserickson hope you don't mind I edited the issue to better highlight just the problem.

[chriserickson]

I started on a PR, but can't get tests to run, can you give me a pointer?
#1468

[stebogit]

Sorry @chriserickson I can't, maybe @rowanwins or @DenisCarriere have some tip for you?

[chriserickson]

It appears to be a bunch of typescript errors, did you happen to look at the output on the PR?

[stebogit]

I don't know typescript, that's why I asked the other guys if they could help.

[chriserickson]

It appears that it is just missing a bunch of type annotations; and is broken in current master. Is there a different branch I should be PRing to that doesn't have the typescript annotations required?

[rowanwins]

Hey @chriserickson

Thanks for the report. contains is a tricky definition and TBH I'm not 100% sure on the correct application in this case, just because other libs get certain results it doesn't always mean they've implemented it correctly. That said I've tried to test our results against shapely (a python GEOS port), I'll need to re-look at the results there.

With PostGIS for example there is ST_Contains and also ST_ContainsProperly. Their doco also contains a link to this blog post which talks about the challenges of the definitions, so far greater minds have struggled with this than mine :)

If you'd like to do any work on this do it on the v7 branch as that branch is typescript-free and is a major overhaul.

Cheers
Rowan

[chriserickson]

I agree that it is a complicated formal definition. However I'd also argue that formal definition should agree with intuition in basic cases. The formal definition listed on that blog post falls short, regardless of its source.

The same problem actually exists on a line-in-polygon. Given a polygon the shape of a U, and a line which begins inside the upper-left side of the U and goes to the upper-right side of the U, what should Contains return?
(False, although currently contains will return true)

A hypothetical question:
If you densify a geometry (add more points without changing its shape), should the result of a contains operation change.
I assert "No".

I assert a more correct formal definition would be, "Geometry A contains Geometry B iff no points of B lie in the exterior of A, and at least one point of the interior of B lies in the interior of A, and no segment of B crosses any segment of A."

Now, I will conceded that projection issues can gray this, as 2 lines may cross in one projection and not in another, but that is a different issue.

[chriserickson]

@rowanwins,
Thanks for the testing info, I rebased and can now run tests. FWIW, I had to add the "esm" module to my NPM environment; package.json didn't pull it down automagically. Not sure if it should have, I'm a little new to the NPM world.

A question:
The linked post mentions that "Polygons do not contain their boundary", meaning that a polygon should not contain itself.

One of the test cases, "PolygonExactSameShape.geojson", tests that contains should return true in this case. (I also happened to have broken this test case with my fix, as the boundaries now intersect, causing it to be false).

Thoughts?

[chriserickson]

@rowanwins
Do you have a timeline of getting v7 published to NPM? I'd really like to be able to pull this down to where we are using it...

Thanks!

[stebogit]

@chriserickson there is a [email protected] version available, would that work for you?

[chriserickson]

@stebogit - that was published before the PR fixing this was merged, so I don't think so.

[chriserickson]

@stebogit - I am sure you guys are busy, but wanted to check again if there was a timeline for a new version with the fix in it.
Thanks!

[rowanwins]

Hey @chriserickson

I'm waiting on a PR to land over here in the next day or two, that will increase the treee-shakability of turfjs - with that landed I'll be able to publish a new version to npm that contains 95% of the modules in a way that shakes well.

So stay tuned, I'll drop you a note when it's published

Cheers
R