Field of View of a Point on a 2D Cartesian Plane

Question

Say I have nothing but some points randomly placed in different (x,y) positions on a 2-Dimensional plane. When examining a single point, I want to find out the degree range of points that exist around it. Say there are points only on the left side of the point that we want to examine, and not in a vertical line with it, then the angle of view of that point would have to be less than 180. If there were other points on the vertical line as well as to the left, it would be exactly 180. I want to generalize this to find the exact field of view for any point if I know the positions of all points. By generalized, I mean that this is easy to see in a problem or figure, but I want to form as an algorithm for randomly placed points in code.

Answer 1

Several ideas.

Find the angles from your single point to all pairs of the other points. The largest gap (modulo $2\pi$) in that set of angles will be the complement of the field of view.

If the single point happens to be in the convex hull of the others the field of view will be greater than $\pi$. I hope that makes sense in your application.

If you have or find the convex hull of the other points (there are algorithms for that) you can apply the above algorithm to the set of vertices.

Edit in response to comment.

A naive brute force calculation to find the field of view for each of the points calls for finding the three angles of each of the triangles, so $$ 3 \binom{n}{3} = \frac{n(n-1)(n-2)}{2} $$ dot products, then dividing by vector lengths. You can speed that up by finding the vector lengths just once, and finding the third angle in each triangle by subtraction. With the right data structure you should be able to read off the fields of view when you're done.