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 08:37:14

Barend Gehrels wrote:
> On 25-9-2013 22:56, Mateusz Loskot wrote:
>> On 25 September 2013 19:34, Adam Wulkiewicz 
>> <adam.wulkiewicz_at_[hidden]> wrote:
>>>
>>> What do think we should do with self-intersecting polygons? This is 
>>> slightly modified traverse_intersection_52:
>>>
>>>
>>>
>>> Is the blue polygon within the green one?
>> According to OGC specification, the result is undefined.
>> In other words: self-intersecting polygons are not valid and therefore
>> their spatial relation can not be determined.
>>
>> There was somewhat related discussion, see the thread
>> "[ggl] is_simple is_valid" started by Barend:
>> http://lists.boost.org/geometry/2009/10/index.php
>
> Ha, did not remember that, thanks.
>
> I agree, polygons self-intersecting like in Adam's picture will result 
> in non-defined behaviour. By design we check validity not beforehand, 
> before each operation. We check it afterwards if the intersection 
> fails, one of the reasons to do that was, if I remember correctly, to 
> report it to the user. Also to avoid lots of reports of failing 
> intersections...
>
> Besides validity on self-crossings, we could consider if spikes can be 
> handled correctly, there are several cases with this. Sometimes also 
> still generated by our library (we have to consider that separately), 
> but they might be solveable.
>

Thanks for the info and pictures. So self intersecting polygons are 
undefined. It's ok for me since it would be a lot harder to handle them 
properly. Though I feel that for my example within() should return true, 
for now probably false will be returned.

I think I now understand turns and am ready to implement within(). This 
is what I figured out about it (I'm attaching the SVGs, each one's name 
starts with the corresponding point number):

0. Point 0 of the first polygon should lie in the interior or on the 
boundry of the second polygon. This probably will be enough in the 
conection with the points below.
     Or more explicit: no point of the first polygon should lie in the 
exterior of the second polygon.
     Or maybe all points should be tested if they're inside (interior or 
boundry) the second polygon?
1. those combinations of methods and operations are ok:
     a) t+iu, m+iu,
     b) t+ii, probably m+ii, ('1 within t,ii.svg')
     c) c+cc, c+iu,
     d) e+cc, e+iu
2. those are potentially ok:
     a) t+uu, m+uu (see: '2 within t,uu.svg', '2 not within t,uu.svg', 
'2 within m,uu.svg')
     b) t+cc, m+cc (see: '2 [not] within (t|m),cc.svg')
     So I think that for those I also need to check if points of 
touching segments are inside. But is it sufficient? Probably yes 
assuming the 'no crossing' policy (point 4) is used.
3. operation can't be 'x' (block) (see: '3 *.svg'). Btw, for 
covered_by() it would be allowed.
4. method can't be 'i' (cross) because otherwise it won't be possible to 
simply distinguish between '4 within si i.svg' and '4 not within si 
i.svg' (number of crossings per segment isn't enough). So for self 
intersecting polygons within() will return false.
5. area of the first (both?) polygon must be > 0 (see: '5 *.svg') 
because if area is 0 there is no interior and within() should return 
false. Btw within(Linestring, Polygon) should return true in this case.
If both areas are = 0 'x' (block) operation is generated (see: '3 
*.svg'), would it be always the case?

What do you think? Have I missed something?

Regards,
Adam