Как вычислить пару ближайших точек на двух 3d кругах?

Question

У меня есть два двумерных круга в трехмерном пространстве (определяемых центром, нормалью и радиусом), и я пытаюсь найти пару точек, которая является одной из множества ближайших пар точек. Я знаю, что существует от 1 до бесконечного числа пар точек, мне просто нужна одна подходящая пара.

Есть ли простой способ сделать это? Точность не важна. Радиус обеих окружностей одинаков, ненулевое значение.

В случае, если фон полезен, мой общий алгоритм принимает кривую NURBS в пространстве и выдавливает 2d многоугольник вдоль кривой, получая деформированный цилиндр. Я просто пробую несколько точек вдоль кривой. Нормаль каждого круга - это касательная к кривой NURBS, и я пытаюсь выяснить, как выровнять соседние сэмплы, чтобы не получалось странное скручивание. Кажется, что самые близкие точки на соседних образцах должны быть выровнены.

---

Спасибо за все ответы здесь ... эта часть проекта немного затянулась, поэтому я еще не проверил все ответы. Я обязательно добавлю сюда несколько изображений и отмечу ответ, когда снова приступлю к работе.

Answer 1

То, что вы действительно пытаетесь вычислить, это пара точек, которая минимизирует расстояние между точками, которые лежат на 2 разных окружностях в 3 измерениях. Метод, который вы должны использовать, чтобы найти точное решение (как почти во всех задачах оптимизации), состоит в том, чтобы представить расстояние как функцию всех возможных точек и получить его производную по отношению к независимым переменным и установить получающиеся выражения в 0 Поскольку у вас есть 2 круга, у вас будет 2 независимых переменных (т.е. угол точки на одном круге и один на другом круге). Решив уравнения минимизации, вы также найдете точки на окружностях, которые удовлетворят вашему ограничению. (В основном вы найдете углы на кругах для пары искомых точек.)

Я нашел бумагу онлайн (на этом сайте ), которая тщательно проводит расчеты, но в результате получается решение полиномиального уравнения 8-го порядка. Вы можете попытаться упростить уравнения и найти менее точное решение, удовлетворяющее вашим потребностям.

Существует также бумага , в которой утверждается, что имеется гораздо более быстрый алгоритм для определения расстояния между двумя окружностями в 3d; однако я не могу просмотреть содержимое и, следовательно, не могу сказать, дает ли оно также пару точек, которые удовлетворяют этому условию.

ОБНОВЛЕНИЕ: Перечитав ваш вопрос, я вижу, что, хотя вы просите найти ближайшую пару точек на двух окружностях в 3-х измерениях, я думаю, вы должны заплатить больше обратите внимание на свойства кривой NURBS, которые вы пытаетесь вытянуть вдоль 2D-многоугольника. Вы упоминаете, что ориентация круга в данной точке кривой определяется касательным вектором в этой точке. Однако в трехмерных кривых есть нечто большее, чем просто касательный вектор; есть вектор нормальный (или кривизна ), который указывает к центру кривизны кривой в данной точке, а затем существует вектор кручения , который в основном определяет величину «подъема» кривой от плоскости, заданной касательной и векторами нормалей. Все они определяют (что называется) кадр Френе. Вы можете прочитать больше об этом в статье Википедии .

Я подозреваю, что вы можете достичь желаемого эффекта, соединяя точки последовательных окружностей, каждая из которых лежит вдоль направления вектора нормали базовой 3D-кривой. Таким образом, вы будете иметь закручивание только тогда, когда кривая действительно закручивается, то есть когда вектор кручения не равен нулю и вектор нормали также меняет направление. В других обстоятельствах это должно удовлетворить ваши реальные потребности.

Вам, вероятно, не нужно излишнее нахождение ближайших точек на последовательных кругах.

Answer 2

Поток здесь , упомянутый в другом ответе, дает формулу параметризации для трехмерного круга: P = R cos (t) u + R sin (t) nxu + c, где u - единичный вектор от центра круга до любой точки окружности; R - радиус; n - единичный вектор, перпендикулярный плоскости, а c - центр круга, t - от 0 до 2pi, а под nxu я подразумеваю «n пересекают u». Таким же образом параметризируйте один круг, а другой - другим параметром, скажем, s. Тогда каждая точка Pt на первом круге будет иметь координаты в переменной t, а каждая точка Ps на втором круге будет иметь координаты в переменной s.

Напишите функцию расстояния d (s, t) между Ps и Pt обычным способом (или, лучше, квадратом евклидова расстояния, чтобы вам не приходилось связываться с квадратным корнем, когда вы берете производные). График этой функции d двух переменных представляет собой поверхность над квадратом 2pi на 2pi в плоскости s, t, и это минимум того, что вам нужно. Вы можете определить это с помощью стандартных методов исчисления, например, как объяснено здесь .

Answer 3

Я думаю, что с двумя ближайшими точками вы все еще можете получить странное скручивание ... Крайний пример: предположим, что оба круга имеют R = 1. Если центр первого круга - O, и он сидит на плоскости XY, а центр второго круга - в X = 1, Y = 0, Z = 0,01, и он просто слегка наклонен в направлении роста X, ближайший точки на двух кругах наверняка получат «странный поворот», которого вы пытаетесь избежать. Поскольку самые близкие точки не дают вам странного поворота в случае, если второй круг находится в точке X = 0, Y = 0, Z = 0,01 и одинаково наклонен, то в какой-то момент утверждения «выровнены по двум ближайшим точкам на двух кругах» и «странного скручивания не видно» больше не соответствуют друг другу.

Предполагая, что это может происходить в рамках ограничения NURBS, вот еще одна идея. В начале возьмем три точки на кривой NURBS - две, которые принадлежат центрам ваших кругов, а третья точно между ними. Нарисуйте плоскость между тремя. Эта плоскость пересечет два круга в 4 точках. Две из этих точек будут находиться на одной и той же «стороне» линии, которая соединяет центры окружностей - они являются вашими точками выравнивания.

Для следующих точек выравнивания вы должны взять точку выравнивания «предыдущего круга» и нарисовать плоскость между центром «предыдущего круга», этой точкой выравнивания и центром «нового круга». Отсюда вы получите «следующую точку выравнивания», основанную на пересечении с другим кругом.

Следующий шаг - «предыдущий круг» = «новый круг», а «новый круг» - ваш следующий по кривой NURBS.

Если радиусы от центров окружностей к выбранным точкам выравнивания пересекаются, вы знаете, что картинка будет выглядеть немного некрасиво - это сценарий, в котором с алгоритмом «ближайшей точки» вы все равно получите странное скручивание.

Я думаю, что координаты точки на окружности, которая является пересечением с плоскостью, проходящей через ее центр, должно быть легко вычислено (это точка на линии, образованная пересечением двух плоскостей, одной из окружности и цели плоскость; на расстоянии R от центра).

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

Answer 4

Для того, что вы описываете, достаточно выбрать точку по периметру первого круга и найти точку по периметру каждого круга вдоль, ближайшую к той, которая была выбрана для предыдущего круга; это полностью ограничит полигонизацию без скручивания, и ее будет гораздо проще решить, чем в общем случае - просто найдите точку на плоскости, содержащую вторую окружность, которая ближе всего к выбранной в первой, и пересечете линию, проходящую через эта точка и центр второго круга с периметром второго круга.

Однако это может не привести к столь приятной полигонизации экструдированного цилиндра, как поддержание постоянной площади многоугольника, и для этого потребуется некоторое скручивание между соседними кругами.

Answer 5

Yikes, если только круги не оказываются в одной или параллельных плоскостях, я думаю, что единственный способ сделать это - найти минимум в уравнении расстояния между двумя точками на окружности.

http://www.physicsforums.com/showthread.php?t=123168

Эта ссылка показывает, как получить уравнение каждого круга в трехмерном пространстве, а затем минимизировать формулу расстояния между этими уравнениями. Не очень, хотя, надеюсь, кто-то придумает что-то более умное.

Answer 6

Расширить круги до плоскостей (используя центральные точки и нормали). Если плоскости параллельны, тогда подойдут любые точки. Если плоскости не параллельны, то они пересекаются по линии. Постройте плоскость через два центра окружностей, перпендикулярных линии. Два круга пересекают эту новую плоскость в четырех точках. Эти четыре точки - две ближайшие точки и две самые дальние точки на кругах.

Answer 7

Разве это не просто вопрос построения линии между двумя центрами окружностей / сфер и нахождения пересечения линии и окружностей? Наиболее близкими являются решения (если окружность не пересекается, тогда ответ зависит от того, как вы хотите интерпретировать этот случай).