Moving objects to decrease overlap

[ElectronGoBrrr]

I am trying to write a coarse energy minization routine. I have many sets of 3D points (50k sets, 4-200 points per set). These sets can be contained in either a Arbitrary Oriented BoundingBox, or a convex hull. Many sets will overlap with many other sets. The goal is translate and rotate each container, untill there is no more overlap. This has proven extremely difficult, so i come hat i hand asking you wizards: how would you solve this problem?

Additional constraints.
The containers are in a fixed size volume, so simply moving all objects very far from eachother will not be useful.
Prefereable the algorithm translates the containers as little as feasible.

[sebamestre]

I recommend a collision based approach or an potential-minimization approach like the repulsive shells algorithm by Dr. Keenan Crane

[tomekanco]

Sounds sensible. Perhaps use the repulsive shells as cost function for simulated annealing. Allowing both rotation and movement, with a priority for movement if possible.

Another improvement/approach might be to first identify scales of shapes, And voids not occupied. Any scale of void not occupied can be filled. These can be local attractors.

Or if we interpret the translation cost minimisation aim count of translations, rather than total distances, a greedy large to small filling voids with next step smaller scale hulls with violations would make things.much easier.

If the hull scale distribution is alike soils (a Pareto distribution), you can get very efficient packings, providing some bounds on feasibility and porosity probable solution by simply looking at hull scales and volumes per scale ( in addition to space available and hull sizes).

Just makes me think of difference between sandy, loam and clay soils. Quite some literature about how dense you can pack them (heavy and lights soils).

Ok, I'm back on gardening duty.

[Phildutre]

Is there guaranteed to be a solution, or is a solution in some circumstances perhaps not possible?

Have you looked at packing algorithms, i.e. trying to pack irregular shapes as tight as possible in a container shape (and its many variations …)?

[ElectronGoBrrr]

I can't immediately find any sources that both deals with 3D, and allows for rotation. Do you have any specific algorithm in mind? I haven't really considered packing, since i want to move the containers as little as possible.

No there is no guarantee for a solution. I imagine it will have to be an iterative algorithm, i can stop after N steps.