Angular Sweep Algorithm
By using Angular Sweep, we can solve this problem in O(n2log n). The basic logical idea of this algorithm is described below.
We pick an arbitrary point P from the given set. We then rotate a circle with fixed-radius ‘R’ about the point P. During the entire rotation P lies on the circumference of the circle and we maintain a count of the number of points in the circle at a given value of Θ where the parameter Θ determines the angle of rotation. The state of a circle can thus be determined by a single parameter Θ because the radius is fixed.
Below is the implementation of the above approach:
# python program to find the maximum number of
# points that can be enclosed by a fixed-radius
# circle
import math
MAX_POINTS = 500
arr = [0] * MAX_POINTS
dis = [[0 for i in range(MAX_POINTS)] for j in range(MAX_POINTS)]
# This function returns the maximum points that
# can lie inside the circle of radius 'r' being
# rotated about point 'i'
def mycompare(A, B):
if A[0] < B[0]:
return True
elif A[0] > B[0]:
return False
else:
return A[1] == 1
def getPointsInside(i, r, n):
# This vector stores alpha and beta and flag
# is marked true for alpha and false for beta
angles = []
for j in range(n):
if i != j and dis[i][j] <= 2*r:
# acos returns the arc cosine of the complex
# used for cosine inverse
B = math.acos(dis[i][j]/(2*r))
# arg returns the phase angle of the complex
A = math.atan2(arr[j].imag - arr[i].imag, arr[j].real - arr[i].real)
alpha = A - B
beta = A + B
angles.append([alpha, True])
angles.append([beta, False])
# angles vector is sorted and traversed
angles.sort(key=lambda x: (x[0], x[1] == 1))
# count maintains the number of points inside
# the circle at certain value of theta
# res maintains the maximum of all count
count = 1
res = 1
for angle in angles:
# entry angle
if angle[1]:
count += 1
# exit angle
else:
count -= 1
res = max(res, count)
return res
# Returns count of maximum points that can lie
# in a circle of radius r.
def maxPoints(arr, n, r):
# dis array stores the distance between every
# pair of points
for i in range(n - 1):
for j in range(i + 1, n):
# abs gives the magnitude of the complex
# number and hence the distance between
# i and j
dis[i][j] = dis[j][i] = abs(arr[i] - arr[j])
# This loop picks a point p
ans = 0
for i in range(n):
# maximum number of points for point arr[i]
ans = max(ans, getPointsInside(i, r, n))
return ans
# Driver code
r = 1
arr = [complex(6.47634, 7.69628),
complex(5.16828, 4.79915),
complex(6.69533, 6.20378)]
n = len(arr)
print("The maximum number of points are:", maxPoints(arr, n, r))
Output
The maximum number of points are: 2
Time complexity: O(n2 * log n)
Auxiliary Space: O(n2)
Angular Sweep in Python
Given ‘n’ points on the 2-D plane, find the maximum number of points that can be enclosed by a fixed-radius circle of radius ‘R’.
Note: The point is considered to be inside the circle even when it lies on the circumference.
Examples:
Input: R = 1
points[] = {(6.47634, 7.69628), (5.16828 4.79915),(6.69533 6.20378)}
Output: 2
The maximum number of points is 2Input: R = 1
points[] = {(6.65128, 5.47490), (6.42743, 6.26189)
(6.35864, 4.61611), (6.59020 4.54228), (4.43967 5.70059)
(4.38226, 5.70536), (5.50755 6.18163), (7.41971 6.13668)
(6.71936, 3.04496), (5.61832, 4.23857), (5.99424, 4.29328)
(5.60961, 4.32998), (6.82242, 5.79683), (5.44693, 3.82724) |
(6.70906, 3.65736), (7.89087, 5.68000), (6.23300, 4.59530)
(5.92401, 4.92329), (6.24168, 3.81389), (6.22671, 3.62210)}
Output: 11
The maximum number of points is 11