Define regular polygon while iterating through a two-dimensional array.

Question

I apologize ahead of time if this question was already answered - I may have stumbled across it but not realized it since I'm not entirely certain what all the symbols mean even after looking them up.

I'm attempting to iterate through a two-dimensional array (grid for a game) and check if a given coordinate is within the bounds of a polygon, in this case an octagon.

I'm just can't seem to figure out what the distance should be to check for.

As an example, for a circle I can just use the Pythagorean theorem to see if "c" is less than or equal to the given radius. If it is, then I change the value in my grid for that coordinate.

If it matters, this uses quadrant I in the Cartesian coordinates grid.

Please let me know if this is too vague and I will clarify - thanks in advance to anyone who even bothers to look at this!

Answer 1

Let $S$ be a regular octagon in the $xy$-plane.

Given a point $Q$ in the $xy$-plane, the goal is to decide whether $Q$ is inside $S$, on $S$, or outside $S$.

Let $r$ be the distance from the center of the octagon to one of the vertices.

Preliminary transformations:

• $\;$Translate all points so that the center of the octagon is $(0,0)$.$\\[6pt]$
• $\;$Rotate all points about the origin so that some vertex has coordinates $(r,0)$.

Let the new coordinates of $Q$ be $(a,b)$.

Let $L:\mathbb{R}^2 \to \mathbb{R}$ be defined by $$L(x,y) = x + y(\sqrt{2}-1) - r$$ and let $v = L(a',b')$, where \begin{align*} a' &= \max(|a|,|b|)\\[4pt] b' &= \min(|a|,|b|)\\[4pt] \end{align*} The sign of $v$ is decisive:

• $\;$If $v<0$, then $Q$ is inside $S$.$\\[6pt]$
• $\;$If $v=0$, then $Q$ is on $S$.$\\[6pt]$
• $\;$If $v>0$, then $Q$ is outside $S$.

Done!

Answer 2

Let $S$ be a (not necessarily convex) simple polygon in the $xy$-plane, with $n$ sides, such that the coordinates of the successive vertices $$P_1 = (x_1,y_1),\;P_2 = (x_2,y_2),\ldots,P_n = (x_n,y_n)$$ are known.

Suppose point $Q$ has known coordinates $Q=(a,b)$.

The goal is decide whether $Q$ is inside $S$, on $S$, or outside $S$.

First test to see if $Q$ is on $S$ . . .

If $Q$ is equal to one of the vertices $P_1,...,P_n$, then of course $Q$ is on $S$.

Next, assuming $Q$ is not one of the vertices, test to see if $Q$ is on an edge, strictly between the endpoints of the edge.

For convenience, define $P_{n+1}=P_1$.

Then $Q$ is on edge $P_iP_{i+1}$, strictly between $P_i$ and $P_{i+1}$ if and only if $Q = (1-t)P_i + tP_{i+1}$, for some $t \in \mathbb{R}$ with $0 < t < 1$.

This will hold if and only if the vector equation $$(a,b) = (1-t)(x_i,y_i) + t(x_{i+1},y_{i+1})$$ has a solution with $0 < t < 1$.

Equivalently, equating corresponding coordinates, the condition is that for some $t \in \mathbb{R}$ with $0 < t < 1$, both of the equations \begin{align*} a &= (1-t)x_i + tx_{i+1}\\[4pt] b &= (1-t)y_i + ty_{i+1}\\[4pt] \end{align*} are satisfied.

So just solve the above system for $t$. If a solution exists, check to see if $0 < t < 1$.

Checking each edge in succession, you can determine whether or not $Q$ is on one of the edges, strictly between the endpoints.

Thus, you can determine whether or not $Q$ is on $S$.

Next assume $Q$ is not on $S$.

Choose some line $L$ through $Q$ which doesn't pass through any of the vertices of $S$, and is not parallel to any of the edges of $S$, and suppose $L$ has the parametric form \begin{align*} x = a + ct\\[4pt] y = b + dt\\[4pt] \end{align*} for some $c,d \in \mathbb{R}$, not both zero.

For $i=1,...n$, let $t_i$ be the value of $t$ for which the line $L$ intersects the (full) line through the vertices $P_i,P_{i+1}$, and let $Q_i$ be the corresponding intersection point.

Let $m$ be the number of points $Q_i$ for which

• $\;t_i > 0$.$\\[4pt]$
• $\;Q_i$ is on the edge $P_iP_{i+1}$, strictly between $P_i$ and $P_{i+1}$.

Note: Testing to see if $Q_i$ is on the edge $P_iP_{i+1}$, strictly between $P_i$ and $P_{i+1}$, can be done the same way as the analogous prior test for the point $Q$.

The parity of $m$ is decisive:

• $\;$If $m$ is even (possibly zero), then $Q$ is outside $S$.$\\[4pt]$
• $\;$If $m$ is odd, then $Q$ is inside $S$.

Done!

Update:

The procedure outlined above works for an arbitrary (not necessarily convex) simple polygon $S$.

For the case were $S$ is a regular octagon, it can be decided more easily$\,-\,$see my new answer.