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

Subject: Re: [geometry] within(Poly, Poly)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-09-27 09:45:02

Barend Gehrels wrote:
> On 26-9-2013 23:01, Adam Wulkiewicz wrote:
>> Barend Gehrels wrote:
>>
>>>
>>>>
>>>> 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.
>

Ok now I'm checking special cases and I think that my previous 
assumtions wasn't fully ok. Correct me if I'm wrong.

Of course method 'i' and operation 'xx' is automatic fail.

Only if we have operation 'u' we must worry about
'uu' - touches from the outside
'ux' - is outside
'ui' - the curve potentially goes to the other side of the second curve.

All other combination with operations 'i' and 'c|c' are ok, also t+cc, m+cc?

So additionally we should check if points of segments for which u|i was 
generated are inside the polygon. This would be ok for '[not] within 
*.svg', '(2-5).svg' but would fail for '1.svg'. However in those cases 
there would be uu there so it might be used as well. So I guess if there 
are some 'u|i' operations we should check if all (or some) points are 
inside. If there is some 'u|u' we should check if on the same point 
there are no other intersections to detect cases like 'ok_uu.svg'.

Of course if there are no intersections, only one point may be tested if 
it's inside.

What do you think?

Regards,
Adam