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

Subject: Re: [geometry] within(Poly, Poly)
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-09-26 18:02:41

Hi,

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

That is right but I wrote (at least I meant, let met add "only"): if 
there is *only* one intersection point, uu, nothing more... If there is 
anything more than uu, we can discard it, its information is useless.

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

Spikes are not in the official spec, as far as I know.

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

Yes. No within for ux, only touch. For ix only within, no touch. Within 
is more complex than touch, because it is not symmetrical. So you have 
to analyse more of which operation is caused by which source, indeed. 
For touch that was not necessary. Therefore touch is simpler.

> Also if both blue segments on 2 left pictures were on the left side of 
> the green segment the turn would be uu. 

Yes.

> The opposite situation on the right would produce ii. 

Yes

> And if the blue curve went on the other side the turn would be ui. Is 
> this correct?

Yes. You got it ;-)

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

Not really - see my last answer about this, which apparently crossed 
your post.

Regards, Barend