# center of an arbitrary set of points in 2D

This topic is 4200 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

If have a set of points in 2D, what's the most efficient way of calculating the center of all points?

##### Share on other sites
Assuming all points are equal, average all your x coordinates, then all your y coordinates, and so on.

##### Share on other sites
Quote:
 Original post by importer_exporterIf have a set of points in 2D, what's the most efficient way of calculating the center of all points?
There is no single center for a set of points; there are lots of different centers with different properties. If you want a good answer, you need to specify what properties you want this center to have.

Compare the over 1000(!) centers that exist for a simple triangle:
http://faculty.evansville.edu/ck6/encyclopedia/
(also http://faculty.evansville.edu/ck6/tcenters/index.html)

##### Share on other sites

Yikes, I knew there was more than one center to a triangle, but not that many!

I think the definition would be:
The center point where the distances, from that center to each other point, are equal.

Cool to hear from you Christer. I have your book and it's awesome.

##### Share on other sites
A point like that doesn't always exist in a given set of points. What you probably want is the centroid of the polygon. Check this out:

http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/

##### Share on other sites
With your definition there is no such point in general. Such point can be found only if the points are located on the arc of a circle. However, perhaps you want a point that minimizes the distances to all other points? Notice, that this requirement reduces to your original definition when the points _are_ on the arc of the circle.

You can calculate the center by minimizing sum_i {(x_i - c_x)^2 + (y_i - c_y)^2}, where x_i and y_i are the coordinates of the ith point and c_x and c_y are the coordinates of the center to be found. Google for least squares problem.

##### Share on other sites

Sorry, I did mean the center point that is the shortest distance *possible* to all the other points.

##### Share on other sites
I should point out that the least squares solution is only one of the ways to mathematically describe a point which in some sense is at minimum distance to other points. Equally well one could wish to find the point for which the maximum of distances is minimized, which is also a way to say that a point is close to all the other points.

##### Share on other sites
i have an idea but i am not so sure , maybe if you find the convex hull of the set and then discard all these convex hull's vertices , and repeat this process untill you find a convex polygon (without interior points) and finally find the centroid of this polygon .

##### Share on other sites
Winograd, could I trouble you for the solution you described in psuedocode? Im not clear on how I would translate "minimizing sum_i {(x_i - c_x)^2 + (y_i - c_y)^2}," to code.

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633384
• Total Posts
3011597
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!