Для начала вспомним некоторые определения. Сфера — это поверхность шара. Сферический сегмент — это часть сферы, ограниченная окружностью. При сечении сферы плоскостью она разделяется на два сферических сегмента. Например, полусфера — это сферический сегмент. Середина сферического сегмента — это точка на нём, равноудалённая от всех точек его границы. Заметим, что середина сегмента отличается и от центра сферы и от центра окружности — границы сегмента. Угловой размер сферического сегмента — это величина угла, вершина которого находится в центре сферы, одна сторона которого проходит через середину сферического сегмента, а другая — через одну из точек его границы. Например, угловой размер полусферы — 90°.
На сфере задана система координат, позволяющая указать положение точки с помощью её широты и долготы. Дано конечное множество точек на сфере, заданных своими координатами. Найти сферический сегмент наименьшей площади, содержащий все точки этого множества (т.е. найти координаты его середины и его угловой размер).
Здравствуйте, nikov, Вы писали:
N>На сфере задана система координат, позволяющая указать положение точки с помощью её широты и долготы. Дано конечное множество точек на сфере, заданных своими координатами. Найти сферический сегмент наименьшей площади, содержащий все точки этого множества (т.е. найти координаты его середины и его угловой размер).
Переборное решение:
— сделать триангуляцию сферы по указанным точкам
— вокруг каждого треугольника нарисовать сегмент
— отсортировать сегменты по убыванию размера
— выбросить сегменты, внутрь которых попали точки
— выбрать сегмент наибольшего размера
— взять его дополнение
Кстати, поскольку плоский угол (пропорциональный радиусу сегмента на сфере), его синус (пропорциональный радиусу окружности-сечения), телесный угол (площадь сегмента) и даже площадь сечения — выражаются друг через друга монотонно, то можно просто говорить о "размере".
К>- сделать триангуляцию сферы по указанным точкам К>- вокруг каждого треугольника нарисовать сегмент К>- выбросить сегменты, внутрь которых попали точки
Хм, надо не выбрасывать, а уменьшать сегмент, чтобы точки, попавшие внутрь "апельсиновой дольки" — сегмента сегмента, — оказались за и на окружности.
Или ещё хитрее поступить.
Взять центр треугольника, спроецировать сферу из этой точки на плоскость (центр станет бесконечностью), найти круглую оболочку точек на плоскости, спроецировать её обратно.
(Это в том случае, если окружности проецируются в окружности... в чём я не очень уверен, может ли такое быть...)
Здравствуйте, nikov, Вы писали:
К>>- вокруг каждого треугольника нарисовать сегмент N>Это ведь можно сделать двумя способами, и получить два сегмента — дополнения друг друга. Ты предлагаешь добавить их оба?
Если мы делали триангуляцию, то, естественно, нужно брать тот сегмент, чья центральная точка лежит "внутри" треугольника.
Смысл в том, что внутри треугольника заведомо нет точек, поэтому описывающая окружность и является кандидатом в круглую оболочку.
Просто на плоскости у нас круглая оболочка ровно одна, а на сфере — ну, как минимум, по количеству треугольников.
А если на сфере ровно три точки, то решение вырождается понятно как
Здравствуйте, Кодт, Вы писали:
К>А если на сфере ровно три точки, то решение вырождается понятно как
Мне кажется, что если у нас несколько точек, лежащих на окружности небольшого размера, то последний шаг твоего алгоритма получит не малый сегмент внутри этой окружности, а его дополнение.
Здравствуйте, nikov, Вы писали:
N>На сфере задана система координат, позволяющая указать положение точки с помощью её широты и долготы. Дано конечное множество точек на сфере, заданных своими координатами. Найти сферический сегмент наименьшей площади, содержащий все точки этого множества (т.е. найти координаты его середины и его угловой размер).
Построить диаграмму Вороного, например, этим алгоритмом.
За константное время проверить каждую из точек, в которой сходятся границы ячеек Вороного. Каждая такая точка — середина сферического сегмента, угол между ней и центром любой смежной ячейки — максимальный угловой размер сферического сегмента.
Получается, что решается за время O(NlogN) от количества точек.
Здравствуйте, nikov, Вы писали:
К>>А если на сфере ровно три точки, то решение вырождается понятно как
N>Мне кажется, что если у нас несколько точек, лежащих на окружности небольшого размера, то последний шаг твоего алгоритма получит не малый сегмент внутри этой окружности, а его дополнение.
Ну и нестрашно.
Если все точки собрались в одном полушарии (кстати, необязательно на одной окружности), — то между ними в этом полушарии, разумеется, будет куча треугольников.
Но ведь второе полушарие тоже должно быть покрыто треугольниками. Мы же всю сферу триангулируем.
И какой-то из этих треугольников даст нам самый большой сегмент.
Перекуём баги на фичи!
