Merging touching polygons giving wrong result

Question

I'm trying to write a piece of code that given a list of polygons (defined as a list of lists of IntPoints) checks if any of them touch and if so merge them into a single polygon. In order to do this I have already tried the following two methods:

List<List<IntPoint>> output=new List<List<IntPoint>>();
output = Clipper.SimplifyPolygons(input,PolyFillType.pftPositive);

and

Clipper c = new Clipper();
c.AddPaths(input, PolyType.ptClip, true);
c.Execute(ClipType.ctUnion, output);

Now both of these merge the polygons together quite easily however they are a bit overzelous as any polygon open spaces are ignored and open areas are simply combined into a single polygon, meaning that something like this:

happens. Now this is obviously wrong as these two polygons do not touch each other. The same result occurs with both methods. The result would be the same as the input. Any idea how to fix this? The sollution does not have to use the clipper library (I'm not married to it) but I do need something that uses polygons that are defined by a list of points input is a List> where an Intpoint is just a struct containing an x and a y.

Edit I notice that this problem also occurs when there is no polygon inside of the other polygon, so the solution is always "filled" edit edit: here is also an example of what input might be like

input[0][0]
{ClipperLib.IntPoint}
    X: -724
    Y: -472
input[0][1]
{ClipperLib.IntPoint}
    X: 428
    Y: -472
input[0][2]
{ClipperLib.IntPoint}
    X: 428
    Y: -472
  input[0][3]
{ClipperLib.IntPoint}
    X: 428
    Y: 632
input[0][4]
{ClipperLib.IntPoint}
    X: 428
    Y: 632
input[0][5]
{ClipperLib.IntPoint}
    X: -724
    Y: 632
input[0][6]
{ClipperLib.IntPoint}
    X: -724
    Y: 632
input[0][7]
{ClipperLib.IntPoint}
    X: -724
    Y: -472
input[0][8]
{ClipperLib.IntPoint}
    X: -88
    Y: -218
input[0][9]
{ClipperLib.IntPoint}
    X: -107
    Y: -218
input[0][10]
{ClipperLib.IntPoint}
    X: -107
    Y: -218
input[0][11]
{ClipperLib.IntPoint}
    X: -107
    Y: -209
input[0][12]
{ClipperLib.IntPoint}
    X: -107
    Y: -209
input[0][13]
{ClipperLib.IntPoint}
    X: -320
    Y: -172
input[0][14]
{ClipperLib.IntPoint}
    X: -320
    Y: -172
input[0][15]
{ClipperLib.IntPoint}
    X: -320
    Y: 132
input[0][16]
{ClipperLib.IntPoint}
    X: -320
    Y: 132
input[0][17]
{ClipperLib.IntPoint}
    X: -88
    Y: 173
input[0][18]
{ClipperLib.IntPoint}
    X: -88
    Y: 173
input[0][19]
{ClipperLib.IntPoint}
    X: -88
    Y: -201
input[0][20]
{ClipperLib.IntPoint}
    X: -88
    Y: -201
input[0][21]
{ClipperLib.IntPoint}
    X: -88
    Y: -218

The input this descripes is a square with a hole cut into it.

Answer 1

There needs to be a PolyType.ptSubject(missing from your code) and a PolyType.ptClip added to your Clipper before execution. Also you need to select the ClipType that will produce the result you want, as shown below:

    private void Form1_Paint(object sender, PaintEventArgs e)
    {
        clip = new List<List<IntPoint>>();
        clip.Add(pol2);

        input = new List<List<IntPoint>>();
        input.Add(pol1);

        output = new List<List<IntPoint>>();

        Clipper c = new Clipper();
        c.AddPaths(input, PolyType.ptSubject, true);
        c.AddPaths(clip, PolyType.ptClip, true);
        c.Execute(clipType, output);

        DrawPolygon(output, e.Graphics, Pens.Red);
    }

XOR:

Union:

Intersection:

Difference: pol1 - pol2

Difference: pol2 - pol1

Answer 2

It looks like the library needs some combination of the PolyTree version of the Execute method, and some more complicated build up of the polygons in the Clipper object, that takes into account whether the input contains holes.

It doesn't look like the green polygon with the hole is represented as just an array of points, it should be a PolyTree with an outer polygon and an inner hole polygon.

Answer 3

Another thing you could look into is the Spatial datatypes introduced in SQL Server 2008 when handling geometric shapes.

https://msdn.microsoft.com/en-us/library/microsoft.sqlserver.types.sqlgeometry.stintersection.aspx

Geography is same URL but with sqlgeography instead of sqlgeometry

You can use the .STIntersects() == 1 and .STIntersection(AnotherShape) to retrieve the intersections. There are also other methods to give you the same results as above.

The benefit to this is that if you incorporate this with your database, you can utilize spatial indexes to make it even faster.

https://msdn.microsoft.com/en-us/library/bb934196.aspx