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.


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

Ship navigation

  • $\begingroup$ 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. $\endgroup$ – Gribouillis Dec 29 '17 at 8:35
  • $\begingroup$ What do you mean by “cross the point?” $\endgroup$ – amd Dec 29 '17 at 8:46
  • $\begingroup$ @amd I mean, that the point will lie on the circle. $\endgroup$ – Spook Dec 29 '17 at 8:47
  • $\begingroup$ On the implied circle or on the actual broken-line path? $\endgroup$ – amd Dec 29 '17 at 8:50
  • $\begingroup$ @amd On the circle itself. $\endgroup$ – Spook Dec 29 '17 at 8:51

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.

  • $\begingroup$ Jusr for clarity, cot means cotangens? (I'm familiar with notation ctg) $\endgroup$ – Spook Dec 29 '17 at 12:24
  • $\begingroup$ Could you please break down the equations? Did you use form (x-a)^2+(y-b)^2-r^2=0? $\endgroup$ – Spook Dec 29 '17 at 14:14
  • $\begingroup$ @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. $\endgroup$ – amd Dec 29 '17 at 19:42
  • $\begingroup$ 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... $\endgroup$ – Spook Dec 30 '17 at 7:51
  • $\begingroup$ @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. $\endgroup$ – amd Dec 30 '17 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.