使用具有内边界的Google Earth KML的Clipper多边形合并结果

Question

我想把多边形合并成一个可以有洞的区域。Clipper可以做到这一点，然而，当我在Google Earth中使用生成的两个多边形时，问题是Google earth将这些多边形分开处理，并将它们相互叠加。在KML中，可以为多边形创建OuterBoundary和InnerBoundary元素。问题是，使用Clipper结果，您如何知道什么是内部边界，什么是外部边界。值得一提的是:即使它可以以某种方式确定，在实际的Clipper联合调用中，我也使用了几千个圆形多边形。所以有多个有孔的独立区域。

合并后：

​

下面是包含四个简单形状的代码：

/* 
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             
*/

更新:在KML中，总是有两组多边形列表，OuterBoundaries和InnerBoundaries。我设法递归地解析多边形，并检查每个最外层的多边形是否有内部多边形。最外层的内部多边形是InnerBoundary。所有其他内部多边形再次作为OuterBoundary多边形启动。一旦我找出了一些非常大的多边形集的问题，我会尽快发布代码。

Answer 1

我基本上使用了一个递归方法来遍历所有嵌套的多边形。OuterBoundary和InnerBoundary元素交替使用。我确信还有改进的空间，但结果似乎与QGIS导出(我后来发现)是一样的。当我使用复杂数据时，未填充的多边形会出现问题。我在GIS StackExchange页面中添加了一个关于此问题的单独问题：

 // 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;
        }
  }