Учитывая набор единичных направлений в 3D d_1, ..., d_n,
Как найти самый плотный конус вокруг них?
Например. Как мне найти другой единичный вектор m и скалярное значение alpha, представляющее угол, такой, что:
foreach i, AngleBetween(m, d_i) ‹ альфа
и альфа минимальна.
Добавлено примечание: направления могут охватывать более половины пространства. В таком случае под «конусом» мы подразумеваем набор полулиний, начинающихся с вершины конуса и в пределах заданного угла от оси конуса.
Если все ваши направления попадают в одно полупространство через начало координат, то вы можете вычислить выпуклую оболочку вершин вектора на сфере с единичным радиусом, что дает выпуклый многоугольник на этой сфере, а затем найти наименьший круг, описывающий этот многоугольник . Вы можете избежать сферических вычислений путем проецирования на подходящую плоскость.
Я понимаю, что это абстрактное представление, и вам, вероятно, нужен более конкретный совет, но он все же может помочь: выпуклая оболочка + минимальный описанный круг.
Если ваш набор направлений охватывает более полупространства, вам нужно будет определить, что вы подразумеваете под «конусом» в этом случае.
Это задача линейного программирования.
Найдите a, p, максимизирующие cos(a) при условии:
px*d1x+py*d1y*pz*d1z >= cos(a)
px*d2x+py*d2y*pz*d2z >= cos( a)
...
px*dnx+py*dny*pz*dnz >= cos(a)
Я бы посмотрел на алгоритмы LP. Тем временем я решил очень похожую проблему, которая может стать отправной точкой: https://github.com/VictorDavis/GeoConvexHull. Вы правы, как только вы найдете выпуклую оболочку, вы сможете найти минимальную описывающую окружность. Однако оказывается, что доказать, что n точек лежат в одном полушарии, нетривиально. Возможно, этот алгоритм можно адаптировать для решения вашей задачи о «самом маленьком конусе».
