CODEWITHSUNDEEP
3dgeometrydata-fitting
ALoopingIcon
ALoopingIcon

Reputation: 2368

Tightest cone fitting a set of directions

Given a set of unit directions in 3D d_1, ..., d_n,

How to find the tightest cone around them?

E.g. How can I find another unit vector m, and a scalar value alpha representing an angle, such that:

foreach i, AngleBetween(m, d_i) < alpha

and alpha is minimum.

Note added: directions can span more than an half space. In such a case with 'cone' we means the set of halflines starting from the cone apex and within a given angle from the cone axis.

Upvotes: 2

Views: 337

Answers (2)

Victor Alyn Davis
Victor Alyn Davis

Reputation: 11

This is a linear programming problem.

Find a, p maximizing cos(a) subject to:
px*d1x+py*d1y*pz*d1z >= cos(a)
px*d2x+py*d2y*pz*d2z >= cos(a)
...
px*dnx+py*dny*pz*dnz >= cos(a)

I would look into LP algorithms. Meanwhile, I've solved a very similar problem that could be a jumping off point: https://github.com/VictorDavis/GeoConvexHull. You're correct, once you DO find the convex hull, you can then find the minimum circumscribing circle. As it turns out though, proving n points lie in the same hemisphere is non-trivial. Maybe this algorithm can be tailored to answer your "smallest cone" problem.

Upvotes: 0

Joseph O&#39;Rourke
Joseph O&#39;Rourke

Reputation: 4406

If your set of directions all fall within one halfspace through the origin, then you could compute the convex hull of the vector tips on the unit-radius sphere, which yields a convex polygon on that sphere, and then find the smallest circle circumscribing that polygon. You could avoid the spherical calculations by projection to a suitable plane.

I realize this is an abstract view and you likely need more concrete advice, but it still might help: Convex hull + minimum circumscribing circle.

If your set of directions span more than a halfspace, then you would need to define what you mean by "cone" in this circumstance.

Upvotes: 1

Related Questions