如何计算质心 [英] How to Calculate Centroid

问题描述

我正在处理地理空间形状，并在此处查看质心算法，

I am working with geospatial shapes and looking at the centroid algorithm here,

http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon

我已经在C#中实现了这样的代码(这是经过改编的)，

I have implemented the code in C# like this (which is just this adapted),

找到多边形的质心?

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形)时，此算法，

The problem is that this algorithm when I have this shape (which is an L shape),

(1,1)(1,10)(2,10)(2,2)(10,2)(10,1)(1,1)

(1,1) (1,10) (2,10) (2,2) (10,2) (10,1) (1,1)

它给了我结果(3.62，3.62).可以，除了该点在形状之外.周围是否还有其他算法可以考虑到这一点?

It gives me the result (3.62, 3.62). Which is OK, except that point is outside the shape. Is there another algorithm around that takes this into account?

基本上，一个人将要在地图上绘制形状.这个形状可能跨越多条道路(可能是L形)，我想算出形状的中心.这样一来，我就可以算出路名了.如果他们画了一个细长的L形，那么将它放在形状之外对我来说是没有意义的.

Basically a person is going to be drawing a shape on a map. This shape might span multiple roads (so could be an L shape) and I want to work out the centre of the shape. This is so I can work out the road name at that point. It doesn't make sense to me for it to be outside the shape if they have drawn a long skinny L shape.

推荐答案

此答案的灵感来自Jer2654的答案和以下来源: http://coding-experiments.blogspot .com/2009/09/xna-quest-for-centroid-of-polygon.html

This answer is inspired by the answer by Jer2654 and this source: http://coding-experiments.blogspot.com/2009/09/xna-quest-for-centroid-of-polygon.html

  /// <summary>
  /// Method to compute the centroid of a polygon. This does NOT work for a complex polygon.
  /// </summary>
  /// <param name="poly">points that define the polygon</param>
  /// <returns>centroid point, or PointF.Empty if something wrong</returns>
  public static PointF GetCentroid(List<PointF> poly)
  {
     float accumulatedArea = 0.0f;
     float centerX = 0.0f;
     float centerY = 0.0f;

     for (int i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
     {
        float temp = poly[i].X * poly[j].Y - poly[j].X * poly[i].Y;
        accumulatedArea += temp;
        centerX += (poly[i].X + poly[j].X) * temp;
        centerY += (poly[i].Y + poly[j].Y) * temp;
     }

     if (Math.Abs(accumulatedArea) < 1E-7f)
        return PointF.Empty;  // Avoid division by zero

     accumulatedArea *= 3f;
     return new PointF(centerX / accumulatedArea, centerY / accumulatedArea);
  }

这篇关于如何计算质心的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！