Jump to content
  • Advertisement
Sign in to follow this  
importer_exporter

center of an arbitrary set of points in 2D

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
Assuming all points are equal, average all your x coordinates, then all your y coordinates, and so on.

Share this post


Link to post
Share on other sites
Quote:
Original post by importer_exporter
If 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

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!