Hi Adam,

On 26-9-2013 14:37, Adam Wulkiewicz wrote:

Barend Gehrels wrote:

On 25-9-2013 22:56, Mateusz Loskot wrote:

On 25 September 2013 19:34, Adam Wulkiewicz <adam.wulkiewicz@gmail.com> wrote:

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?

According to OGC specification, the result is undefined.
In other words: self-intersecting polygons are not valid and therefore
their spatial relation can not be determined.

There was somewhat related discussion, see the thread
"[ggl] is_simple is_valid" started by Barend:
http://lists.boost.org/geometry/2009/10/index.php

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

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

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

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

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

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.

- 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 return false

3. 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

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.

Any crossing will return false indeed.

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?

This is a "spike" and officially invalid. Therefore behaviour is undefined. However as said before we might reconsider spikes for Boost.Geometry.
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 things).

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.

Regards, Barend