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.

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;

Works great, thanks for the fast reply!

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:

 *
             *
          *


             *

              *

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.

Averaging will move the "middle" around if an unusually large number of points is to one side instead of the other ...

The method should depend on how the set of points were created...

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
= max_x/2 - min_x/2 + min_x
= max_x/2 + min_x/2
= (max_x + min_x)/2

Cuts out an incredible one addition - probably not even one cycle nowadays!

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).

[url http://www2.inf.ethz.ch/personal/gaertner/miniball.html]

AFAIK, there is two ways depending on what you want.
If you want the center of a bounding box defined by the most extreme points in the set, you already have the answer in the thread.
Just do it dimension by dimension, you can have any nomber of dimensions, it doesn't matter.

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.
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.

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).

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.

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.

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.
So when you add a point you just need to check it against the previous max, min or add it to the total, then calc the middle.
When removing, with the max/min method you'd need to redo the search, with the average method you just need to reduce the total by that points value.
If you're changing the set alot each time you might want to do the final calculation separately after all adding/removal. Doing it for each change would be rather stupid in that case.