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

Question

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

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

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

---

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

Answer 1

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

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

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

UPDATE: Перечитав свой вопрос, я вижу, что даже если вы просите способ найти ближайшие пару точек на два кругов в 3-х измерениях, я думаю, вы должны уделять больше внимания к свойства кривой NURBS, которые вы пытаетесь вытеснить двумерный многоугольник. Вы отмечаете, что ориентация окружности в данной точке кривой задается касательным вектором в этой точке. Однако для 3D-кривых больше, чем только касательный вектор; есть нормальное (или кривизны) вектор , что указывает по направлению к центру кривизны кривой в данной точке, а затем есть кручения вектор, который в основном определяет количество «подъемной силы» кривой от плоскости, заданной касательной и нормальными векторами. Все они определяют рамку Frenet (что называется). Вы можете прочитать больше об этом на Wikipedia article.

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

Я думаю, что с двумя ближайшими точками вы все равно можете получить странное скручивание ... Крайний пример: предположим, что обе окружности имеют 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 6

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

Answer 7

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