我正在处理地理空间形状并在这里查看质心算法,
http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon
我已经像这样在 C# 中实现了代码(就是这样改编的),
class Program
{
static void Main(string[] args)
{
List<Point> vertices = new List<Point>();
vertices.Add(new Point() { X = 1, Y = 1 });
vertices.Add(new Point() { X = 1, Y = 10 });
vertices.Add(new Point() { X = 2, Y = 10 });
vertices.Add(new Point() { X = 2, Y = 2 });
vertices.Add(new Point() { X = 10, Y = 2 });
vertices.Add(new Point() { X = 10, Y = 1 });
vertices.Add(new Point() { X = 1, Y = 1 });
Point centroid = Compute2DPolygonCentroid(vertices);
}
static Point Compute2DPolygonCentroid(List<Point> vertices)
{
Point centroid = new Point() { X = 0.0, Y = 0.0 };
double signedArea = 0.0;
double x0 = 0.0; // Current vertex X
double y0 = 0.0; // Current vertex Y
double x1 = 0.0; // Next vertex X
double y1 = 0.0; // Next vertex Y
double a = 0.0; // Partial signed area
// For all vertices except last
int i=0;
for (i = 0; i < vertices.Count - 1; ++i)
{
x0 = vertices[i].X;
y0 = vertices[i].Y;
x1 = vertices[i+1].X;
y1 = vertices[i+1].Y;
a = x0*y1 - x1*y0;
signedArea += a;
centroid.X += (x0 + x1)*a;
centroid.Y += (y0 + y1)*a;
}
// Do last vertex
x0 = vertices[i].X;
y0 = vertices[i].Y;
x1 = vertices[0].X;
y1 = vertices[0].Y;
a = x0*y1 - x1*y0;
signedArea += a;
centroid.X += (x0 + x1)*a;
centroid.Y += (y0 + y1)*a;
signedArea *= 0.5;
centroid.X /= (6*signedArea);
centroid.Y /= (6*signedArea);
return centroid;
}
}
public class Point
{
public double X { get; set; }
public double Y { get; set; }
}
问题是这个算法当我有这个形状(这是一个 L 形状)时,
(1,1) (1,10) (2,10) (2,2) (10,2) (10,1) (1,1)
它给了我结果(3.62,3.62)。没关系,除了那个点在形状之外。是否有另一种算法考虑到这一点?
基本上,一个人将在地图上绘制一个形状。这个形状可能跨越多条道路(所以可能是 L 形),我想计算出形状的中心。这样我就可以在那时计算出道路名称。如果他们画了一个又长又瘦的 L 形,那么它在形状之外对我来说是没有意义的。