1

Topic: Circles in three-dimensional space

In three-dimensional space two circles are given. For each of circles are given: triple of coordinates of center; unit vector of a normal to a plane in which the circle lies; and radius. If it is pleasant to someone, it can increase at once a normal vector by radius and  that the circle is set by two vectors. It is required, for the general case, to find coordinates of pair the nearest points lying on different circles. If it simplifies the decision, the cases possessing any kind of symmetry when such pairs of points more than one, it is possible to throw out from reviewing. For the cases having more of one local minimum,  to find only one, giving the least distance. The task has applied relevance (in area collision detection), therefore is quite comprehensible, if the decision is received in the form of one or several transcendental equations of one variable. (Which then can be solved numerical methods and to hammer into the table). It is possible to pass from Cartesian coordinate system to any convenient (spherical, cylindrical and even actually invented specially for this task). Over this task I fought already almost about twenty years ago but so it and was not gave to me. It was possible to solve the similar task for a circle and a straight line. Here I also thought: and you never can tell, and suddenly, somebody solves.

2

Re: Circles in three-dimensional space

Hello, rg45, you wrote: R> In three-dimensional space two circles are given. For each of circles are given: triple of coordinates of center; unit vector of a normal to a plane in which the circle lies; and radius. If it is pleasant to someone, it can increase at once a normal vector by radius and  that the circle is set by two vectors. It is required, for the general case, to find coordinates of pair the nearest points lying on different circles. R> if it simplifies the decision, the cases possessing any kind of symmetry when such pairs of points more than one, it is possible to throw out from reviewing. R> the task has applied relevance (in area collision detection), therefore is quite comprehensible, if the decision is received in the form of one or several transcendental equations of one variable. (Which then can be solved numerical methods and to hammer into the table). R> It is possible to pass from Cartesian coordinate system to any convenient (spherical, cylindrical and even actually invented specially for this task). R> Over this task I fought already almost about twenty years ago but so it and was not gave to me. It was possible to solve the similar task for a circle and a straight line. Here I also thought: and you never can tell, and suddenly, somebody solves. Would explain on a simple example what steams of points to you are necessary. Enough only one such minimum pair to find or all possible? P.S. In case analytical the decision is not allowed to eat such : we throw on a circle electrical charges which pritjagivajutsja/make a start to each other and it is iterated we move them, modeling their sliding on circles under actions of forces of an attraction-pushing away.

3

Re: Circles in three-dimensional space

Hello, apachik, you wrote: A> would Explain on a simple example what steams of points to you are necessary. Enough only one such minimum pair to find or all possible? So explained If it simplifies the decision, the cases possessing any kind of symmetry when such pairs of points more than one, it is possible to throw out from reviewing. A> P.S. In case analytical the decision is not allowed to eat such : we throw on a circle electrical charges which pritjagivajutsja/make a start to each other and it is iterated it is moved them, modeling their sliding on circles under actions of forces of an attraction-pushing away. Before I and itself guessed

4

Re: Circles in three-dimensional space

Hello, rg45, you wrote: R> It is required, for the general case, to find coordinates of pair the nearest points lying on different circles. R> the task has applied relevance (in area collision detection), therefore is quite comprehensible, if the decision is received in the form of one or several transcendental equations of one variable. If the theory, and practical result I would advise to take library OpenCASCADE was necessary to you not, to create two circles and to give the task to find the nearest points. Most easier to write the code on a C ++, especially examples are applied on library on similar subjects. If the theory after you will make it is necessary, come in the code of library which caused at the decision of the practical task and look as there at all it is arranged. And all is arranged there completely not simply if not to tell on the contrary. Life you will spend, that it is all to study.

5

Re: Circles in three-dimensional space

Hello, velkin, you wrote: V> If the theory, and practical result I would advise to take library OpenCASCADE was necessary to you not, to create two circles and to give the task to find the nearest points. Most easier to write the code on a C ++, especially examples are applied on library on similar subjects. If the theory after you will make it is necessary, come in the code of library which caused at the decision of the practical task and look as there at all it is arranged. And all is arranged there completely not simply if not to tell on the contrary. Life you will spend, that it is all to study. Well, the practical result was necessary to me twenty years ago. Now me it interests as an etude more. But for thanks council, I will glance, as soon as appears more free time.

6

Re: Circles in three-dimensional space

Cool problem. While it turned out to write out distance from a point to a circle. And basically it is clear how to solve now it is iterated. Type binary search it is necessary points on sections of the second circle where distance function will behave it is convex.

7

Re: Circles in three-dimensional space

Hello, rg45, you wrote: R> It is possible to pass from Cartesian coordinate system to any convenient (spherical, cylindrical and even actually invented specially for this task). R> Over this task I fought already almost about twenty years ago but so it and was not gave to me. It was possible to solve the similar task for a circle and a straight line. Here I also thought: and you never can tell, and suddenly, somebody solves. The difficult equation 4 + levels there turns out, for practical needs analytically not to solve, only approximations.

8

Re: Circles in three-dimensional space

Hello, apachik, you wrote: A> a cool problem. While it turned out to write out distance from a point to a circle. And basically it is clear how to solve now it is iterated. Type binary search it is necessary points on sections of the second circle where distance function will behave it is convex. Here approximately so I and  then. But here there is an ambush - local minima there can be more than one (and even more than two) and there is a problem of the correct choice of initial approach.

9

Re: Circles in three-dimensional space

Hello, Nik, you wrote: N> the difficult equation 4 + levels There turns out, for practical needs analytically not to solve, only approximations. Indeed. But for the related task a circle-straight line the equation which does not have the analytical decision (I do not remember already a level - the third or ) too turned out. And here, with passage in cylindrical coordinates, the task it was possible to reduce to transcendental the equations with a sine in one of parts. So can, here again it will be possible to receive something similar?

10

Re: Circles in three-dimensional space

Hello, rg45, you wrote: R> Hello, apachik, you wrote: A>> a cool problem. While it turned out to write out distance from a point to a circle. And basically it is clear how to solve now it is iterated. Type binary search it is necessary points on sections of the second circle where distance function will behave it is convex. R> here approximately so I and  then. But here there is an ambush - local minima there can be more than one (and even more than two) and there is a problem of the correct choice of initial approach. Probably, because minima can be four also the biquadratic equation turns out, whatever one may do. Though as there there are symmetric, that is chances of the equation only the second level...

11

Re: Circles in three-dimensional space

Hello, rg45, you wrote: R> Here approximately so I and  then. But here there is an ambush - local minima there can be more than one (and even more than two) and there is a problem of the correct choice of initial approach.  the simple

12

Re: Circles in three-dimensional space

Hello, apachik, you wrote: A> it is visible, because minima can be four also the biquadratic equation turns out, whatever one may do. Though as there there are symmetric, that is chances of the equation only the second level... For an estimation of a level of a polynom it is necessary to consider an amount of all extrema, and not just minima And is still such , as contrary flexure points which occasionally are easy for accepting for an extremum (for example, y = x 3 at x = 0). And still saddle points. In general, .

13

Re: Circles in three-dimensional space

I understood. The excellent coffin for acm-kontesta turned out. A problem that jury it is necessary  to write the operating decision and tests)))

14

Re: Circles in three-dimensional space

Hello, apachik, you wrote: A> I understood. The excellent coffin for acm-kontesta turned out. A problem that jury it is necessary  to write the operating decision and tests))) Well, we will not hurry up.

15

Re: Circles in three-dimensional space

Hello, rg45, you wrote: R> In three-dimensional space two circles are given. For each of circles are given: triple of coordinates of center; unit vector of a normal to a plane in which the circle lies; and radius. If it is pleasant to someone, it can increase at once a normal vector by radius and  that the circle is set by two vectors. It is required, for the general case, to find coordinates of pair the nearest points lying on different circles. Probably, something useful is at Eberly: https://www.geometrictools.com/Document … ircle3.pdf https://www.geometrictools.com/Document … lipse3.pdf

16

Re: Circles in three-dimensional space

Hello, Nik, you wrote: N> Hello, rg45, you wrote: R>> Here approximately so I and  then. But here there is an ambush - local minima there can be more than one (and even more than two) and there is a problem of the correct choice of initial approach. N> simple In  the problem of local minima is not necessary to Nejronka, since there high dimensionality and local minima turn around saddle points, and here dimensionality 3...