In a circle of radius $r$ centered at $c$, if I want to know the point on the circle that is furthest in a direction specified by a vector $d$ I use the formula $c+(r/||d||)d$.

Is there a similar (fast) way of finding the furthest vertex on a regular $n$-gon given some arbitrary direction vector $d$?


First, a general method for a possibly irregular polygon $P$, which may be suitable for implementation in computer applications:

Let a point $c$ inside the polygon be given. Effectively we're seeking the intersection of $c+\Bbb R_{\ge0}d$ with $P$.

Given the coordinates $p_0, p_1,\ldots, p_n = p_0$ of $P$, we can use linear algebra to determine $r_1,\ldots, r_n$ (and corresponding $\lambda_i$) in:

$$c+r_id = p_{i-1}+\lambda_i(p_i-p_{i-1})$$

Now if the polygon is convex, we simply take the least nonnegative $r_i$. Otherwise, we choose the least nonnegative $r_i$ subject to $0\le \lambda_i\le 1$.

For a regular polygon (for simplicity, I've assumed it to be inscribed in the unit circle; a scaling will help adapt to the general situation) and $c= 0$, we can do better. By symmetry, we can assume without loss of generality that $d$ has a angle $\theta_d$ with $0\le \theta_d \le \dfrac{2\pi}n$ ($\theta_d$ is the unique angle such that $(\cos \theta_d,\sin\theta_d)=\dfrac d{\|d\|}$). Then we can use the generic method on the chord $(1,0)$-$(\cos\frac{2\pi}n,\sin\frac{2\pi}n)$, which after some algebra yields:

$$r= \frac{\sin\frac{2\pi}n}{\sin\theta_d-\sin(\theta_d-\frac{2\pi}n)}$$

which has the expected mirror symmetry $\theta_d \mapsto \frac{2\pi}n-\theta_d$ as an argument for its correctness.

Of course, determining $\theta_d$ from $d$ can be a pain. The $\rm atan2$ function in many programming languages and computer algebra systems was designed specifically for this purpose. The $\theta_d$ for our computation would then be ${\rm atan2}(d) \pmod{\frac{2\pi}n}$.

I hope these methods are of some help to you, even though they are of limited practical value without a computer's aid.

  • $\begingroup$ Thank you for the reply. didn't get everything you said but let me go straight to the result. You are saying that the vertex furthest in directin $d$ is simply given by c+rd where $$r= \frac{\sin\frac{2\pi}n}{\sin\theta_d-\sin(\theta_d-\frac{2\pi}n)}$$ Right? The result I want must be one of the polygon's vertices (one of $p_0, \dots$ in your reply) $\endgroup$ – saadtaame Nov 3 '13 at 9:42
  • $\begingroup$ I don't have much time right now, but could you update your question to state what you mean by "the furthest vertex in the direction $d$"? For in most directions, there won't be any such vertex. So I took it to mean an arbitrary point on the polygon. $\endgroup$ – Lord_Farin Nov 3 '13 at 13:56
  • $\begingroup$ You take the dot product of the direction vector and the vertices and take the vertex that gave the max dot product as the furthest. $\endgroup$ – saadtaame Nov 4 '13 at 21:44
  • 1
    $\begingroup$ In that case, simply round the angle $\theta_d$ to the nearest $\frac{2\pi k}n$ and take the $k$th vertex. $\endgroup$ – Lord_Farin Nov 4 '13 at 21:52

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.