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

Subject: Re: [geometry] within(Poly, Poly)
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-09-26 17:43:45

On 26-9-2013 23:01, Adam Wulkiewicz wrote:
> Barend Gehrels wrote:
>>
>>> I tought that this may be used to get different results from 
>>> get_turns. That it automatically will handle holes with correct 
>>> 'outside' size and will produce e.g. t+xu instead of t+iu. So I 
>>> tried to define holes in reverse order but get_turns give the same 
>>> results.
>>
>> Are you sure? That should not be the case. If holes are defined in 
>> reverse order (that means: clockwise for a clockwise polygon), they 
>> should return different results than holes in correct 
>> (counter-clockwise) order.... Unless the operation is symmetric (of 
>> course).
>
> No, you're right. e.g. in the attached files there is difference m+iu 
> vs m+uu so this works as expected.
>
>>
>>>
>>> So must I handle each special case, analysing the exterior rings, 
>>> polygons inside holes, holes inside holes, etc? Or do you see some 
>>> other, clever way of doing it?
>>
>> Yes, all turn information should be totally independent on segments 
>> being exterior or interior (iff the orientation is correct w.r.t. the 
>> compile-time specified orientation)
>
> Ok so the algorithm complicates, correct me if I'm wrong:
>
> If P1 exterior isn't inside P2 exterior
>     return NOT_WITHIN
> If P2 has holes
>     If P1 exterior is disjoint or only touches holes of P2
>         return WITHIN
>     If holes of P2 which intersects P1 are also inside P1 holes
>         return WITHIN
>     else
>         return NOT_WITHIN

You are right - if there are holes, this must be checked. See also the 
unit-tests for union.cpp (with TEST_WITH_SVG): union_wrapped, 
union_winded, union_within_holes_disjoint, 
union_intersect_holes_disjoint, ...

For touches this is done in "rings_containing", this is probably 
possible here too. That makes it not really complex and because turns 
are OK for all exterior/interior combinations, the holes are not a big 
issue.

For union/intersection, and also for dissolve in intersections, this is 
done in "select_rings" (the dissolve.hpp contains a simple version that 
might do ; the others are in overlay.hpp) They are followed by 
"assign_parents" but that is probably not necessary for this algorithm.

>
> And holes should be reversed before checking because they have 
> different orientation than the exterior ring.

No, we assume correct polygons. And all turn info is correct for holes. 
We don't have to check (besides for things located inside each other 
without intersections).
I don't know if you mean this, but for information: we have a specific 
type for polygons where order is dynamic (both allowed: 
order_undetermined) but that is not yet implemented anywhere.

Regards, Barend