现有一个面，里边包含若干空洞，也即内环，需要生成一条连接线，将所有的内环连接，而且保证连接线不存在自相交现象。处理思路：
首先获取面的外环，之后针对每个外环，捕捉其面心点，将其面心点链接。
获取面心点后，需要根据面心点集构造一条过所有面心点的多段线；这个问题本质上以上运筹学中的基本最短路问题(ESPP)，但是我们这里不要求那么精确；只需要生成一条不相交的多段线即可。一个最简单的处理为根据X和Y坐标排序，生成有序点集，再将有序点集转化为多段线即可。
此外还有一种思路是调用ArcGIS的VRP工具处理，但是流程相对较为复杂，暂不考虑
1 由无序点集生成不相交路径的算法
1.1 算法原理介绍与示意图
来自知乎的一个回答：
对所有点按照x坐标（x相同时按y）从小到大排序，把最左边的点记为A（若有多个取最下方的点），最右边的点记为B（若有多个取最上方的点）。
构造上链： 把所有在直线AB上方的点按x坐标（x相同时按y）从小到大连接起来
构造下链：对位于直线AB下方的点同样处理。
最后输出的时候注意把下链颠倒一下（连的时候是从A连到B的，输出的时候从B到A输出）就行。正确性显而易见：上链内部是边不交的（因为边的端点的x坐标从小到大排列），下链同理，上下链之间也不交（因为分处直线AB两侧，没法交）。然后就完了！时间复杂度O(NlgN)，而且非常好写！示意图如下：
1.2 代码实现
下面是一段C#代码，吸收了上面算法的思想，主要思路为：
- 将原始点集线按照Y坐标递增排序
- 通过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
可以通过已下属性和方法，获取四至范围信息：
常见GeometryType类型图示：
2.2 获取面心点
面心点，即为一个面的中心点，示意图如下：
代码：
1. IPoint pt = new PointClass(); 2. (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); }
