Intersection between polygons as line Clipper

Question

I'm trying to use the Clipper C++ library to implement an is_bordering function, as shown below.

bool is_bordering(Path p1, Path p2) {

    Paths solutions;
    Clipper c;

    // execute intersection on paths
    c.AddPath(p1, ptSubject, true);
    c.AddPath(p2, ptClip, true);
    c.Execute(ctIntersection, solutions, pftNonZero);

    return (solutions.size() > 0); // the paths share edges
}


int main() {
    Path p1, p2;
    p1 << IntPoint(0,0) << IntPoint(1,0) << IntPoint(0,1) << IntPoint(0,0);
    p2 << IntPoint(1,0) << IntPoint(1,1) << IntPoint(0,1) << IntPoint(1,0);
    cout << is_bordering(p1, p2) << endl;
}

I thought that when two bordering polygons were tested with ctIntersection the result would contain the bordering edges, but for me this returns false. What I expect from the above would be the following, with green representing the solutions Paths.

How do I get this function working (with the Clipper library)?

Suggestion: Your paths look like open polylines to me. Is there any change if you make your paths closed polygons? — acraig5075, Mar 03 '20 at 06:51

Laszlo · Answer 1 · 2020-03-18T00:29:55.397

0

The polygons in your example are not intersecting, so the function is_bordering() is returning 0 as expected. The union of adjacent polygons will be a single polygon, so you could test for that too:

#include "clipper.hpp"
#include <iostream>

using namespace std;
using namespace ClipperLib;

bool is_bordering(Path p1, Path p2) {
   Paths _intersection, _union;

   Clipper c;
   c.AddPath(p1, ptSubject, true);
   c.AddPath(p2, ptClip, true);
   c.Execute(ctIntersection, _intersection, pftNonZero  );
   c.Execute(ctUnion, _union, pftNonZero);
   return (_intersection.size() > 0 || _union.size() < 2);      
}


int main() {
   Path p1, p2;
   cInt I = 10;
   p1 << IntPoint(0, 0) << IntPoint(I, 0) << IntPoint(0, I) << IntPoint(0, 0);
   p2 << IntPoint(I, 0) << IntPoint(I, I) << IntPoint(0, I) << IntPoint(I, 0);

   cout << is_bordering(p1, p2) << endl;
}

This works only for the case when one polygon is not entirely inside the other.

edited Mar 18 '20 at 00:29

answered Mar 17 '20 at 23:36

Laszlo

769
9
19

This unfortunately doesn't work for me, because a polygon can be entirely inside another with 0 edges bordering and return true. – k-a-v Mar 17 '20 at 23:46
1

Yes, you're right. How should we check for that condition? ( We could test for the union or the intersection being equal to any of the polygons and the two polygons are not identical.) – Laszlo Mar 18 '20 at 00:06
I tried doing something similar this, where I checked the `Union` to see if it was a single polygon, but I also ended up checking the `xor` to see if it created holes in the result (meaning one is entirely inside the other). Sadly this doesn't work on some edge cases that I can only explain through a drawing, and it makes two calls to Clipper, which I want to avoid (because of large polygons and speed). – k-a-v Mar 18 '20 at 00:11
1

Yes, indeed. I found that if one polygon is entirely inside another, one cannot distinguish between the cases when they are bordering and when they are not. I think a new algorithm needs to be added for this purpose, that checks the vertices pairwise. – Laszlo Mar 18 '20 at 00:24
The `xor` trick does distinguish these because if they border it won't make a hole, but it fails in certain circumstances where one is not outside the other and they border but their `xor` still create a hole – k-a-v Mar 18 '20 at 03:12
Exactly. One gets two polygons back. One would need to check whether or not the hole is 'bordering' the outside polygon, and then we are back at square one. – Laszlo Mar 18 '20 at 15:08

Intersection between polygons as line Clipper

1 Answers1