Точки на сфере , Разные задачи

[prografix]

У меня появилось несколько задач связанных с точками на единичной сфере. Вот 3 из них.
1. Даны два множества точек на сфере. Нужно узнать, можно ли их разделить плоскостью проходящей через центр сферы.
2. Даны два выпуклых многоугольника на сфере. Нужно узнать, пересекаются ли они.
3. Дано множество точек на сфере. Нужно узнать, лежат ли они в одной полусфере.
Надеюсь, что есть решения по времени линейно зависящие от количества точек.

[Akina]

Задача сродни построению минимальной описывающей окружности (МОО) - просто не на плоскости, а на сфере. Должно неплохо решаться при работе в полярных координатах. Имея параметры текущей МОО и точку, несложно определить, внутри точка или нет. А если нет - опять же должно быть несложно построить новую МОО.

Возможно, что лучше даже работать с минимальной выпуклой оболочкой (МВО) - проверки и достроения будут проще. А потом финальным штрихом - построение МОО вокруг найденной МВО.

Ну а уж в полярных координатах сравнить МОО с полусферой - и вовсе дело плёвое.

[prografix]

Я придумал для третьей задачи такое решение.
Известно, что есть линейный по времени от количества точек алгоритм для нахождения минимальной охватывающей сферы.
Находим такую сферу и смотрим на её радиус. Если точки лежат в одной полусфере, то радиус будет меньше 1, иначе - равен 1.
Тут плохо разделяется пограничный случай, но для моих целей этого достаточно.
Две первые задачи сводятся к третьей следующим образом. Отобразим, к примеру, второе множество точек относительно центра на противоположную сторону сферы.
Затем проверим лежат ли первое множество и отображённое второе в одной полусфере. Если да, то значит они разделяются плоскостью.

Сообщение отредактировано: prografix - 08.12.23, 06:30

[Mikle]

Третья задача.
Координаты декартовы. Считаем точки векторами.
Находим пару точек с минимальным дотпродуктом (то есть максимально взаимно удалённые). Если дотпродукт = -1, то точки полярны, условие не выполнено.
Суммируем найденные вектора, полученную сумму нормализуем, получаем вектор VN1.
Находим кросспродукт от VN1 и одного из двух первых векторов, нормализуем, получаем VN2.
Находим проекции всех оставшихся точек на плоскость, образованную векторами VN1 и VN2. Ищем углы в этой плоскости между полученными проекциями и вектором VN1. Если диапазон углов лежит в пределах Pi, то точки умещаются в одну полусферу.

Решение первой задачи можно продолжить из этого решения.

Сообщение отредактировано: Mikle - 08.12.23, 08:00

[leo]

Mikle

Цитата

Находим пару точек с минимальным дотпродуктом (то есть максимально взаимно удалённые)

Вопрос: Эту задачу можно выполнить за линейное время?

Могу предложить модификацию варианта Mikle (критика приветствуется):
Сначала вычисляем средний 3D вектор между всеми точками в исходной системе координат.
Затем за один цикл (на лету) делаем преобразование координат точек с разворотом оси X (или Y) по этому вектору, рассчитываем углы поворота точек в горизонтальной и вертикальной плоскостях в новой системе координат с одновременным определением мин. и макс. значений этих углов.
Окончательно проверяем, что разница мин. и макс. углов в обеих плоскостях не превышает Pi.

Сообщение отредактировано: leo - 29.01.24, 13:37