Re: [Boost-users] [geometry] within(Poly, Poly)

Subject: Re: [Boost-users] [geometry] within(Poly, Poly)
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-09-27 10:08:03

> 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.

? xx fails but i is ok for turns including on holes?

> 
> 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.

? yes but this all means failure for all turns including holes? (except ui, sometimes)

> 
> 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?
> 

sorry I don't understand it. As I said before, holes are processed correctly automatically for any turn. You don't have to process any turn special for any hole. So i is intersection, this is Ok. But u is union, then the within should fail. The interior is really the inside of a polygon, not the hole. That is outside....

Or maybe I did not understand your mail.

I never handle holes separately in any turn in the whole traverse process. As long as the direction is ccw (for a cw polygon), it all goes ok. The interior is always on the right side.

Of course, as we discussed before, if a hole does not have any turnpoints, we should check it separately and differently, not with turn info

Regards, Barend

Sent from iPad.
Barend Gehrels
www.barendgehrels