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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

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

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

Ответ 5

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

Ответ 6

Нить здесь, упомянутая в другом ответе, дает формулу параметризации для трехмерного круга: 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 двух переменных является поверхностью над a 2pi квадратом 2pi в плоскости s, t, и это минимум, что вы после. Вы можете определить его стандартными методами исчисления, например. как описано здесь.

Ответ 7

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