How to replace nested for loop with something more time efficient?

Question

I have given a rectangle whose lower left and upper right vertex coordinates are given as (x1,y1) and (x2,y2). A general point (x, y) is given outside the rectangle. and an integer value R is also given.

Now my objective is to find total number of integral points on and inside the rectangle whose distance from (x,y) is less than or equal to R.

What I did is:

n=0
for i in range(x1, x2+1, 1):
    for j in range(y1, y2+1, 1):
        if (i-x)**2+(j-y)**2<=R2:
            n+=1

print(n)

My code is very inefficient and its time complexity is high as nested for loops have been used. Can you please provide an efficient method to solve the same problem in python?

Example: (x1,y1)=(0,0) and (x2,y2)=(1,1)

let (x,y)=(-8,0) and R=9

then output must be 3 as only (0,0),(1,0) and (0,1) satisfies the conditions.

A nested list comprehension would be equally time inefficient, wouldn't it ? — JoseKilo, Oct 17 '20 at 14:12
For faster approximate answer, you may try [Monte Carlo method](https://en.wikipedia.org/wiki/Monte_Carlo_method). — Heikki, Oct 17 '20 at 14:19
@Ethan not really ... check this answer https://stackoverflow.com/a/22108640 maybe there is a tiny improvement, but at the bytecode level, they are essentially the same. Anyway, OP is asking about improving the time complexity. — JoseKilo, Oct 17 '20 at 14:41

Alain T. · Answer 1 · 2020-10-17T16:01:42.360

You can greatly reduce the complexity by approaching the circle's discrete points as a series of lines. With those lines, counting the number of intersecting points with the rectangle can be done mathematically without a nested loop. This will reduce the complexity from O(n^2) down to O(n).

For example:

x1,y1 = (0,0)
x2,y2 = (1,1)
x,y   = (-8,0)
R     = 9

n = 0 
for cy in range(y-R,y+R+1):           # cy: vertical coordinate of circle's lines
    if cy not in range(y1,y2+1):          # no vertical intersection
        continue
    dx  = int((R**2-(cy-y)**2)**0.5)      # width of half circle at cy
    cx1,cx2 = x-dx,x+dx                   # edges of circle at line cy
    if cx2<x1 or cx1>x2: continue         # no horizontal intersection
    n += min(x2,cx2)-max(x1,cx1)+1        # intersection with cy line

print(n) # 3

Visually:

# (x1,y1)          -----      y+3  ... no vertical intersection 
#     XXXXXXXXXXX---------    y+2  ... intersect line at y+2 with x1..x2
#     XXXXXXXXXX-----------   y+1  ... intersect line at y+1 with x1..x2
#     XXXXXXXXXX-----o-----   y    ... intersect line at y+0 with x1..x2
#     XXXXXXXXXX-----------   y-1  ... intersect line at y-1 with x1..x2
#     XXXXXXXXXXX---------    y-2  ... intersect line at y-2 with x1..x2
#     XXXXXXXXXXXX -----      y-3  ... no horizontal intersection
#     XXXXXXXXXXXX 
#     XXXXXXXXXXXX
#             (x2,y2)

score 1 · Answer 2 · answered Oct 17 '20 at 14:35

Find points of intersection of the circle with rectangle.

Classify intersection type as cap (circle segment), as sector-like, as segment without sector, perhaps other types are possible.

Scan by Y-coordinate and for every Y get corresponding last X inside rectangle and circle.

Add X - edgeX value to result for sector-like intersection. edgeX might be x1 or x2 depending on which edge is intesected by the circle.

For circle cap take two X-points and add their difference.

With this approach complexity is linear relative to rectangle size, but some efforts needed to classify intersection.

flabons · Answer 3 · 2020-10-17T14:33:41.963

You can use numpy for a vectorized bruteforce version:

import numpy as np
P_x,P_y=-8,0
R=9
x_min,x_max=0,1
y_min,y_max=0,1

xx,yy=np.meshgrid(np.arange(x_min,x_max+1),np.arange(x_min,x_max+1))
distances=((xx-P_x)**2+(yy-P_y)**2)

print(distances)
print(np.sum(distances<=R**2))

However you will probably even get faster by thinking out a semianalytic approach. The computational complexity of this formulation remains of the order of the area of the rectangle with a lower prefactor due to the higher execution speed of numpy routines. But the problem can be reduced to only looking at the boundaries of the circle. And deciding which subset of points lies within the boundaries.

How to replace nested for loop with something more time efficient?

3 Answers3