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:45:40

Barend Gehrels wrote:
> 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...)
>

Yes point in polygon works for self intersecting polygons.

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

Ok.

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

Yes, you're right.

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

Ok, thanks.

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

I must disagree here, see e.g. attached traverse_intersection_52. The 
containing polygon may touch itself and the contained polygon may be 
touching the first one in the same point but still be within it.

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

Ok will have that in mind.

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

AFAIU the difference between Within() and CoveredBy() is that the second 
one for spikes should refurn TRUE. Or am I wrong? According to 
en.wikipedia.org/wiki/DE-9IM only boundries my overlap for CoveredBy(). 
If what I'm saying is true we should probably support them, right?

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

So those are two ux and two ix. Also if both blue segments on 2 left 
pictures were on the left side of the green segment the turn would be 
uu. The opposite situation on the right would produce ii. And if the 
blue curve went on the other side the turn would be ui. Is this correct?

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

Yes and it's even more complex because I have a feeling that I should 
check relations between P1 exterior with P2 exterior, P1 exterior with 
P2 interior and P1 interiors with P2 interiors (see my second email). 
And for those cases different turns must be analyzed.

Regards,
Adam