在GIS中，为了让地图传递更多的信息，而且能使得这些信息具有更好的可读性，标注是不可获缺少的。最近公司的B/S项目，为了脱离服务端的标注功能，减少服务端的负担，就必须在客户端代码直接实现。下面是本人写一个标注点的算法（在C#的Winform写的），算法不算完善，但对普遍的多边形找到标注点是可行的。
我采用的算法是得到多边形的所有对角线，按从大到小排序并逐一遍历，如果一旦有一条的对角线的中点在多边形内，就停止遍历，输出该点即为标注点。对于一些端点非常多的多边形图形，为了减少对角线的计算量，在得到所有对角线之前最好能够先平滑掉一些影响不大的点。
平滑多边形：
/// <summary>
/// 线的结构
/// </summary>
public struct MyLine
{
public PointF startPoint;
public PointF endPoint;
}
计算点到直线的距离函数
public double CaculateDistance(MyLine line, PointF point)
{
//直线方程式：ax-y+c=0
double a = (line.startPoint.Y - line.endPoint.Y) / (line.startPoint.X - line.endPoint.X);
double c = line.startPoint.Y - a * line.startPoint.X;
double distance = Math.Abs(a * point.X - point.Y + c) / Math.Sqrt(a*a+1);
return distance;
}
平滑多边形，返回多变的坐标串
public List<PointF> Smooth(List<PointF> pointList)
{
string str = string.Empty;
pointList.Add(pointList[0]); //List最后一个位置添加多边形起始点
//为List的第一个位置添加多边形最后一个点
List<PointF> pointListNew = new List<PointF>();
pointListNew.Add(pointList[pointList.Count - 2]);
for (int i = 0; i < pointList.Count; i++)
{
pointListNew.Add(pointList[i]);
}
for (int i = 1; i < pointListNew.Count - 1; i++)
{
MyLine line = new MyLine();
line.startPoint = pointListNew[i - 1];
line.endPoint = pointListNew[i + 1];
if (CaculateDistance(line, pointListNew[i]) < 5) //5为阈值
{
pointListNew.RemoveAt(i);
}
}
pointListNew.RemoveAt(0);
pointListNew.RemoveAt(pointListNew.Count - 1);
return pointListNew;
}
接下来，要写出一个判断点是否在多变性的方法：该方法是利用该点沿着y轴的射线与多边形的交点个数来判断的，一般情况下，交点为奇数个的时，该点在多边形内，相反，为偶数个的时候，该点位于多边形外。本方法还考虑到了射线不穿过多边形而只与多边形的端点相交的情况，如何判断这样的特殊点呢？首先你要知道这个待判断特殊点的在坐标串的位置，如果该待判断特殊点的前一个点和后一个点都在直线的同一边，则这个待判断特殊点就是名副其实的特殊点。如果有特殊点存在时，判断的点是否在多边形内的方法就会有所不同：如果该射线与多边形的交点为奇数个，且特殊点也为奇数个，则点在多边形外；如果该射线与多边形的交点为奇数个，且特殊点也为偶数个，则点在多边形内；如果该射线与多边形的交点为偶数个，且特殊点也为奇数个，则点在多边形内；如果该射线与多边形的交点为偶数个，且特殊点也为偶数个，则点在多边形外。
public bool JudgeInOutPolygon(List<PointF> pointList, PointF labelPoint)
{
pointList.Add(pointList[0]); //List最后一个位置添加多边形起始点
//为List的第一个位置添加多边形最后一个点
List<PointF> pointListNew = new List<PointF>();
pointListNew.Add(pointList[pointList.Count - 2]);
for (int i = 0; i < pointList.Count; i++)
{
pointListNew.Add(pointList[i]);
}
int intersectionPointNumber = 0;
int specialPoint = 0; //特殊点，就是该点为多边形的顶点，而且与该点相邻的上下点都在标注点的同一边
for (int i = 1; i < pointListNew.Count - 1; i++)
{
if ((pointListNew[i].X <= labelPoint.X && pointListNew[i + 1].X >= labelPoint.X) || (pointListNew[i].X >= labelPoint.X && pointListNew[i + 1].X <= labelPoint.X))
{
float a = (pointListNew[i].Y - pointListNew[i + 1].Y) / (pointListNew[i].X - pointListNew[i + 1].X);
float b = pointListNew[i].Y - a * pointListNew[i].X;
float y = a * labelPoint.X + b;
if (y >= labelPoint.Y && y != pointListNew[i + 1].Y)
{
intersectionPointNumber++; //得到全部的交点个数
// MessageBox.Show("X—>" + labelPoint.X + "Y—>" + y);
if (y == pointListNew[i].Y)
{
if ((pointListNew[i - 1].X > labelPoint.X && pointListNew[i + 1].X > labelPoint.X) || (pointListNew[i - 1].X < labelPoint.X && pointListNew[i + 1].X < labelPoint.X))
{
specialPoint++;
}
}
}
}
}
// MessageBox.Show("总共的点数：" + intersectionPointNumber.ToString() + "特殊点数：" + specialPoint.ToString());
if ((intersectionPointNumber % 2 == 0 && specialPoint % 2 == 1) || intersectionPointNumber % 2 == 1 && specialPoint % 2 == 0)
{
return true;
}
return false;
}
判断方法现有了，最后面该做的就是遍历多变行的对角线，得出该标注点：
public double LineLength(MyLine line)
{
double length = Math.Sqrt((line.startPoint.X - line.endPoint.X) * (line.startPoint.X - line.endPoint.X) + (line.startPoint.Y - line.endPoint.Y) * (line.startPoint.Y - line.endPoint.Y));
return length;
}
//对角线求标注点，能够保证点一点在多边形内(适合凹多边形，但还不是最优的位置)
public PointF LookForLabelPoint3(List<PointF> pointArray)
{
PointF centerPoint = new PointF();
MyLine longestdiagonalLine = new MyLine(); //对角线
double length = 0;
int num = 0;
for (int i = 0; i < pointArray.Count - 2; i++)
{
if (i == 0)
{
num = pointArray.Count - 1;
}
else
{
num = pointArray.Count;
}
for (int j = i + 2; j < num; j++)
{
MyLine line = new MyLine();
line.startPoint = pointArray[i];
line.endPoint=pointArray[j];
centerPoint.X = (line.startPoint.X + line.endPoint.X) / 2;
centerPoint.Y = (line.startPoint.Y + line.endPoint.Y) / 2;
bool judgeIn = JudgeInOutPolygon(pointArray,centerPoint);
if (LineLength(line) > length && judgeIn)
{
longestdiagonalLine = line;
length = LineLength(line);
}
}
}
centerPoint.X = (longestdiagonalLine.startPoint.X + longestdiagonalLine.endPoint.X) / 2;
centerPoint.Y=(longestdiagonalLine.startPoint.Y+longestdiagonalLine.endPoint.Y)/2;
return centerPoint; //所得到的标注点
}
该标注点比较实用于凹多边形，对于凸多边形来说，直接去重心显得更完美些，（前提是你要先有个算法来得出多边形是凹多边形还是凸多边形，提示，只要存在多边形的两条相邻边的向多边形内的夹角>180°，就是凹多边形，否则为凸多边形）以下是多边形重心的求法：
//多边形的重心作为标注点
public PointF LookForLabelPoint2(List<PointF> points)
{
float area = 0;
PointF center = new PointF();
for (int i = 0; i < points.Count - 1; i++)
{
area += (points[i].X * points[i + 1].Y - points[i].Y * points[i + 1].X) / 2;
center.X += (points[i].X * points[i + 1].Y - points[i].Y * points[i + 1].X) * (points[i].X + points[i + 1].X);
center.Y += (points[i].X * points[i + 1].Y - points[i].Y * points[i + 1].X) * (points[i].Y + points[i + 1].Y);
}
area += (points[points.Count - 1].X * points[0].Y - points[points.Count - 1].Y * points[0].X) / 2;
center.X += (points[points.Count - 1].X * points[0].Y - points[points.Count - 1].Y * points[0].X) * (points[points.Count - 1].X + points[0].X);
center.Y += (points[points.Count - 1].X * points[0].Y - points[points.Count - 1].Y * points[0].X) * (points[points.Count - 1].Y + points[0].Y);
center.X /= 6 * area;
center.Y /= 6 * area;
return center;
}
个人小结：此算法能成功找到标注点，但寻找的标注点并不能处于多边形最优的位置，可以改进的地方是找到一条最长的对角线，而且该对角线的全部处于多边形内，这样求出来的标注点将会更加合适。这紧紧是我个人琢磨思考后得到的，如有更好的办法，欢迎大家来一起交流，对以上的代码，错误难免，欢迎指正。一起学习，一起进步。
相关文章
