Сфера, которая обязательно охватывает заданный список точек [точки с координатами x, y и z] - PullRequest
Новая
       48

Сфера, которая обязательно охватывает заданный список точек [точки с координатами x, y и z]

3 голосов
/ 21 апреля 2011

Я пытаюсь найти сферу, которая неприемлемо охватывает данный список точек.Точки будут иметь координаты x, y и z [Точки в 3D].

На самом деле я пытаюсь найти новые три точки на основе заданного списка точек с помощью некоторых вычислений, таких как find MinX, MaxX, MinY,MaxY, а также MinZ и MaxZ, сделайте некоторую операцию и найдите новые три точки

И я нарисую сферу из этих трех точек.

И я также возьму все эти три указывает на диаметр сферы, поэтому у меня есть уникальная сфера.

Существует ли какой-либо стандартный способ для нахождения охватывающей сферы данного списка точек?

Ответы [ 2 ]

3 голосов
/ 21 апреля 2011

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

По своей сути, алгоритм переставляет точки (случайным образом), чтобы найти 1-4 точки, которые лежат на границе сферы.По сути, это умный алгоритм проб и ошибок.Из этих точек вы можете найти центр, найдя точку, которая имеет одинаковое расстояние до всех этих точек.Версия Гертнера использует улучшенное числовое устройство, чтобы найти центр.Кроме того, он использует дополнительный шаг поворота, который, по-видимому, заставляет алгоритм работать лучше для большого количества входных точек.

Если все, что вам нужно, это сфера вокруг трех точек, я предлагаю вам по-прежнему использовать «устройство» Гертнерса длявычислить окружность треугольника.В противном случае метод, вероятно, будет легко вырождаться (т. Е. Когда треугольник будет очень плоским).

0 голосов
/ 21 апреля 2011

Вам нужно 3 балла или любое количество баллов?

Если вам нужен ответ только для 3 баллов, каждая пара точек определяет отрезок.Возьмите самый длинный отрезок.Возьмите сферу с центром в середине этого отрезка, радиус которого равен половине длины отрезка.Есть два случая.

  1. Третий пункт находится внутри этой начальной сферы.Если так, то у вас самая маленькая сфера.
  2. Третья точка находится за пределами этой начальной сферы.Тогда решение в Найти центр окружности из трех точек треугольника [без компаса] даст вам центр самой маленькой сферы, содержащей эти 3 точки.произвольное количество точек, я бы сделал какой-то алгоритм итеративной аппроксимации.Поскольку вам, похоже, это не нужно, я не буду прорабатывать детали.
...