Using result of Clipper polygon union for Google Earth KML with inner boundaries

Question

I want to merge polygons into one area that can have holes. Clipper can do this, however when I use the two resulting polygons in Google Earth the problem is that Google earth treats those polygons separately and just pust them over each other. In KML there is the possibility to create OuterBoundary and InnerBoundary elements for a polygon. The problem is is that with the Clipper result how do you know what is inner and what is outer boundary. Another thing to mention: Even if it can be somehow determined, in the actual Clipper union call I use serveral thousand circle polygons. So there are multiple separate areas with holes. After merge:

Here is the code with four simple shapes:

/* 
0     -------
9     |     |
8     |  2  |
7 -------   |-----
6 |     |----    |
5 |  1  |xx|  3  |  
4 |     |--|     |
3 -------  -------
2     |  4  |
1     |     |
0     -------
  0123456789012345             
*/

IntPolygons polygons = new IntPolygons();
// 1
polygons.Add(new IntPolygon{
    new IntPoint { X = 0, Y = 3 },
    new IntPoint { X = 6, Y = 3 },
    new IntPoint { X = 6, Y = 7 },
    new IntPoint { X = 0, Y = 7 }
});

// 2
polygons.Add(new IntPolygon{
    new IntPoint { X = 4, Y = 6 },
    new IntPoint { X = 10, Y = 6 },
    new IntPoint { X = 10, Y = 10 },
    new IntPoint { X = 4, Y = 10 }
});

// 3
polygons.Add(new IntPolygon{
    new IntPoint { X = 9, Y = 3 },
    new IntPoint { X = 15, Y = 3 },
    new IntPoint { X = 15, Y = 7 },
    new IntPoint { X = 9, Y = 7 }
});

// 4
polygons.Add(new IntPolygon{
    new IntPoint { X = 4, Y = 0 },
    new IntPoint { X = 10, Y = 0 },
    new IntPoint { X = 10, Y = 4},
    new IntPoint { X = 4, Y = 4 }
});

Clipper clipper = new Clipper();
foreach (var polygon in polygons)
{
    clipper.AddPath(polygon, PolyType.ptSubject, true);
}

IntPolygons mergedPolygons = new IntPolygons();

clipper.Execute(ClipType.ctUnion, mergedPolygons,
    PolyFillType.pftNonZero, PolyFillType.pftNonZero);

for (int i = 0; i < mergedPolygons.Count; i++)
{
    Console.WriteLine("polygon " + (i + 1));
    foreach (var point in mergedPolygons[i])
    {
        Console.WriteLine("X: " + point.X + "\t\t Y: " + point.Y);
    }
}

// Result:
//polygon 1
//X: 10            Y: 3
//X: 15            Y: 3
//X: 15            Y: 7
//X: 10            Y: 7
//X: 10            Y: 10
//X: 4             Y: 10
//X: 4             Y: 7
//X: 0             Y: 7
//X: 0             Y: 3
//X: 4             Y: 3
//X: 4             Y: 0
//X: 10            Y: 0

//polygon 2
//X: 6             Y: 4
//X: 6             Y: 6
//X: 9             Y: 6
//X: 9             Y: 4

// The second polygon is the inner boundary
/* 
0              
9                   
8               
7                
6       x  x        
5                 
4       x  x        
3                  
2                    
1                   
0                   
  0123456789012345             
*/

Update: In KML there are always two sets of polygon lists, OuterBoundaries and InnerBoundaries. I managed to recursively parse the polygons and check for each outermost polygon if it has inner polygons. The outermost inner polygons are the InnerBoundary. All other inner polygons are starting as OuterBoundary polygons again. I will post the code as soon as I figured out some issues with very large sets of polygons that.

Answer 1

I basically used a recursive method to go through all nested polygon. OuterBoundary and InnerBoundary elements alternate. I'm sure there is still room for improvement, but the result seems to be the same as with QGIS export (which I found out about afterwards). There are issues with unfilled polygons when I use complex data. I added a separate question about this in the GIS StackExchange page:

 // A class to hold the inner polygons
 public class HierarchicalPolygon
    {
        private Polygon _polygon;
        private List<HierarchicalPolygon> _innerPolygons;

        public HierarchicalPolygon(Polygon polygon)
        {
            _polygon = polygon;
        }

        public Polygon MainPolygon { get
            {
                return _polygon;
            }
            set
            {
                _polygon = value;
            }
        }


        public List<HierarchicalPolygon> InnerPolygons
        {
            get
            {
                return _innerPolygons;
            }
            set
            {
                _innerPolygons = value;
            }
        }

    }

public class PolygonHelper
{
    public static List<HierarchicalPolygon> GeneratePolygonHierachy(Polygons polygons)
        {
            // Step 1: get polygons that have no enclosing polygons
            var outerPolygons = new List<HierarchicalPolygon>();
            foreach (var polygon in polygons)
            {
                var enclosingPolygon = FindEnclosingPolygon((Polygon)polygon, polygons);
                if (enclosingPolygon == null)
                {
                    outerPolygons.Add(new HierarchicalPolygon((Polygon)polygon));
                }
            }

            // Step 2: recursively go through all nested polygons
            // Only two levels are allowed in KML. For example 
            //  OuterBoundary: country polygon 
            //  InnerBoundary: lake polygon
            //  OuterBoundary: island in lake polygon
            var polygonHierarchy = new List<HierarchicalPolygon>();
            foreach (var polygon in outerPolygons)
            {
                ParsePolygonRecursively(polygon, polygonHierarchy, polygons, true);
            }

            return polygonHierarchy;
        }

        private static void ParsePolygonRecursively(HierarchicalPolygon polygonToProcess, List<HierarchicalPolygon> mainList, Polygons allPolygons, bool currentIsOuterBoundary)
        {
            var innerPolygons = FindInnerPolygons(polygonToProcess.MainPolygon, allPolygons);

            if (currentIsOuterBoundary)
            {
                mainList.Add(polygonToProcess);

                // If OuterBoundary then add the nesteed Polygons the the current polygon
                if (innerPolygons != null && innerPolygons.Count > 0)
                {
                    polygonToProcess.InnerPolygons = new List<HierarchicalPolygon>();
                    foreach (var innerPolygon in innerPolygons)
                    {
                        var newPolygon = new HierarchicalPolygon((Polygon)innerPolygon);

                        // Not all inner polygons can be added, because they may be nested inside each other
                        // Adding of all inner polygons would only be possible, if the would not be contained in each other.
                        var enclosingPolygon = FindEnclosingPolygon((Polygon)innerPolygon, innerPolygons);

                        if (enclosingPolygon == null || enclosingPolygon.Count == 0)
                        {
                            polygonToProcess.InnerPolygons.Add(newPolygon);
                            ParsePolygonRecursively(new HierarchicalPolygon((Polygon)innerPolygon), mainList, allPolygons, false);

                            // don't break there could be multiple inner polygons that have again inner polygons
                            //break;
                        }
                    }
                }
            }
            else
            {
                // If InnerBoundary then don't add another layer but start at the OuterBoundary again
                foreach (var innerPolygon in innerPolygons)
                {
                    var enclosingPolygon = FindEnclosingPolygon((Polygon)innerPolygon, innerPolygons);

                    if (enclosingPolygon == null || enclosingPolygon.Count == 0)
                    {
                        ParsePolygonRecursively(new HierarchicalPolygon((Polygon)innerPolygon), mainList, allPolygons, true);
                    }
                }
            }
        }

        /// <summary>
        /// Uses IsPointInPolygon Method to check a points of a polygon to all other polygons
        /// </summary>
        /// <param name="insidePolygon"></param>
        /// <param name="polygonList"></param>
        /// <returns></returns>
        public static Polygon FindEnclosingPolygon(Polygon insidePolygon, Polygons polygonList)
        {
            //bool isInside = false;
            foreach (var polygon in polygonList)
            {
                int insidePointCount = 0;

                foreach (var insidePoint in insidePolygon)
                {
                    if (IsPointInPolygon(polygon, insidePoint))
                    {
                        insidePointCount += 1;
                    }
                    else
                    {
                        break;
                    }
                }

                if (insidePointCount == insidePolygon.Count)
                {
                    return (Polygon)polygon;
                }
            }

            return null;
        }

    /// <summary>
    /// Uses IsPointInPolygon Method to check a points of a polygon to all other polygons
    /// </summary>
    /// <param name="insidePolygon"></param>
    /// <param name="polygonList"></param>
    /// <returns></returns>
    public static Polygons FindInnerPolygons(Polygon parentPolygon, Polygons polygonList)
    {
        var innerPolygons = new Polygons();

        foreach (var polygon in polygonList)
        {
            int insidePointCount = 0;

            foreach (var point in polygon)
            {
                if (IsPointInPolygon(parentPolygon, point))
                {
                    insidePointCount += 1;
                }
                else
                {
                    break;
                }
            }

            if (insidePointCount == polygon.Count)
            {
                innerPolygons.Add((Polygon)polygon);
            }

        }

        return innerPolygons;
    }

        /// <summary>
        /// Source: https://stackoverflow.com/questions/4243042/c-sharp-point-in-polygon
        /// </summary>
        /// <param name="polygon"></param>
        /// <param name="testPoint"></param>
        /// <returns></returns>
        public static bool IsPointInPolygon(List<DoublePoint> polygon, DoublePoint testPoint)

            bool result = false;
            int j = polygon.Count() - 1;
            for (int i = 0; i < polygon.Count(); i++)
            {
                if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
                {
                    if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
                    {
                        result = !result;
                    }
                }
                j = i;
            }
            return result;
        }
  }