Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3899477 Mon, 29 Jan 2024 13:00:39 +0000 Точки на сфере https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3899477 Mikle
Цитата
Находим пару точек с минимальным дотпродуктом (то есть максимально взаимно удалённые)

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

Могу предложить модификацию варианта Mikle (критика приветствуется):
Сначала вычисляем средний 3D вектор между всеми точками в исходной системе координат.
Затем за один цикл (на лету) делаем преобразование координат точек с разворотом оси X (или Y) по этому вектору, рассчитываем углы поворота точек в горизонтальной и вертикальной плоскостях в новой системе координат с одновременным определением мин. и макс. значений этих углов.
Окончательно проверяем, что разница мин. и макс. углов в обеих плоскостях не превышает Pi.]]> leo Алгоритмы https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897662 Fri, 08 Dec 2023 07:00:15 +0000 Точки на сфере https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897662 Координаты декартовы. Считаем точки векторами.
Находим пару точек с минимальным дотпродуктом (то есть максимально взаимно удалённые). Если дотпродукт = -1, то точки полярны, условие не выполнено.
Суммируем найденные вектора, полученную сумму нормализуем, получаем вектор VN1.
Находим кросспродукт от VN1 и одного из двух первых векторов, нормализуем, получаем VN2.
Находим проекции всех оставшихся точек на плоскость, образованную векторами VN1 и VN2. Ищем углы в этой плоскости между полученными проекциями и вектором VN1. Если диапазон углов лежит в пределах Pi, то точки умещаются в одну полусферу.

Решение первой задачи можно продолжить из этого решения.]]> Mikle Алгоритмы https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897661 Fri, 08 Dec 2023 06:28:10 +0000 Точки на сфере https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897661 Известно, что есть линейный по времени от количества точек алгоритм для нахождения минимальной охватывающей сферы.
Находим такую сферу и смотрим на её радиус. Если точки лежат в одной полусфере, то радиус будет меньше 1, иначе - равен 1.
Тут плохо разделяется пограничный случай, но для моих целей этого достаточно.
Две первые задачи сводятся к третьей следующим образом. Отобразим, к примеру, второе множество точек относительно центра на противоположную сторону сферы.
Затем проверим лежат ли первое множество и отображённое второе в одной полусфере. Если да, то значит они разделяются плоскостью.]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897657 Thu, 07 Dec 2023 17:30:10 +0000 Точки на сфере https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897657
Возможно, что лучше даже работать с минимальной выпуклой оболочкой (МВО) - проверки и достроения будут проще. А потом финальным штрихом - построение МОО вокруг найденной МВО.

Ну а уж в полярных координатах сравнить МОО с полусферой - и вовсе дело плёвое.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897654 Thu, 07 Dec 2023 16:16:28 +0000 Точки на сфере https://forum.sources.ru/index.php?showtopic=440296&view=findpost&p=3897654 1. Даны два множества точек на сфере. Нужно узнать, можно ли их разделить плоскостью проходящей через центр сферы.
2. Даны два выпуклых многоугольника на сфере. Нужно узнать, пересекаются ли они.
3. Дано множество точек на сфере. Нужно узнать, лежат ли они в одной полусфере.
Надеюсь, что есть решения по времени линейно зависящие от количества точек.]]> prografix Алгоритмы