11

我正在处理地理空间形状并在这里查看质心算法,

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 形,那么它在形状之外对我来说是没有意义的。

4

5 回答 5

17

这个答案的灵感来自 Jer2654 的答案和这个来源: 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);
  }
于 2013-11-03T05:57:40.910 回答
6
public static Point GetCentroid( Point[ ] nodes, int count )
{
    int x = 0, y = 0, area = 0, k;
    Point a, b = nodes[ count - 1 ];

    for( int i = 0; i < count; i++ )
    {
        a = nodes[ i ];

        k = a.Y * b.X - a.X * b.Y;
        area += k;
        x += ( a.X + b.X ) * k;
        y += ( a.Y + b.Y ) * k;

        b = a;
    }
    area *= 3;

    return ( area == 0 ) ? Point.Empty : new Point( x /= area, y /= area );
}
于 2013-05-30T16:08:59.037 回答
5

您可以检查 .NET 4.5 DbSpatialServices 功能,例如DbSpatialServices.GetCentroid

于 2012-11-09T14:23:40.507 回答
0

对于 3d Points,我在 C# 中创建了一个方法,希望对您有所帮助:

public static double[] GetCentroid(List<double[]> listOfPoints)
    {
        // centroid[0] = X
        // centroid[1] = Y
        // centroid[2] = Z
        double[] centroid = new double[3];

        // List iteration
        // Link reference:
        // https://en.wikipedia.org/wiki/Centroid
        foreach (double[] point in listOfPoints)
        {
            centroid[0] += point[0];
            centroid[1] += point[1];
            centroid[2] += point[2];
        }

        centroid[0] /= listOfPoints.Count;
        centroid[1] /= listOfPoints.Count;
        centroid[2] /= listOfPoints.Count;

        return centroid;
    }
于 2020-07-20T03:57:51.370 回答
0

我的实现:

GpsCoordinates GetCentroid(ICollection<GpsCoordinates> polygonCorners)
{
    return new GpsCoordinates(polygonCorners.Average(x => x.Latitude), polygonCorners.Average(x => x.Longitude));
}

public readonly struct GpsCoordinates
{
    public GpsCoordinates(
        double latitude,
        double longitude
        )
    {
       
        Latitude = latitude;
        Longitude = longitude;
    }

    public double Latitude { get; }
    public double Longitude { get; }
}

取自这里的想法

于 2021-09-23T14:07:59.487 回答