Использование результата объединения полигонов Clipper для Google Earth KML с внутренними границами
Я хочу объединить полигоны в одну область, в которой могут быть отверстия. Clipper может сделать это, однако, когда я использую два получающихся в Google Планета Земля многоугольника, проблема заключается в том, что Google Планета Земля обрабатывает эти полигоны отдельно и просто накладывает их друг на друга. В 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. Мне удалось рекурсивно разобрать полигоны и проверить для каждого внешнего полигона, если у него есть внутренние полигоны. Внешние внутренние полигоны - это Внутренняя граница. Все остальные внутренние полигоны снова начинаются как полигоны OuterBoundary. Я опубликую код, как только я выясню некоторые проблемы с очень большими наборами полигонов.
1 ответ
Я в основном использовал рекурсивный метод, чтобы пройти через все вложенные многоугольники. Элементы OuterBoundary и InnerBoundary чередуются. Я уверен, что есть еще возможности для улучшения, но результат, по-видимому, такой же, как и при экспорте в QGIS (о чем я узнал позже). Есть проблемы с незаполненными полигонами, когда я использую сложные данные. Я добавил отдельный вопрос по этому поводу на странице ГИС 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://stackru.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;
}
}