# Furthest point on regular polygon given arbitrary direction

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.

-
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) –  staame Nov 3 '13 at 9:42
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. –  Lord_Farin Nov 3 '13 at 13:56
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. –  staame Nov 4 '13 at 21:44
In that case, simply round the angle $\theta_d$ to the nearest $\frac{2\pi k}n$ and take the $k$th vertex. –  Lord_Farin Nov 4 '13 at 21:52