Sign in to follow this  

center of an arbitrary set of points in 2D

This topic is 3859 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

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
Ok. Lets rewrite it a bit:
f(c_x, c_y) = sum_i {(x_i - c_x)^2 + (y_i - c_y)^2} = sum_i {x_i^2 -2*x_i*c_x +c_x^2 + y_i^2 -2*y_i*c_y +c_y^2}

This function has a single minimum and it occurs when the gradient wrt c_x and c_y of the above function is 0:

grad_f(c_x, c_y) = [ sum_i { - x_i + c_x} ] = [ N*c_x - sum_i { x_i } ] = 0
[ sum_i { - y_i + c_y} ] [ N*c_y - sum_i { y_i } ]

That means that minimizing the distance in least squares sense, is equal to setting:

c_x = sum_i{ x_i } / N
c_y = sum_i{ y_i } / N

where N is the number of points. That is coordinates of the center in this sense are the average of the coordinates of the points.

Confusing definition lead to trivial solution :)

Share this post


Link to post
Share on other sites
Quote:
Original post by importer_exporter
Sorry, I did mean the center point that is the shortest distance *possible* to all the other points.
Generally the best approach when asking questions like these is to give the background as to why you are asking what you're asking (because there may be a better solution to the original problem than the one you have in mind).

So, in this case, why do you need this center? Possible answers include:

1. I want the center that produces the smallest bounding shape around the points (circle, box, or some other shape).

2. I want the point for which the sum of distances to all points in the set is minimized, because the points are tanks and I'm intending to station the fuel supplies in my RTS game at that location.

3. The set of points represent a polygon and I want a point drawn somewhere in the center of the polygon that people can click on and drag the polygon around.

4. I have an infinitely large tray with 1 kg weights at each of the set points and I need to find the point at which the tray would be balanced.

Etc.

When you provide this kind of information, it is much easier to suggest how the center is (best) computed. (Or, indeed, suggest alternative approaches altogether.)

Share this post


Link to post
Share on other sites
Winograd, thank you that helps.

Christer, you're right I should have just explained myself from the get go. I have a little 2D engine and, in order to allow for more complex geometry, there's a set of grouping classes. Basically, they're a just a collection of particles and constraints.

I would like to provide the user a 'center' property in the interface of the Group class. It's now possible to rotate the group of particles around an arbitrary center, but I would like to let the user be able to grab the center property and pass that to the rotate method. Or just make center available for any other purpose the user might need, such as using a single sprite in place of all the subcomponents.

Share this post


Link to post
Share on other sites

This topic is 3859 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this