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

Subject: Re: [geometry] within(Poly, Poly)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-09-26 17:01:06

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

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

Regards,
Adam