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

Subject: Re: [geometry] within(Poly, Poly)
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-09-26 15:13:04

Hi Adam,

On 26-9-2013 17:15, Adam Wulkiewicz wrote:
> Adam Wulkiewicz wrote:
>> Adam Wulkiewicz wrote:
>>>
>>> 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?
>>>
>> Of course I missed something! Holes. So the external ring must be 
>> analyzed as above but holes must be analyzed separately for thouch 
>> (like in touches()), so no intersection operation, etc. See attachments.
> Another portion of special cases.

Thanks for all your work and clear attachments! I start with your last mail.

>
> A question: in OGC standard the exterior ring and holes must have 
> different point order. This way the same algorithms probably may work 
> for exterior ring and the the holes because 'automatically' the 
> 'outside' is set properly. Is this also true for BG?

Sure! If exterior ring is cw, all interior rings must be ccw. If that is 
OK all intersections & unions & differences work correctly. For all 
turns, this then is automatically OK. A good thing to always realize is 
that for a clockwise polygon, the interior is always on the right side 
(both for the exterior ring and for the interior rings). So all segments 
are directed and they have the "occupied" area on the right side.

> I tought that this may be used to get different results from 
> get_turns. That it automatically will handle holes with correct 
> 'outside' size and will produce e.g. t+xu instead of t+iu. So I tried 
> to define holes in reverse order but get_turns give the same results.

Are you sure? That should not be the case. If holes are defined in 
reverse order (that means: clockwise for a clockwise polygon), they 
should return different results than holes in correct 
(counter-clockwise) order.... Unless the operation is symmetric (of course).

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

Regards, Barend