How to calculate Centroid

Question

I work with geospatial forms and look at the centroid algorithm here,

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

I implemented code in C #, like this one (which has just been adapted),

Looking for the center of gravity of a polygon?

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

The problem is that this algorithm, when I have this form (form L),

(1.1) (1.10) (2.10) (2.2) (10.2) (10.1) (1.1)

This gives me the result (3.62, 3.62). This is normal, except that the point is out of shape. Is there any other algorithm that takes this into account?

Basically, a person will draw a figure on a map. This shape can span several roads (it could be an L-shape), and I want to work out the center of the figure. This means that I can determine the name of the road at this moment. It doesn't make sense to me if he were out of shape if they drew a long skinny L-shape.

Answer 1

I would recommend not writing this yourself and using SharpMap instead

http://sharpmap.codeplex.com/

They did a good job giving their centroids (should even be within), and the whole group has more features you might need.

Answer 2

This answer is inspired by Jer2654's answer 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); } 

Answer 3

You can check if the .NET 4.5 function of DbSpatialServices works, e.g. DbSpatialServices.GetCentroid

Answer 4

 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 = aY * bX - aX * bY; area += k; x += ( aX + bX ) * k; y += ( aY + bY ) * k; b = a; } area *= 3; return ( area == 0 ) ? Point.Empty : new Point( x /= area, y /= area ); }