Как рассчитать Centroid

Question

Я работаю с геопространственными формами и смотрю на алгоритм центроида здесь,

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,623.62).Что в порядке, за исключением того, что точка находится за пределами фигуры.Есть ли другой алгоритм, который учитывает это?

По сути, человек будет рисовать фигуру на карте.Эта форма может охватывать несколько дорог (так что это может быть L-образная форма), и я хочу проработать центр формы.Это так, чтобы я мог определить название дороги на этом этапе.Для меня не имеет смысла находиться за пределами фигуры, если они нарисовали длинную худую форму L.

Answer 1

Этот ответ основан на ответе Jer2654 и источника: http://coding -experiment.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);
  }

Answer 2

Вы можете проверить, работают ли .NET 4.5 DbSpatialServices, например DbSpatialServices.GetCentroid

Answer 3

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 );
}

Answer 4

Я бы порекомендовал не писать это самостоятельно, а вместо этого использовать SharpMap

http://sharpmap.codeplex.com/

Они проделали хорошую работу, предоставив центроидам (даже должны быть внутри) и целую кучу дополнительных функций.Вы можете хотеть.