center of an arbitrary set of points in 2D
Author
If have a set of points in 2D, what's the most efficient way of calculating the center of all points?
Assuming all points are equal, average all your x coordinates, then all your y coordinates, and so on.
Quote:Original post by importer_exporterThere 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.
If have a set of points in 2D, what's the most efficient way of calculating the center of all points?
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)
Author
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.
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/
http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/
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.
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.
Author
Sorry, I did mean the center point that is the shortest distance *possible* to all the other points.
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.
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 .
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
