Geometry Boost List: Re: [geometry] within(Poly, Poly)

Subject: Re: [geometry] within(Poly, Poly)
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-09-24 09:27:28

Hi Adam,

On 24-9-2013 15:13, Adam Wulkiewicz wrote:
> Mateusz Loskot wrote:
>> On 24 September 2013 13:44, Barend Gehrels <barend_at_[hidden]> wrote:
>>> On 24-9-2013 1:22, Adam Wulkiewicz wrote:
>>>> I'm playing with the implementation of missing boolean operations.
>>>> Currently I'm implementing within(Poly, Poly).
>>>
>>> Great!
>> Indeed!
>>
>>>> I figured out that I'll check if there is some point of the first 
>>>> polygon
>>>> within the second one using detail::within::point_in_polygon and 
>>>> then check
>>>> if the first polygon's exterior ring doesn't overlap the second 
>>>> polygon
>>>> rings. I can't use detail::disjoint::disjoint_linear because this will
>>>> return false for polygons which boundries overlap. And within() should
>>>> return true also for those cases. I thought I'll use
>>>> boost::geometry::get_turns, the same like it's used in the 
>>>> implementation of
>>>> the touches() algorithm. Basically I need to detect if the 
>>>> boundries crosses
>>>> or just touches itself. Is it possible to use get_turns this way?
>>>
>>> Yes. One detail, in case you are not aware of this: within should 
>>> return
>>> false even if the whole polygon is more or less inside, touching 
>>> only the
>>> border from the inside. So there should be no intersections at all.
>> I'd also point to PostGIS documentation (OGC specification may be a
>> bit tricky to grasp it all),
>> where the within/contains relations is well explained and visualised
>>
>> http://postgis.net/docs/manual-2.0/ST_Within.html
>> http://postgis.net/docs/manual-2.0/ST_Contains.html
>>
>> See important notes about boundary.
>>
>
> So am I bad at interpretation of the standard? 

Probably I was bad... Thanks for the wiki-page, I did not know of its 
existance.

> E.g. here:
> OpenGIS® Implementation Standard for Geographic information - Simple 
> feature access - Part 1: Common architecture, page 38 (even the picture)
> or here:
> http://en.wikipedia.org/wiki/DE-9IM
> Within is defined as an operation which return true if there is at 
> least one point of the interior of the first geometry in the interior 
> of the second one and the interior and boundry of the first geometry 
> isn't in the exterior of the second geometry. But boundries may 
> overlap. It just must have at least one point in the interior of the 
> second geometry. Covered by musn't, may be 'wholly contained' in the 
> boundry.

This is new for me. I always thought that within was fully inside, I did 
not look it up this morning. But maybe this is only for point-in-polygon...

I see also there: (1) /a/ is within /b/, /a/ lies in the interior of /b/.
And also (contains): /(2) b/ is within /a/. Geometry /b/ lies in the 
interior of /a/. Another definition: "/a/ 'contains' /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/"

contains is reversal of within.

But indeed, (2) says there may be someting on the boundary.

More here:
http://lin-ear-th-inking.blogspot.nl/2007/06/subtleties-of-ogc-covers-spatial.html

>
> And e.g. here:
>
> http://postgis.net/docs/manual-2.0/ST_Within.html
>
> states: It is a given that if ST_Within(A,B) is true and 
> ST_Within(B,A) is true, then the two geometries are considered 
> spatially equal.
>
> If within() returns true only if boundries don't overlap, how those 
> both functions may return true at the same time?
> Another thing is that this can't work for 0-sized degenerated polygons 
> because there won't be any interior.
>
> Is my reasoning wrong at some point?
>

No, you are completely right.

Thanks, Barend