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

Subject: Re: [geometry] within(Poly, Poly)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-10-09 13:49:57

Adam Wulkiewicz wrote:
>
> Ok now I'm checking special cases and I think that my previous 
> assumtions wasn't fully ok. Correct me if I'm wrong.
>
> Of course method 'i' and operation 'xx' is automatic fail.
>
> Only if we have operation 'u' we must worry about
> 'uu' - touches from the outside
> 'ux' - is outside
> 'ui' - the curve potentially goes to the other side of the second curve.
>
> All other combination with operations 'i' and 'c|c' are ok, also t+cc, 
> m+cc?
>
> So additionally we should check if points of segments for which u|i 
> was generated are inside the polygon. This would be ok for '[not] 
> within *.svg', '(2-5).svg' but would fail for '1.svg'. However in 
> those cases there would be uu there so it might be used as well. So I 
> guess if there are some 'u|i' operations we should check if all (or 
> some) points are inside. If there is some 'u|u' we should check if on 
> the same point there are no other intersections to detect cases like 
> 'ok_uu.svg'.
>
> Of course if there are no intersections, only one point may be tested 
> if it's inside.
>
> What do you think?
>

  FYI, I have a working version. It's slightly different algorithm than 
the one desceibed above. Now I'm testing Multipolygons and invalid 
Geometries and it seems that for self-touching points I also need to 
check if intersection points are duplicated, e.g. like on the attached 
examples. Some of those Geometries aren't valid according to the OGC 
standard, but I'd like to support those cases because I feel that the 
result should be consistent with similar cases where valid Geometries 
are involved. They may be invalid e.g. because of some numerical errors.
So, intersection/crossing, t+ui, etc. for some cases isn't an automatic 
fail (e.g. for aLinestring going through a touch point of two Polygons 
of a MultiPolygon). Or maybe in this particular case within() should 
return FALSE? Also u/i where union operation source_index is set for the 
first Geometry (it goes to the outside of the second one) isn't 
automatic fail, sometimes - for colinear and equal segments and for the 
last point of a Linestring it's ok. So there is a lot of special cases.

Regards,
Adam