find best fit 3d object

Question

I have a uneven 3d object and need to fit another 3d symmetrical shape (Cone or cylinder) into this. I need to rotate and expand / shrink the symmetrical shape so that we can find the largest fitting cone / cylinder into this rough object.

I have looked at few bin packing problems but all seem to be dealing with rectangular shapes only ( container as well as the object to fit) and do not seem to be exactly meet my requirements.

The algorithm should also be having optimal performance.

Answer 1

What about the paper:

FOLLERT, Frank, et al. Computing a largest empty anchored cylinder, and related problems. International Journal of Computational Geometry & Applications, 1997, 7.06: 563-580.

The abstract says:

Let S be a set of n points in ℝd, and let each point p of S have a positive weight w(p). We consider the problem of computing a ray R emanating from the origin (resp. a line l through the origin) such that minp∈S w(p) · d(p, R) (resp. minp∈S w(p) · d(p, l)) is maximal. If all weights are one, this corresponds to computing a silo emanating from the origin (resp. a cylinder whose axis contains the origin) that does not contain any point of S and whose radius is maximal. For d=2, we show how to solve these problems in O(n log n) time, which is optimal in the algebraic computation tree model. For d=3, we give algorithms that are based on the parametric search technique and run in O(n log5 n) time. The previous best known algorithms for these three-dimensional problems had almost quadratic running time. In the final part of the paper, we consider some related problems.

A pdf is here.