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
– JoseKilo, Commented Oct 17, 2020 at 14:12
For faster approximate answer, you may try Monte Carlo method. — Heikki
– Heikki, Commented Oct 17, 2020 at 14:19
@Ethan not really ... check this answer 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
– JoseKilo, Commented Oct 17, 2020 at 14:41

Alain T. · Accepted Answer · 2020-10-17 16:01:42Z

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)

MBo · Accepted Answer · 2020-10-17 14:35:15Z

1

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.

answered Oct 17, 2020 at 14:35

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Comments

flabons · Accepted Answer · 2020-10-17 14:33:41Z

0

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.

edited Oct 17, 2020 at 14:33

answered Oct 17, 2020 at 14:23

flabons

3411 silver badge8 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related