Given a set of 2D or 3D points:
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.
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 Stack Overflow Q&A) may be incorrect as shown in the example.
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).
One application could be found in Finding minimum-area-rectangle for given points?.
Answer
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:
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.
Inductively, the barycenter of n (equally weighted) vertices is obtained by averaging their coordinates separately.
The barycenter of a line segment is its midpoint. (This is clear by symmetry.)
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).)
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.
No comments:
Post a Comment