Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Well it might be a simple question. Given a set of 2D or 3D points, the question is:

How to find the center of geometry of an object?

According to the following figure, the center of geometry differs from the center of mass if it is calculated in the simplest form i.e., homogenous density of mass. The problem appears, indeed, in the computation of those. Commonly, one approach is to average X coordinates and Y coordinates separately i.e., find an average position to the given points (here in 2D). This may be used as centroid for the set of points representing an object. As shown, due to the extra vertex along the bottom edge, for a simple rectangle the resulting centroid is (0.5,0.4) while the correct answer is (0.5,0.5).
Note that the example given is too simple. The problem of interest however is for complex shapes in 2D and objects in 3D for which only coordinates of vertices are available.
BTW, an efficient computational way is of interest.

Update 1:
Just to mention that I have checked some web links such as Wikipedia's however my current problem is that there are group of 2D and 3D points wish to find a point as representative for those. Thus centroid became of interest. The points are given without any topological information. You may consider them as point cloud. The demonstration here provided to make it clear that the commonly known averaging of coordinates (see for example this) may be incorrect as shown in the example. Hope the point is clear now.

enter image description here

Update 2:
Here are some implementations for comparison:

  • aa = accepted answer below
  • chull = convex-hull of points i.e., the golden polygon
  • cent = centroid proposed in Wikipedia and discussed in aa as the polygon centroid
  • centl = centroid of polyline as explained in aa

Visually, centl looks better representative for the geometry given compared to cent. Two others look promising here but usually they are too biased if the dispersion of the points were inhomogeneous as it is a usual case.
And also consider that although convex-hull makes problem reasonably simpler however it may generate too long and too short edges without any symmetrical positioning in the space, that is, awareness is necessary if you do simple averaging (i.e., without weighting) for both cases: entire points (green) or convex-hull polygon vertices (blue).

enter image description here

Update 3:
One application could be found in this post.

share|improve this question
    
Will this work? Finding the centroid of a polygon? (StackOverflow) –  blah238 Apr 3 '12 at 5:00
3  
I am not sure what your Question is. Center of Geometry or (usually the centroid) can be different from barycenter (center of mass). This is a well known fact. Also there are various ways to calculate the center of a geometry. See: en.wikipedia.org/wiki/Triangle_center , en.wikipedia.org/wiki/Encyclopedia_of_Triangle_Centers & faculty.evansville.edu/ck6/encyclopedia/ETC.html. –  Devdatta Tengshe Apr 3 '12 at 5:00
1  
Re the update: when there is no topology, a point cloud is just a point cloud. Your figure of a polygonal square does not apply (and your 'centroid' of (0.5,0.4) does not appear to arise from any standard formula, by the way: symmetry argues strongly for any central point of the square to coincide with (0.5,0.5), no matter how it is defined). For some ideas about finding representative or central locations for point clouds in two and more dimensions, please see stats.stackexchange.com/questions/1927. –  whuber Apr 3 '12 at 7:13
1  
@Developer, I see your point now, your 5th point on the bottom of the "rectangle" (actually a polygon) makes a simple averaging of vertex coordinates yield a different barycenter than that of a polygon as whuber's answer explains. –  blah238 Apr 3 '12 at 16:33
1  
Aha! I completely missed that fifth vertex, even though I had been looking for some such thing. To help future readers, I have made a slight edit in the question to point this out. This really does get to the heart of the matter, too: inserting or deleting vertices along edges will change how a poly{line,gon} is represented, but it should not change the computation of its innate geometric properties. That is why the barycenter of the vertices can have an almost arbitrary relationship to the barycenters of a polygon or its boundary. –  whuber Apr 3 '12 at 19:25
show 6 more comments

1 Answer 1

up vote 36 down vote accepted

Every polygon has, at a minimum, four distinct "centers":

  • The barycenter of its vertices.

  • The barycenter of its edges.

  • Its barycenter as a polygon.

  • A GIS-specific "center" useful for labeling (usually calculated with undocumented proprietary methods).

(They may accidentally coincide in special cases, but for "generic" polygons they are distinct points.)

A "barycenter" in general is a "center of mass." The three types differ on where the mass is presumed located: it either is entirely on the vertices, spread uniformly on the edges, or spread uniformly throughout the polygon itself.

Simple methods exist to compute all three barycenters. One approach relies on the basic fact that the barycenter of the disjoint union of two masses is the total-mass-weighted average of the barycenters. From this we easily obtain the following:

  1. The barycenter of two (equally weighted) vertices is their average. This is obtained by averaging their coordinates separately. Geometrically, it is the midpoint of the line segment joining the two vertices.

  2. Inductively, the barycenter of n (equally weighted) vertices is obtained by averaging their coordinates separately.

  3. The barycenter of a line segment is its midpoint. (This is clear by symmetry.)

  4. The barycenter of a polyline is obtained by finding the midpoints of each line segment and then forming their weighted average using the segment lengths as weights.

    For example, consider the "L" shape delineated by the points (0,0), (6,0), (6,12). There are two segments: one of length 6 with midpoint at ( (0+0)/2, (0+6)/2 ) = (3,0) and another of length 12 with midpoint at ( (6+6)/2, (0+12)/2 ) = (6,6). Their length-weighted average coordinates are therefore (x,y) with

    x = (6*3 + 12*6) / (6+12) = 5,  y = (6*0 + 12*6) / (6+12) = 4.
    

    This differs from the barycenter of the three vertices, which is ( (0+6+6)/3, (0+0+12)/3 ) = (4,4).

    (Edit As another example, consider the figure in the question, which although square in shape, is represented as a pentagon determined by the sequence of points (0,0), (1/2,0), (1,0), (1,1), (0,1). The five sides have lengths 1/2, 1/2, 1, 1, 1 and midpoints (1/4,0), (3/4,0), (1,1/2), (1/2,1), and (0,1/2), respectively. Their weighted average therefore equals

    [(1/2)*(1/4, 0) + (1/2)*(3/4, 0) + (1)*(1, 1/2) + (1)*(1/2, 1) + (1)*(0, 1/2)] / (1/2+1/2+1+1+1)
    = (2/4, 2/4) = (0.5, 0.5)
    

    as one would hope, even though the barycenter of the vertices alone (computed as in #2 above) is (0.5, 0.4).)

  5. The barycenter of a polygon can be obtained by triangulation to decompose it into triangles. The barycenter of a triangle-qua-polygon coincides with the barycenter of its vertices. The area-weighted average of these barycenters is the polygon's barycenter. Triangle areas are readily computed in terms of their vertex coordinates (e.g., in terms of the wedge product of two of the sides). For an illustration of such area calculations, including how to exploit signed (positive or negative) areas, see the section on "Area" at my (old) course notes page.

    (Edit Consider the polygon depicted in the question for example. We could triangulate it with triangles ((0,0), (1/2,0), (0,1)) on the left, ((0,1), (1/2,0), (1,1)) in the middle, and ((1,1), (1,0), (1/2,0)) on the right. Their areas are 1/4, 1/2, 1/4 respectively and their barycenters--obtained by averaging their vertices--are (1/6,1/3), (1/2,2/3), and (5/6,1/3), respectively. The area-weighted average of these barycenters equals

    [(1/4)*(1/6,1/3) + (1/2)*(1/2,2/3) + (1/4)*(5/6,1/3)] / (1/4 + 1/2 + 1/4)
    = (12/24, 6/12)
    = (0.5, 0.5)
    

    as it should, despite the presence of that fifth vertex along the bottom edge.)

It is evident that each of these methods is efficient: it requires just a single pass over the "spaghetti" representation of the polygon, using (fairly little) constant time at each step. Note that in all cases except the first (of pure vertices), more information than just a list of vertex coordinates is needed: you need to know the topology of the figure as well. In the "L" example, we needed to know that (0,0) was connected to (6,0) and not to (6,12), for instance.

These are all Euclidean concepts. They can be extended to the sphere (or ellipsoid) in several ways. A straightforward one views the features as a simplicial complex in three (Euclidean) dimensions, computes the appropriate barycenter, and then projects it outward from the center of the ellipsoid back to the surface. This requires no new concepts or formulas; you only have to work with a third (z) coordinate in addition to the first two coordinates. (Areas are still found using lengths of wedge products.)

Another generalization recognizes that the Euclidean metric--the square root of a sum of squares, according to Pythagoras--can be changed to other Lp metrics for p >= 1: you take the pth root of the sum of pth powers. Finding appropriate "barycenters" is no longer so simple, because the beautiful additive properties exploited above (barycenters are weighted averages of barycenters of simpler parts of a figure) no longer hold in general. Often, iterative approximate numerical solutions have to be obtained. They might not even be unique.

Additional centers can be defined for various purposes. Triangles have many different centers that can generalize (somewhat) to polygons: the center of the circumcircle, the center of (some) maximal incircle, the center of a minimum-area bounding ellipse, and others. Any set can be enclosed in various "hulls," such as the convex hull, and the centers of those hulls obtained.

Note that many of these "centers" are not necessarily located within the interior of a polygon. (Any reasonable center of a convex polygon will lie within its interior, though.)

This variety of approaches and solutions indicates one should be wary of a generic term like "center of geometry" or merely "center": it could be just about anything.

share|improve this answer
    
To community: Such a good answer like this from 'whuber' can be expected only for a good question, as my familiarity with his preference, thus, would you everybody mind to up-vote the question too if you found it interesting ;) –  Developer Apr 3 '12 at 9:20
    
I found it useful in some sence, wish to give sometime to other contirbuters as motivation for answering. I mark this however an accepatable constructive answer so far. –  Developer Apr 3 '12 at 9:21
    
Can you explain why areas are still found using wedge products on a sphere? Wouldn't the spherical triangle area be more appropriate? The closest reference (aside from this excellent answer!) that I've found is: jennessent.com/downloads/Graphics_Shapes_Online.pdf - which uses areas of spherical triangles. –  Jason Davies Dec 7 '12 at 10:47
    
@Jason I am intrigued: how do you propose using spherical triangle areas to compute barycenters of spherical features? –  whuber Dec 7 '12 at 14:20
    
@whuber The spherical polygon is decomposed into spherical triangles, and the barycenter of each triangle is computed by averaging the Cartesian coordinates of its vertices. I'm proposing that the polygon barycenter is the weighted average of these triangles, where the weight is the spherical triangle area, not the planar area as you suggested in your answer (assuming I understand the wedge product correctly). –  Jason Davies Dec 7 '12 at 16:05
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.