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

Subject: Re: [geometry] within(Poly, Poly)
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-09-26 16:23:30

Hi Adam,

On 26-9-2013 14:37, Adam Wulkiewicz wrote:
> 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.

Right - the undefined polygons can return whatever appropriate. For 
example area is (depending on your viewpoint) correct: the duplicate 
part is counted twice. Also perimeter is correct, counting all of the 
lines (also the crossing part). Also the point-in-polygon is (I did not 
test but I think) correct if we use the winding (=default) strategy, 
because the point is on the right side of all segments (see also my 
previous email about the right side - this is the interior...)

For with poly,poly it will generate turns with "crossing", or other 
intersections which will continue over the lines, so I agree, false will 
be returned. We cannot (at least with current means) distinguish between 
that (we might throw an exception though - if we know)

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

As far as I can see now, testing a point is only necessary if there are 
no turns at all. If there is any turn, they can be examined, there is a 
touching point or a shared border. If there is no turn, the polygons are 
either completely disjoint, or one is inside the other. The can be done 
by testing one point (for multi-polygons this is also true).

> 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
I cannot guarantee this without divining into this deeper, but it is 
probably OK. The "i" is important here - because it is a "within" 
operation, testing the interior and no points in the exterior we would 
act as if we do an intersection. And that "i" should belong to the 
polygon-examined-for-within (so the inner one). Then it is OK. If the 
"i" belongs to the outer one, it is not OK. Similar for "u" but the 
other way round, it should belong to the outer one. This is known - the 
operations are numbered, and (as far as I remember - did not look it up) 
the 0 is for the first one, the 1 is always for the second one (they 
also have segment-identifiers with a source-id which is guaranteed to be 
0 and 1 here)
- e+cc is certainly good, it has both polygons on the right side. Same 
for c+cc.
- ii is also certainly OK, these are situations you don't see often in 
real life, but they always act for intersections, so the "inside", this 
is OK.

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

- uu is normally discarded. But it gives sometimes extra (necessary) 
information and therefore it is still generated. In 2-not-within it 
gives this information: there is one intersection point, uu, nothing 
more -> we know that one is not inside of the other, so we can return false

> 3. operation can't be 'x' (block) (see: '3 *.svg'). Btw, for 
> covered_by() it would be allowed.

- xx means that it is blocked for intersection and union. If so, we can 
return false -> these are two opposite collinear segments
- xi (or ix - the order does not matter) is OK if i belongs to the inner 
one.. I did not check this with a test and they are not yet there, but 
it is probably OK

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

Any crossing will return false indeed.

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

This is a "spike" and officially invalid. Therefore behaviour is 
undefined. However as said before we might reconsider spikes for 
Boost.Geometry.
Block operations can be generated in different situations, the basic 
idea is that they are NOT followed. So ix may ( should) be followed for 
intersection but not for union. And ux should only be followed for a 
union but not for an intersection. xx is never followed. These are 
examples of turns where xx is generated:

(they come from overlay.ppt  which is another useful ppt for these things).

What I mean is actually, that turn-info is based on two pairs of 
segments - it is not only related to spikes or polygons with area zero, 
though there might be a relation (but I have the feeling they might also 
only cross each other...)

>
> What do you think? Have I missed something?

It is a complex thing... We might miss something but this is already 
great work, success.

What I'm a bit worried about is that it seems complexer than the 
implementation for touches. Did we miss something there? We might test 
this more thoroughly.

Regards, Barend