Barend Gehrels wrote:

...

On 26-9-2013 23:01, Adam Wulkiewicz wrote:

...

Barend Gehrels wrote:

...

...

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?

Yes, all turn information should be totally independent on segments being exterior or interior (iff the orientation is correct w.r.t. the compile-time specified orientation)

Ok so the algorithm complicates, correct me if I'm wrong:

If P1 exterior isn't inside P2 exterior return NOT_WITHIN If P2 has holes If P1 exterior is disjoint or only touches holes of P2 return WITHIN If holes of P2 which intersects P1 are also inside P1 holes return WITHIN else return NOT_WITHIN

You are right - if there are holes, this must be checked. See also the unit-tests for union.cpp (with TEST_WITH_SVG): union_wrapped, union_winded, union_within_holes_disjoint, union_intersect_holes_disjoint, ...

For touches this is done in "rings_containing", this is probably possible here too. That makes it not really complex and because turns are OK for all exterior/interior combinations, the holes are not a big issue.

For union/intersection, and also for dissolve in intersections, this is done in "select_rings" (the dissolve.hpp contains a simple version that might do ; the others are in overlay.hpp) They are followed by "assign_parents" but that is probably not necessary for this algorithm.

...

And holes should be reversed before checking because they have different orientation than the exterior ring.

No, we assume correct polygons. And all turn info is correct for holes. We don't have to check (besides for things located inside each other without intersections). I don't know if you mean this, but for information: we have a specific type for polygons where order is dynamic (both allowed: order_undetermined) but that is not yet implemented anywhere.

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.

? xx fails but i is ok for turns including on holes?

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.

? yes but this all means failure for all turns including holes? (except ui, sometimes)

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?

sorry I don't understand it. As I said before, holes are processed correctly automatically for any turn. You don't have to process any turn special for any hole. So i is intersection, this is Ok. But u is union, then the within should fail. The interior is really the inside of a polygon, not the hole. That is outside.... Or maybe I did not understand your mail. I never handle holes separately in any turn in the whole traverse process. As long as the direction is ccw (for a cw polygon), it all goes ok. The interior is always on the right side. Of course, as we discussed before, if a hole does not have any turnpoints, we should check it separately and differently, not with turn info Regards, Barend Sent from iPad. Barend Gehrels www.barendgehrels