Is the aircraft flying inside the safe zone?

Question

I have the latitude and longitude say $(x_i, y_i), i = 1, 2, \ldots n$ ordered ooints on the boundary of the the safe flying zone. I also have the coordinates of the current location of an aircraft $(x_c, y_c)$. Using this information, how can we tell if the aircraft is inside the safe-zone or not. For the sake of simplicity, we can assume that the earth's surface is flat.

Edit: The following are the (longitude, latitude) coordinates and the polygon is concave in my case.

56.06   26.21
56.13   25.36
56.35   25.00
55.35   24.00
55.12   22.42
52.58   22.94
51.47   24.03
53.14   25.94
53.57   26.04
55.2    25.38
56.06   26.21

Answer 1

I think this works. With using Polygon formulas, if we have $n$ points in the plane, with determinant we may find the area of the polygon. Let $$P_1\Big|\begin{array}{r}x_1\\y_1\end{array},\,\,\,P_2\Big|\begin{array}{r}x_2\\y_2\end{array},\,\,\,P_3\Big|\begin{array}{r}x_3\\y_3\end{array},\,\,\,\cdots\,\,\,,\,\,\,P_n\Big|\begin{array}{r}x_n\\y_n\end{array}$$ are vertices of polygon, then the area of polygon is \begin{eqnarray*} S=\frac12 \Big[ \left|\begin{array}{rr}x_1&x_2\\y_1&y_2\end{array}\right| + \left|\begin{array}{rr}x_2&x_3\\y_2&y_3\end{array}\right| %+\left|\begin{array}{rr}x_3&x_4\\y_3&y_4\end{array}\right| + \cdots + \left|\begin{array}{rr}x_{n-1}&x_n\\y_{n-1}&y_n\end{array}\right| + \left|\begin{array}{rr}x_n&x_1\\y_n&y_1\end{array}\right| \Big] \end{eqnarray*} now we add a point $Q_c(x_c,y_c)$, which lies between $P_i$ and $P_{i+1}$, if $S_{new}$ be the area of points $$P_1~,P_2~,\cdots~,P_i~,Q_c~,P_{i+1}~,\cdots~,P_n$$ then if $S_{new}<S$, the point $Q_c$ is interior of polygon.

Adding a point interior of polygon makes the area of it smaller.

Answer 2

The ray-casting (even-odd) algorithm is easy to implement and about as efficient as can be.

The basic idea is to count the number of times the sides of the polygon cross a ray directed outward from $(x_c,y_c).$ An odd number means you’re inside, even means outside.

A simple choice is the ray parallel to the $x$-axis in the positive direction. For each consecutive pair of vertices of the polygon, if one of the $y$-coordinates is less than or equal to $y_c$ and the other is greater than $y_c,$ and if the line between those vertices intersects the line $y=y_c$ to the right of $(x_c,y_c),$ count this as crossing the ray. Otherwise you ignore that pair of vertices.

You may want to check to make sure no vertex coincides with $(x_c,y_c),$ and that when you find an intersection with $y=y_c$ it does not occur exactly at $(x_c,y_c).$ This covers the case where the aircraft is on the perimeter of the polygon. But if that has the same effect as “outside” with respect to your requirements, you might not bother with that.

Unless the polygon zig-zags up and down across the line $y=y_c$ a lot, you can deal with most of its sides just by comparing a couple of $y$ coordinates. If the polygon has many sides you might only need to compute intersections for a very few if any of them. (Note that if both vertices’ $x$-coordinates are greater than $x_c$ then the intersection is on the right side of $(x_c,y_c).$)

---

I’ve actually spent some time working on the complementary problem (keeping the aircraft out of a region with a polygonal boundary) and found that even on a spherical model of the Earth this algorithm is relatively straightforward, in case you need to do this some day without the flat-earth assumption.