基于C#的ArcEngine二次開發50：生成面空洞連接配接線

目錄

1 由無序點集生成不相交路徑的算法

1.1 算法原理介紹與示意圖

1.2 代碼實作

2 面要素外環内環擷取相關說明

2.1 擷取面的四至範圍：Evelope

2.2 擷取面心點

2.3 點集連接配接成線

2.4 提取環

現有一個面，裡邊包含若幹空洞，也即内環，需要生成一條連接配接線，将所有的内環連接配接，而且保證連接配接線不存在自相交現象。處理思路：

1. 首先擷取面的外環，之後針對每個外環，捕捉其面心點，将其面心點連結。
2. 擷取面心點後，需要根據面心點集構造一條過所有面心點的多段線；這個問題本質上以上運籌學中的基本最短路問題(ESPP)，但是我們這裡不要求那麼精确；隻需要生成一條不相交的多段線即可。一個最簡單的處理為根據X和Y坐标排序，生成有序點集，再将有序點集轉化為多段線即可。
3. 此外還有一種思路是調用ArcGIS的VRP工具處理，但是流程相對較為複雜，暫不考慮。

1 由無序點集生成不相交路徑的算法

1.1 算法原理介紹與示意圖

來自知乎的一個回答：

1. 對所有點按照x坐标（x相同時按y）從小到大排序，把最左邊的點記為A（若有多個取最下方的點），最右邊的點記為B（若有多個取最上方的點）。
2. 構造上鍊： 把所有在直線AB上方的點按x坐标（x相同時按y）從小到大連接配接起來
3. 構造下鍊：對位于直線AB下方的點同樣處理。

最後輸出的時候注意把下鍊颠倒一下（連的時候是從A連到B的，輸出的時候從B到A輸出）就行。正确性顯而易見：上鍊内部是邊不交的（因為邊的端點的x坐标從小到大排列），下鍊同理，上下鍊之間也不交（因為分處直線AB兩側，沒法交）。然後就完了！時間複雜度O(NlgN)，而且非常好寫！示意圖如下：

1.2 代碼實作

下面是一段C#代碼，吸收了上面算法的思想，主要思路為：

1. 将原始點集線按照Y坐标遞增排序
2. 通過Y值判斷坐标點是否屬于同一行，再對同一行的坐标點按X值從小到大進行排序

注意，代碼中的lineSpacing可以根據需要任意指定

YSortedPointList = SrcPointList.OrderBy(o => o.Y).ToList();   //坐标點按Y值升序排序（Y值從小到大的排序）
 
            //二維平面坐标點排序
            for (int i = 0; i < YSortedPointList.Count - 1; i++)
            {
                //通過Y值之間的內插補點大小來判斷坐标點是否屬于同一行
                if (Math.Abs(YSortedPointList[i].Y - YSortedPointList[i + 1].Y) < LineSpacing)
                {
                    RowPointList.Add(YSortedPointList[i]);
 
                    //如果最後一個點不是單獨一行的情況
                    if (YSortedPointList.Count - 2 == i)
                    {
                        RowPointList.Add(YSortedPointList[i + 1]);      //将最後一個坐标元素添加進來
                        RowPointList = RowPointList.OrderBy(o => o.X).ToList();
                        SortedPointList = SortedPointList.Concat(RowPointList).ToList();
                        RowPointList.Clear();
                    }
                }
                else
                {
                    //如果第一個點是單獨一行的情況
                    if (0 == i)
                    {
                        SortedPointList.Add(YSortedPointList[i]);
                        continue;
                    }
 
                    RowPointList.Add(YSortedPointList[i]);
                    RowPointList = RowPointList.OrderBy(o => o.X).ToList();                  //坐标點按X值升序排序
                    SortedPointList = SortedPointList.Concat(RowPointList).ToList();
                    RowPointList.Clear();
 
                    //如果最後一個點是單獨一行的情況
                    if (YSortedPointList.Count - 2 == i)
                    {
                        SortedPointList.Add(YSortedPointList[i + 1]);
                    }
                }             
            }
           

2 面要素外環内環擷取相關說明

2.1 擷取面的四至範圍：Evelope

可以通過已下屬性和方法，擷取四至範圍資訊：

屬性或方法	描述
UpperLeft	左上點坐标
UpperRight	右上角坐标
LowerLeft	左下角坐标
LowerRight	右下角坐标
XMin/XMax	X的最小最大值
YMin/YMax	Y的最小最大值
ZMin/ZMax	Z的最小最大值
Project	投影到指定的坐标系中
GeometryType	esriGeometryNull = 0 esriGeometryPoint = 1 esriGeometryMultipoint = 2 esriGeometryPolyline = 3 esriGeometryPolygon = 4 esriGeometryEnvelope = 5 esriGeometryPath = 6 esriGeometryAny = 7 esriGeometryMultiPatch = 9 esriGeometryRing = 11 esriGeometryLine = 13 esriGeometryCircularArc = 14 esriGeometryBezier3Curve = 15 esriGeometryEllipticArc = 16 esriGeometryBag = 17 esriGeometryTriangleStrip = 18 esriGeometryTriangleFan = 19 esriGeometryRay = 20 esriGeometrySphere = 21

常見GeometryType類型圖示：

2.2 擷取面心點

面心點，即為一個面的中心點，示意圖如下：

代碼：

IPoint pt = new PointClass();
(myGeo as IArea).QueryCentroid(pt);
           

2.3 點集連接配接成線

IPointCollection ptColl = new PolylineClass();
//加點
ptColl.AddPoint(pt);
//連線
Polyline line = ptColl as Polyline;
           

2.4 提取環

環分内環和外環，對于普通的幾個要素，隻有一個圖形；但是對于multipart要素，可能包含多個圖形，圖形個數等于外環個數；每個外環内部有多個内環。

IGeometry --> ExteriorRingBag --> InteriorRingBag

下面是官方幫助提供的用法示例：

publicstaticvoid PolygonToString(IPolygon4 polygon)
{
    IGeometryBag exteriorRingGeometryBag = polygon.ExteriorRingBag;
    IGeometryCollection exteriorRingGeometryCollection = exteriorRingGeometryBag as IGeometryCollection ;
    Trace .WriteLine("polygon.ExteriorRingCount = " + exteriorRingGeometryCollection.GeometryCount);
    for (int i = 0; i < exteriorRingGeometryCollection.GeometryCount; i++)
    {
        Trace .WriteLine("polygon.ExteriorRing[" + i +"]" );
        IGeometry exteriorRingGeometry = exteriorRingGeometryCollection.get_Geometry(i);
        IPointCollection exteriorRingPointCollection = exteriorRingGeometryasIPointCollection ;
        for (int j = 0; j < exteriorRingPointCollection.PointCount; j++)
        {
            Trace .WriteLine("Point[" + j +"] = " + PointToString(exteriorRingPointCollection.get_Point(j)));
        }
        IGeometryBag interiorRingGeometryBag = polygon.get_InteriorRingBag(exteriorRingGeometryasIRing );
        IGeometryCollection interiorRingGeometryCollection = interiorRingGeometryBagasIGeometryCollection ;
        Trace .WriteLine("polygon.InteriorRingCount[exteriorRing" + i +"] = " + interiorRingGeometryCollection.GeometryCount);
        for (int k = 0; k < interiorRingGeometryCollection.GeometryCount; k++)
        {
            Trace .WriteLine("polygon.InteriorRing[" + k +"]" );
            IGeometry interiorRingGeometry = interiorRingGeometryCollection.get_Geometry(k);
            IPointCollection interiorRingPointCollection = interiorRingGeometryasIPointCollection ;
            for (int m = 0; m < interiorRingPointCollection.PointCount; m++)
            {
                Trace .WriteLine("Point[" + m +"] = " + PointToString(interiorRingPointCollection.get_Point(m)));
            }
        }
   }
}

privates tatic string PointToString(IPoint point)
{
    return (point.X +", " + point.Y +", " + point.Z);
}

           

歡迎關注個人公衆賬号，一起學習，聰明的努力！