Как вычислить пару самых близких точек на двух 3-х кругах?
Проверьте jCifs в http://jcifs.samba.org/
Кроме этого, палки с LDAP (на самом деле, это должна быть моя первая попытка, но...)
7 ответов
На самом деле вы пытаетесь вычислить пару точек, которая минимизирует расстояние между точками, лежащими на двух разных кругах в трех измерениях. Метод, который вы должны использовать для поиска точного решения (как и почти во всех задачах оптимизации), состоит в том, чтобы представить расстояние как функцию всех возможных точек и взять его производную по независимым переменным и установить для полученных выражений значение 0 . Поскольку у вас 2 круга, у вас будет 2 независимых переменных (т.е. угол точки на одной окружности и одной на другой окружности). После того, как вы решите уравнения минимизации, вы также найдете точки на окружностях, которые будут удовлетворять вашему ограничению. (Обычно вы найдете углы на окружностях для пары точек, которые вы ищете.)
Я нашел статью в Интернете (на на этом сайте ), которая строго соответствует с вычислениями, но конечным результатом является решение полиномиального уравнения 8-го порядка. Вы можете попытаться упростить уравнения и придумать менее точное решение, удовлетворяющее вашим потребностям.
Существует также статья , в которой утверждается, что имеется гораздо более быстрый алгоритм для определения расстояния между двумя окружностями в 3d; однако я не могу просматривать содержимое и, следовательно, не могу сказать, дает ли он вам пару точек, которые удовлетворяют этому условию.
ОБНОВЛЕНИЕ: Перечитав ваш вопрос, я вижу, что даже если вы спрашиваете способ найти ближайшую пару точек на два круга в 3 измерениях, я думаю, вам следует уделять больше внимания свойствам кривой NURBS, по которой вы пытаетесь выдавить 2D-полигон. Вы упомянули, что ориентация окружности в данной точке кривой определяется касательным вектором в этой точке. Однако 3D-кривые - это не только касательный вектор; есть нормальный вектор (или кривизна ), который указывает на центр кривизны кривой в данной точке, а также есть вектор кручения , который в основном указывает количество «подъема» кривой из плоскости, заданной касательными и нормальными векторами. Все они определяют (так называемый) фрейм Френе. Вы можете прочитать об этом больше в статье Википедии .
Я подозреваю, что вы можете добиться желаемого эффекта, соединив точки последовательных кругов, каждая из которых лежит вдоль направления вектора нормали лежащая в основе 3D кривая. Таким образом, скручивание будет только тогда, когда кривая действительно скручивается, то есть когда вектор кручения не равен нулю и вектор нормали также меняет направление. В других случаях это должно удовлетворить вашу реальную потребность.
Вам, вероятно, не нужно излишне искать ближайшие точки на последовательных кругах.
Вы можете прочитать об этом больше в статье Википедии .Я подозреваю, что вы можете добиться желаемого эффекта, соединив точки последовательных кругов, каждая из которых лежит вдоль направления вектора нормали лежащая в основе 3D кривая. Таким образом, скручивание будет только тогда, когда кривая действительно скручивается, то есть когда вектор кручения не равен нулю и вектор нормали также меняет направление. В других случаях это должно удовлетворить вашу реальную потребность.
Вам, вероятно, не нужно излишне искать ближайшие точки на последовательных кругах.
Вы можете прочитать об этом больше в статье Википедии .Я подозреваю, что вы можете добиться желаемого эффекта, соединив точки последовательных кругов, каждая из которых лежит вдоль направления вектора нормали лежащая в основе 3D кривая. Таким образом, скручивание будет только тогда, когда кривая действительно скручивается, то есть когда вектор кручения не равен нулю и вектор нормали также меняет направление. В других случаях это должно удовлетворить вашу реальную потребность.
Вам, вероятно, не нужно излишне искать ближайшие точки на последовательных кругах.
у вас будет скручивание только тогда, когда кривая действительно скручивается, т.е. когда вектор кручения не равен нулю, а вектор нормали также меняет направление. В других случаях это должно удовлетворить вашу реальную потребность.Вам, вероятно, не нужно излишне искать ближайшие точки на последовательных кругах.
у вас будет скручивание только тогда, когда кривая действительно скручивается, т.е. когда вектор кручения не равен нулю, а вектор нормали также меняет направление. В других случаях это должно удовлетворить вашу реальную потребность.Вам, вероятно, не нужно излишне искать ближайшие точки на последовательных кругах.
Я думаю, что с двумя ближайшими точками вы все равно можете получить странное скручивание ... Крайний пример: предположим, что оба круга имеют R = 1. Если центр первого круга - O, и он находится в плоскости XY, а центр второго круга находится в X = 1, Y = 0, Z = 0,01, и он просто слегка наклонен в направлении роста X, ближайший точки на двух кругах обязательно получат «странный поворот», которого вы пытаетесь избежать. Поскольку ближайшие точки не дадут вам странного поворота в случае, если второй круг находится в X = 0, Y = 0, Z = 0,01 и имеет одинаковый наклон, то в какой-то момент утверждения «выровнены по двум ближайшим точкам на двух кругах» и «никаких странных скручиваний» больше не соответствуют друг другу.
Предполагая, что это может происходить в рамках ограничений NURBS, вот еще одна идея. Вначале возьмите три точки на кривой NURBS - две, которые принадлежат центрам ваших кругов, а третья - точно между ними. Нарисуйте плоскость между тремя. Эта плоскость пересечет два круга в 4 точках. Две из этих точек будут на одной «стороне» линии, соединяющей центры кругов - они будут вашими точками совмещения.
Для следующих точек совмещения вы должны взять точку совмещения «предыдущего круга», и нарисуйте плоскость между центром «предыдущего круга», этой точкой выравнивания и центром «нового круга». Отсюда вы получаете «следующую точку выравнивания», основанную на пересечении с другим кругом.
Следующий шаг - «предыдущий круг» = «новый круг» и «новый круг»
Расширьте окружности до плоскостей (используя центральные точки и нормали). Если плоскости параллельны, то подойдут любые точки. Если плоскости не параллельны, то они пересекаются по прямой. Постройте плоскость через два центра окружностей, перпендикулярных линии. Два круга пересекают эту новую плоскость в четырех точках. Эти четыре точки - две ближайшие точки и две самые дальние точки на кругах.
Для того, что вы описываете, достаточно выбрать точку на периметре первого круга и найти точку на периметре каждого круга вдоль, которая ближе всего к точке, выбранной для предыдущего круг; это полностью ограничит полигонизацию, без скручивания, и должно быть намного проще решить, чем общий случай - просто найдите точку на плоскости, содержащую второй круг, который ближе всего к выбранному в первом, и пересечь линию, проходящую через эта точка и центр второго круга с периметром второго круга.
Однако это может не дать такой приятной полигонизации для выдавленного цилиндра, как сохранение площади многоугольника постоянной, насколько это возможно, и для этого потребуется некоторое скручивание между соседними кругами .
Ура, если только круги не находятся в одной плоскости или параллельных плоскостях, я думаю, что единственный способ сделать это - найти минимум в уравнении расстояния между двумя точками на окружности. .
http://www.physicsforums.com/showthread.php?t=123168
Эта ссылка показывает, как получить уравнение каждого круга в трехмерном пространстве, а затем минимизировать формулу расстояния между этими уравнениями. Хотя не очень красиво, надеюсь, кто-нибудь придумает что-нибудь более умное.
The thread here, mentioned in another answer gives the parameterization formula for a 3D circle: P = R cos(t) u + R sin(t) nxu + c, where u is a unit vector from the centre of the circle to any point on the circumference; R is the radius; n is a unit vector perpendicular to the plane and c is the centre of the circle, t goes from 0 to 2pi, and by nxu I mean "n cross u". Parameterize one circle this way, and another similarly with a different parameter, say s. Then each point Pt on the first circle will have coordinates in the variable t, and each point Ps on the second circle will have coordinates in the variable s.
Write the distance function d(s,t) between Ps and Pt in the usual way (or better, the square of the Euclidean distance so you don't have to mess with the square root when you take derivatives). The graph of this function d of two variables is a surface over a 2pi by 2pi square in the s,t plane, and it's minimum is what you're after. You can determine it with the standard calculus methods, e.g. as explained here.
Разве это не просто вопрос построения линии между двумя центрами кругов / сфер и нахождения точки пересечения линии и окружностей? Это наиболее близкие решения (если кружки не пересекаются, то ответ зависит от того, как вы хотите интерпретировать этот случай).