Boost logo

Geometry :

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.


Geometry list run by mateusz at