Boost logo

Geometry :

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

On 24-9-2013 15:28, Mateusz Loskot wrote:
> On 24 September 2013 14:13, Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]> 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 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
>>> See important notes about boundary.
>> So am I bad at interpretation of the standard? E.g. here:
>> OpenGIS® Implementation Standard for Geographic information - Simple feature
>> access - Part 1: Common architecture, page 38 (even the picture)
>> or here:
>> 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 sounds correct, indeed conforms to OGC SFS 1.2 (page 39):
> Expressed in terms of the DE-9IM:
> a.Within(b) ⇔ [ I(a)∩I(b)≠∅ ∧ I(a)∩E(b)=∅ ∧ B(a)∩E(b)=∅ ] ⇔
> a.Relate(b, “T*F**F***”)
> where I - interior, E - exterior, B - boundary.
>> And e.g. here:
>> 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?
> To avoid further confusion, I'll wait for Barend's clarification (if possible).
> Might be, I don't know about all assumptions for within() in Boost.Geometry,
> perhaps there are differences.

Boost.Geometry should follow the specs here. See my previous email, Adam
is right here.

About my proposed solution, it then should obviously also take the
turn-info into account... The file most documenting the turns is
probably get_turn_info.ppt in doc/other/test_cases (of trunk), where
most (or all) possible situations are clearly visualized.

Besides that you might look at the traverse.cpp unit test, defining
TEST_WITH_SVG. It then creates an SVG showing all turns with turn-info
in the SVG. For example traverse_intersection_11_d.svg (but there are more)

So yes now I completely understand you looking at touch (thanks for the
fix), which is similar but there a turn may only turn at the outside,
while here it may only turn at the inside.

Regards, Barend

Geometry list run by mateusz at