|
|
|
This thread is locked; no one can reply to it.
|
| The middle point from a set of points |
|
Inphernic
Member #1,111
March 2001
|
http://edu.kauhajoki.fi/~juipe/Stuff/probby.png What I would like to know is that how to retrieve the middle point from a set of points. The set can be of any size from 3 to lots (cases with one and two points are trivial to solve), and the points in the set are not necessarily laid out in a symmetrical way. To make it slightly more fun, the points are not restricted to a 2D plane like in the examples - they are points in 3D space. In the examples, the black points are the points of the set, and the red point is the middle point. -- |
|
Kitty Cat
Member #2,815
October 2002
 |
Loop through each point and find the smallest x/y/z values, and the biggest, then: ((max_x - min_x) / 2) + min_x; ((max_y - min_y) / 2) + min_y; ((max_z - min_z) / 2) + min_z;
-- |
|
Inphernic
Member #1,111
March 2001
|
Works great, thanks for the fast reply! -- |
|
Oscar Giner
Member #2,207
April 2002
 |
I'd say that if you calculate the average of all x,y,z coordinates you'll get better results, for example in a case like this: * * * * *
-- |
|
Bob
Free Market Evangelist
September 2000
 |
If the point you're looking for must be in the original set, then you should average the coordinates of the points and look for the point with the shortest distance to that coordinate. -- |
|
23yrold3yrold
Member #1,134
March 2001
 |
Averaging will move the "middle" around if an unusually large number of points is to one side instead of the other ... -- |
|
Plucky
Member #1,346
May 2001
 |
The method should depend on how the set of points were created... |
|
Thomas Harte
Member #33
April 2000
 |
Quote: Averaging will move the "middle" around if an unusually large number of points is to one side instead of the other ... Depends what Inphernic means by middle I guess. If he means the point which, if you put any hyperplane through has more or less the same number of points on one side as the other then obviously this isn't a consideration. If instead he means the middle as in the most central point, then he is explicitly thinking about bounding forms, so might want to do something like calculate full extent along every axis and find the midpoint of that (i.e. the midpoint of the axis aligned bounding box). Beyond that I guess he wants to project onto axes, and find the point where the surface integral to the left of a point is equal to that on the right? EDIT: and don't forget: ((max_x - min_x) / 2) + min_x Cuts out an incredible one addition - probably not even one cycle nowadays! [My site] [Tetrominoes] |
|
Inphernic
Member #1,111
March 2001
|
Quote: If instead he means the middle as in the most central point, then he is explicitly thinking about bounding forms
That is what I wanted, but I can settle for a slightly simpler solution (which I should've figured out - shame on me For the curious, the original goal was to get a center point for camera to focus on if there are multiple objects in the field (so that by focusing on to that point, every object gets on the screen - of course, camera distance to that point had to be considered, but that is not a problem anymore). -- |
|
Rash
Member #2,374
May 2002
 |
|
Trezker
Member #1,739
December 2001
 |
AFAIK, there is two ways depending on what you want. Then there is the average point. Dimension by dimension sum all points and divide by the number of points. The thing I'd like to know is about optimisation. |
|
Oscar Giner
Member #2,207
April 2002
|
Quote: How can this be done as fast as possible? with the min/max method is quite easy: keep somwhere these min/max and update them accordingly when you move/add/delete a point. Note: if you chage a lot of points every frame, thne this may get slower. -- |
|
gillius
Member #119
April 2000
|
If you are talking about having a situtation of being able to remove or add a single point from a large set after initial calculation: The average version is probably easier, because the algorithm doesn't require branching if you want the average point, but for the bounding box method you will have to check if the point is a maximum or a minimum, and if so, find the new max or min (for each dimension). Gillius |
|
David Layne
Member #2,053
March 2002
|
How exactly do you define the 'middle point'? What if you have four points arranged to form a perfect square. Which one is considered the middle? Anyway, if the problem amouts to just finding the median of a list, it can be done in O(n) time. There is a quick selection method that can select the n'th element from any list by performing a series of partitions that is guarnteed to take no more than 10n or so operations. |
|
Zaphos
Member #1,468
August 2001
|
David: I think that he does not want the middle-most point of the set, but, rather, he wants to generate a new point which is in the "middle" of the set of existing points -- so for the case of a perfect square, it would just be the average position of them all the points in the set. Overall, though, it's not clear what middle means, as was mentioned throughout this thread.
|
|
Trezker
Member #1,739
December 2001
|
Once you've got the initial max, min or total values you should keep them if you're going to change the set of points. |
|
|
).