Subject: Re: [geometry] within(Poly, Poly)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-09-26 11:15:30
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.
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? 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.
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?
Geometry list run by mateusz at loskot.net