Maximum Points View Angle

Given a set of points along a Cartesian coordinate system, the position of a camera angle, and an angle that represents the cameras field of view, find the rotational angle of the camera that maximizes the number of points it sees in the graph.

The following example should return 180 degrees.

This example should return 270 degrees.

The Idea: Transform this question from a 2D into 1D. If we find the angle of the camera to every other point in the graph, then we could obtain a list of angles. The angle between any two points can be found by $tan^-1(\frac{y_2 - y_2}{x_2 - x_1})$. If we sort this array, we obtain an ascending list of degrees that are between degrees 0 and 360. Iterating through this list would then allow us to rotate about the graph in the anti-clockwise direction. We know that camera can only accept points that are within the field of view of the camera, so that it would follow that if difference between any two angles in the graph are less than or equal to the field of view of the camera, then they are also viewable by the camera. To find the maximum amount of points within this field of view, we need to find a fixed window that carries the most points. We can achieve this in linear time by maintaining a left and right pointer. The algorithm for this goes a follows: first increment the right pointer until the difference between the left and right angles exceed the field of view of the camera. We can then reobtain the field of view by incrementing the left pointer until the difference between the left and right point become less or equal to the field of view. Continue rotating through this process until the right pointer reaches the final angle.

Complexity: O(nlogn) time and O(n) space, where n is the number of points

import math


def to_degrees(radians):
    degrees = (180 / math.pi) * radians
    if degrees < 0:
        return 360 + degrees
    return degrees


# relative to x-axis (0 degrees)
def angle(x1, y1, x2, y2):
    return to_degrees(math.atan2(y2 - y1, x2 - x1))


def opt_angle_fov(points, cam_pos, fov):
    """
    :param points: List[(int, int)] - x, y positions of coordinates
    :param cam_pos: (int, int)      - position of camera
    :param fov: [0, 2pi]            - frame of view (viewing angle)
    :return:
    """

    angles = sorted([angle(cam_pos[0], cam_pos[1], x, y) for x, y in points])

    # find fixed length window of fov that contains maximum points
    l_pts = len(angles)
    max_points = 0
    min_max_angle = (0, 0)
    left_i = 0
    right_i = 0
    cur_window = 0
    while right_i < l_pts - 1:
        while right_i + 1 < l_pts and left_i < l_pts and cur_window <= fov:
            right_i += 1
            cur_window = angles[right_i] - angles[left_i]

        points_encap = abs(right_i - left_i)
        if points_encap > max_points:
            max_points = points_encap
            min_max_angle = (angles[left_i], angles[right_i - 1])

        # increment (catch up) the left iterator until the
        # distance is <= the fov again
        while right_i < l_pts and left_i + 1 <= l_pts and cur_window > fov:
            left_i += 1
            cur_window = angles[right_i] - angles[left_i]

    # now return the center angle that has max fov
    # return the mid point between left
    return (min_max_angle[1] + min_max_angle[0]) / 2


t1 = [(-1, 0), (0, 1), (-1, 1), (-2, 1), (-1, 2), (0, -3),
      (3, -1), (3, -2), (4, -2), (4, -3), (4, 3)]
t2 = [(-3, 0), (-2, 0), (-1, 0), (-.5, 0), (0, 0), (.5, 0),
      (1, 0), (2, 0), (-.25, 0), (.25, 0)]

print(opt_angle_fov(t1, (2, 1), 45))  # 180
print(opt_angle_fov(t2, (0, 3), 20))  # 270