3D math to calculate position

I don't know much about 3d engines and related math so this might be a simple problem. I need to calculate the position of an object (x,y,z) in a 3D environment depending on the dimensions of the environment and the number of other object already occupying said environment.

I want the objects placed into the environment to have the largest distance between other objects and the edges of the environment. For example, we have an "empty" 3D cube 300 pixels by 300px by 300px. When I place 1 object into the environment it needs to find the position that is furthest away from the edges and other objects. In this case it would be at x=0,y=0,z=0 (assuming the origin is in the center of the cube). If I now place a second object into the environment it should let me know what the position of the 2 object present are. I assume this will be:

object1   x=0,y=0,z=-75
object2   x=0,y=0,z=75

What kind of math do I need to achieve this? Assuming the environment is square or rectangular & objects do not occupy any space.

I would also further be interested to know how this calculation changes when object have a preset size (i.e. two balls, one r=30px the other r=60px). Thank you.
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

object1   x=33.6,y=33.6,z=33.6
object2   x=-33.6,y=-33.6,z=-33.6
be furthur away from the walls and each other?
What a strange algorithm! Why are you wanting to do this?
I think ozo has the right idea but not quite the right numbers. But even if his number were correct it would be only 1 solution out 4  equally correct solutions. If you had three objects the number of solutions goes up even higher but there is only one solution if you have 4 objects (all the same size).  My point being that there you wont find a single math formula which can give you all the solutions.

As for math try Pythagoras' theorem (in three space) the distance between two points is
sqrt(x^2 + y^2 + z^2).  The longest line in your cube is between two of the opposite corners e.g. (-150,-150,-150) to (150,150,150) the length of this line is sqrt(300^2 + 300^2 + 300^2) = approx 520.  Now divide the line into 3 segments = approx 173.  now reverse Pythagoras' theorem  eg sqrt((173^2)/3)) =  100. Use this value to move your starting points in the direction of the origin such that  (-50,-50,-50) is one object and (50,50,50) is the other.

CompTIA Network+

Prepare for the CompTIA Network+ exam by learning how to troubleshoot, configure, and manage both wired and wireless networks.

Well, this is a question that is quite on my level of knowledge.

It's a good thing that this is a cube. The parameters for your problem were worded for the impossible (because anything in a cube that is farthest from the eight corners, would be the center, and anywhere else would not fit your practical solution.). I'm assuming that what you're trying to do is evenly space all the objects inside the cube. Well, I'll try to explain the concept.

What you need to do, is divide the volume of the cube into equal sections, depending on how many objects are in the cube. The simplest to visualize is for two objects, shown here in figure one, a side view of your cube:
The two objects are in the exact center of each of the sections. The position of a section's object will ALWAYS be the center, for every number of objects.
|            |           |
|            |           |
|     O     |    O    |
|            |           |
|            |           |
figure one.

This is just one view (front and top). The depth position (z coordinate) of the objects is aligned with the middle of the cube (the same as your first situation of one object). Then, here comes the hard part. If you have 3, your life just got a heck of alot more difficult. You have to somehow divide the cube into 3 equal sections. I recommend splitting it in a 'Y' pattern from the side. Now we seem to think that splitting one side is the way to go, NOT! When you reach 4, it gets more complicated. You need to split the cube from the center into four interlocking pyramids. This seems simple, but the 5 is even harder. But we know that 2 plus 3 is 5, so just divide it in 2, place objects, then divide the cube by 3 ('Y' pattern), then place objects. I'm not sure, but I think you might be able to do this by just splitting things by '|' ( divide by 2 ) and 'Y' ( divide by 3 ). This might work, but I made it up on the fly, so you'll have to try it yourself. You may find more patterns to divide it by. You might also have the problem of some objects haveing the same coordinates. Beware of this. This is where my idea might find fault.
If you get this, but don't know the math, well, you could try something with sin (angle) *radius for y and cos (angle) *radius for x. But I have the feeling you're gonna need to do some line intersection, which isn't too hard. Just remember, to find the center between any given points, just get their mean (I mean average, surely you know what that is).

I hope this helps. I made it up on the fly, but I've been doing 3D programming long enough for you to be right in giving it a try.


Hi RageDBL,

If you look at your diagram, would'nt you agree that if you increased the radius of the O (without changing their position) untill they touched a wall, then the left and right walls would be touched before the top and
bottom walls?  If fact using your solution would'nt the maximum radius be 75 units?

My solution allows for a maximum radius of 86.6 units, which is the distance to origin from (50,50,50)  Note that my solution does not maximize the distances either, the nearest wall from (50,50,50) is 100 units away. That means the real solution is closer to (55,55,55) but who wants to solve the differential equation 8-(

Three points define a plane, hence the solution for 3 objects would be to first finding the largest plane that would fit in the cube and then position the thee objects on that plane The plane in question here would not be a simple bisecting plane (e.g. it would not be orthogonal to any axis). This is the same logic I used for two point - two point form a line, Once you fine the  longest line that can be made in the cube then the two object must be positioned on that line.  If you position the two objects any other way then the length of the line (from a wall through the two objects and on to the next wall) will be shorter and hence the solution will not be maximized.

In any case your solution provides a  method to approximate positioning using a programmatically  simple methodology.  If it were me I would change the problem to make the object fit inside a sphere!
True, very true. My solution doesn't necessarily maximize distances between objects. I was trying to make a simple method. The method I came up with may not be completely solid, though. It may have problems for higher numbers of objects, and numbers such as 4, where you have two patterns that the objects could be arranged in. I don't think I made myself entirely clear in the solution either, but it could inspire some ideas that would lead to the solution.
When I formulated this solution, I intentionally did not consider object radius because the questioner wanted to know how to position the objects before considering radius. Either way the radius of each object would be proportional to the number of objects in the cube.
I think that if we combined our methods, we could very well have the solution. You just need to be a little more clear in your expainations; I didn't exactly follow every word.

I didn't mention another method that would make the problem simpler to solve. It doesn't work for numbers like 3 objects, though. It only works for multiples of 4. You just divide the volume into 4 smaller cubes for each step. This would give you numbers like 1 object, 4 objects, 16 objects, then 256 objects. This is a very simple method to follow, but it doesn't exactly fit the desired solution. If it isn't significant whether you can have numbers other than multiples of 4, it would be a good idea to use this method.

this problem cannot be (analytically) solved directly
from what i understand, youre looking for the solution to a 3D centroidal voronoi diagram.  
it means that you want a minimum energy solution.
in 2D its relatively simple, but in 3D, its a whole different story.
i would try to relax your demands a little.
Speaking of relaxation, that may not be a bad way to solve your problem.
If you simulate particles in a box that repel their closest neighbors and the sides of the box,
and shake the box until they settle in a stable solution, would that meet your requirements?

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
namnoops, if you konw about 'centroidal voronoi diagram' s You ought to dish it out. I'd also very much like to know about it, too.

Oh, yess, ozo!! Relaxed demands would be good right now, but your solution is quite interesting. You repel the walls from each other, then you repel objects?, interesting, but it only might work for concave arrangements (no objects are closer to the center). Which leaves us right back where we started. Still, look into it. That solution might not be as dead as I thought it was. It actually might be it!!

It might not line up with what was said before about the maximum effect.

Still, I'm VERY interested in this 'centroidal voronoi diagram' thing. Please, tell us more!!

RageDBL  --- yes, math does intrigue me.

Does this have to happen quickly?  Because I think I could write a program that does this by working with forces in a particle engine.  Every object & wall would have to exert a force or a backwards elasticity effect.  If you write it correctly, each object would eventually come to a resting point where they're spaced out evenly.  And when it's all finally come to rest, you stop the loop and draw your results.

Check out my tutorial here...

It'll show you how elasticity, gravity, & momentum can be simulated in a program.  Hopefully this will give you some ideas.
Now I'm interested in this too.  I used an old project I have to implement this in a single pass.  No particle engine movement or manipulation was required.

This isn't exactly what you wanted, but I'm sure you could improve upon it...

  int loop = 0;
  float cube = 5; // 5x5x5 cube
  float dist = sqrt(cube*cube + cube*cube + cube*cube) / pow(MAX_PARTICLES, .33333333333);
  int loopx, loopy, loopz;
  int maxLoop = pow(MAX_PARTICLES, .33333333333);
  for (loopx=0; loopx < maxLoop; loopx++)
    for (loopy=0; loopy < maxLoop; loopy++)
      for (loopz=0; loopz < maxLoop; loopz++)
        particle[loop].x = (loopx - maxLoop*.5) * dist;  // Set X position
        particle[loop].y = (loopy - maxLoop*.5) * dist;  // Set Y position
        particle[loop].z = (loopz - maxLoop*.5) * dist;  // Set Z position
medjanAuthor Commented:
Thanks everybody for your interesting approaches, ideas and solutions. As I now understand a precise solution in three dimensional space to this problem becomes problematic as the number of objects increase (also varying radii).

As I needed this problem solved for a visualization project, I believe the idea of relaxation will provide the best solution. My next step will be to write sample code but with that I have some experience.

I’m splitting the points as there could be multiple solutions. Not fully understanding the problem prohibited me from formulating a narrower question.

I couldn't begin to suggest the code that is needed to do this, but I do have an observation that I do not see mentioned here. It would seem to me that the code would need to find the largest prime factor of the number of points. The prime number would determine the number of rays leaving the origin and therefore their realtion to each other. Then the other factor of the number of points would determine the number of points on that ray and thier placement. What I am not certain of is how to divide a cube in say 13 sections that all meet at the origin.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.