4

A spaceship is moving through 2-dimensional space by a series of jumps. Each jump consists of rotating right and flying forward. The angle of rotation is always the same and the distance flown forward is always the same. Thus, ship is flying circles around some point.

Flying a ship

There's a special point marked in space. The question is: with given angle, how far should the ship travel with each jump, such that circle he's flying will cross the point? (ship does not necessarily need to hit the point). Is there only one solution?

Ship may turn left or right, but this decision must be made before starting flying, later it always turns the same way each jump.

Result

Just for fun, this is my ship navigation algorithm, that was developed with amd's aid:

Ship navigation

Spook
  • 946
  • Hint: you could perhaps consider the problem in the complex plane where rotation is multiplication by $\omega = e^{i\theta}$. The position after $n$ steps can be computed with geometric series. – Gribouillis Dec 29 '17 at 08:35
  • What do you mean by “cross the point?” – amd Dec 29 '17 at 08:46
  • @amd I mean, that the point will lie on the circle. – Spook Dec 29 '17 at 08:47
  • On the implied circle or on the actual broken-line path? – amd Dec 29 '17 at 08:50
  • @amd On the circle itself. – Spook Dec 29 '17 at 08:51
  • Is the initial direction of the ship fixed or also a parameter? – amd Dec 29 '17 at 08:54
  • @amd It is fixed, but if it simplifies the calculations, you may think of it a little bit differently: the angle of rotation may be, say, 5° and the ship will turn right or 355° and the ship will turn left. In general, the point is reachable only if it is on the right side of vertical line drawn through the initial position (when turning right). We may assume, that captain chose correct rotation to reach the point. – Spook Dec 29 '17 at 08:57

1 Answers1

3

Assuming that the initial heading of the ship is upwards (in the positive $y$ direction) and that $\theta$ increases clockwise, let $d$ be the hop distance. W.l.o.g. we can assume that the ship starts at the origin. Its first two hops will take it to $(d\sin\theta,d\cos\theta)$ and $(d\sin\theta+d\sin2\theta,d\cos\theta+d\cos2\theta)$. We now have three points on the implied circle and can immediately write down its equation in the form $$\det\begin{bmatrix}x^2+y^2 & x & y & 1 \\ x_1^2+y_1^2 & x_1 & y_1 & 1 \\ x_2^2+y_2^2 & x_2 & y_2 & 1 \\ x_3^2+y_3^2 & x_3 & y_3 & 1 \end{bmatrix} = 0,$$ specifically, $$\det\begin{bmatrix}x^2+y^2 & x & y & 1 \\ 0&0&0&1 \\ d^2 & d\sin\theta & d\cos\theta & 1 \\ d^2(\cos\theta+\cos2\theta)^2+d^2(\sin\theta+\sin2\theta)^2 & d(\sin\theta+\sin2\theta) & d(\cos\theta+\cos2\theta) & 1 \end{bmatrix} = 0$$ which simplifies to $$x^2+y^2-\left(d\cot\frac\theta2\right)x+dy = 0.\tag{*}$$ (Subtract the third row from the fourth to simplify the computation of this determinant.) Solving this for $d$ yields $${x^2+y^2 \over x\cot\frac\theta2-y}.$$ If $d\lt0$, i.e., if $x\cot\frac\theta2\lt y$, that means that the circle would have to be traversed backwards: the target point can’t be reached with the given turn rate.

* This equation is equivalent to $\left(x-\frac12d\cot{\frac\theta2}\right)^2 + \left(y+\frac d2\right)^2 = \left({d \over 2\sin{\frac\theta2}}\right)^2 = {d^2\over 2-2\cos\theta}$, which could be useful if you need to know more about the circle.

amd
  • 53,693
  • Jusr for clarity, cot means cotangens? (I'm familiar with notation ctg) – Spook Dec 29 '17 at 12:24
  • Could you please break down the equations? Did you use form (x-a)^2+(y-b)^2-r^2=0? – Spook Dec 29 '17 at 14:14
  • @Spook Yes, $\cot$ means cotangent. For the equation, I just expanded the determinant and simplified the resulting expression. Converting that into the $(x-a)^2+(y-b)^2-r^2=0$ form is trivial: expand the latter to get $x^2+y^2-2ax-2by+(a^2+b^2-r^2)=0$ and match up coefficients. – amd Dec 29 '17 at 19:42
  • Thanks for the clarification. One final question, where did the determinant come from? I know of matrix-based way of solving series of linear equations, but that doesn't seem to be the case here... – Spook Dec 30 '17 at 07:51
  • @Spook The determinant actually comes from a system of linear equations. There’s a succinct explanation of the method here. It’s applicable to a broad variety of geometric problems. – amd Dec 30 '17 at 08:07
  • That's simply awesome :) Thanks for the solution and the source :) – Spook Dec 31 '17 at 00:06
  • Are you sure, that angle increases counter-clockwise? Small positive values (like 5 degrees) yields positive X and Y and if the rotation was counter-clockwise, X should be negative. (by the way, this suits my needs even better). – Spook Jan 01 '18 at 21:03
  • @Spook Good catch. Fixed. – amd Jan 01 '18 at 22:22
  • By the way, this may be approached also from the perspective of circle segment: https://en.wikipedia.org/wiki/Circular_segment – Spook May 25 '18 at 09:18
  • @Spook Write up an answer that uses it! – amd May 25 '18 at 18:10