On 26-9-2013 14:37, Adam Wulkiewicz wrote:
On 25-9-2013 22:56, Mateusz Loskot wrote:
On 25 September 2013 19:34, Adam
Wulkiewicz <firstname.lastname@example.org> wrote:
According to OGC specification, the result is undefined.
What do think we should do with self-intersecting polygons?
This is slightly modified traverse_intersection_52:
Is the blue polygon within the green one?
In other words: self-intersecting polygons are not valid and
their spatial relation can not be determined.
There was somewhat related discussion, see the thread
"[ggl] is_simple is_valid" started by Barend:
Ha, did not remember that, thanks.
I agree, polygons self-intersecting like in Adam's picture will
result in non-defined behaviour. By design we check validity not
beforehand, before each operation. We check it afterwards if the
intersection fails, one of the reasons to do that was, if I
remember correctly, to report it to the user. Also to avoid lots
of reports of failing intersections...
Besides validity on self-crossings, we could consider if spikes
can be handled correctly, there are several cases with this.
Sometimes also still generated by our library (we have to
consider that separately), but they might be solveable.
Thanks for the info and pictures. So self intersecting polygons
are undefined. It's ok for me since it would be a lot harder to
handle them properly. Though I feel that for my example within()
should return true, for now probably false will be returned.
Right - the undefined polygons can return whatever appropriate. For
example area is (depending on your viewpoint) correct: the duplicate
part is counted twice. Also perimeter is correct, counting all of
the lines (also the crossing part). Also the point-in-polygon is (I
did not test but I think) correct if we use the winding (=default)
strategy, because the point is on the right side of all segments
(see also my previous email about the right side - this is the
For with poly,poly it will generate turns with "crossing", or other
intersections which will continue over the lines, so I agree, false
will be returned. We cannot (at least with current means)
distinguish between that (we might throw an exception though - if we
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?
As far as I can see now, testing a point is only necessary if there
are no turns at all. If there is any turn, they can be examined,
there is a touching point or a shared border. If there is no turn,
the polygons are either completely disjoint, or one is inside the
other. The can be done by testing one point (for multi-polygons this
is also true).
those combinations of methods and operations are ok:
I cannot guarantee this without divining into this deeper, but it is
probably OK. The "i" is important here - because it is a "within"
operation, testing the interior and no points in the exterior we
would act as if we do an intersection. And that "i" should belong to
the polygon-examined-for-within (so the inner one). Then it is OK.
If the "i" belongs to the outer one, it is not OK. Similar for "u"
but the other way round, it should belong to the outer one. This is
known - the operations are numbered, and (as far as I remember - did
not look it up) the 0 is for the first one, the 1 is always for the
second one (they also have segment-identifiers with a source-id
which is guaranteed to be 0 and 1 here)
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
- e+cc is certainly good, it has both polygons on the right side.
Same for c+cc.
- ii is also certainly OK, these are situations you don't see often
in real life, but they always act for intersections, so the
"inside", this is OK.
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
operation can't be 'x' (block) (see: '3 *.svg'). Btw, for
covered_by() it would be allowed.
- xx means that it is blocked for intersection and union. If so, we
can return false -> these are two opposite collinear segments
- xi (or ix - the order does not matter) is OK if i belongs to the
inner one.. I did not check this with a test and they are not yet
there, but it is probably OK
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.
Any crossing will return false indeed.
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?
This is a "spike" and officially invalid. Therefore behaviour is
undefined. However as said before we might reconsider spikes for
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
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...)
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.