如何用更高效的时间替换嵌套的for循环？
我给出了一个矩形，其左下角和右上角的顶点坐标为(x1，y1)和(x2，y2)。一般点(x，y)在矩形外给出。并给出了一个整数值R。
现在我的目标是求出距离(x，y)小于或等于R的矩形上和内的积分点的总数。
我所做的是：
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)我的代码效率很低，而且它的时间复杂度很高，因为使用了嵌套的for循环。您能提供一种有效的方法来解决python中的同样问题吗？
示例：(x1，y1)=(0,0)和(x2，y2)=(1,1)
设(x，y)=(-8,0)和R=9
则输出必须为3，因为只有(0,0)，(1,0)和(0,1)满足条件。
回答 3
Stack Overflow用户
发布于 2020-10-17 15:21:44
通过将圆的离散点作为一系列线来处理，可以大大降低复杂性。有了这些行，不需要嵌套循环，就可以通过数学计算矩形相交点的数目。这将把复杂度从O(n^2)降到O(n)。
例如：
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视觉：
# (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)Stack Overflow用户
发布于 2020-10-17 14:35:15
求圆与矩形的交点。
将交叉口类型划分为帽(圆圈段)、扇形(扇形)、无扇区(无扇区)，也许其他类型是可能的。
用Y-坐标进行扫描，得到每一个Y在矩形和圆内对应的最后X。
将X - edgeX值添加到扇形交叉口的结果中.edgeX可能是x1，也可能是x2，这取决于圆圈所处的边缘。
对于圆帽，取两个X点，然后加上它们的差。
使用这种方法，复杂度相对于矩形大小是线性的，但是需要对交点进行分类。
Stack Overflow用户
发布于 2020-10-17 14:23:55
对于向量化的蛮力版本，可以使用numpy：
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))然而，如果你想出一种半解析的方法，你可能会变得更快。由于numpy例程的执行速度较快，该公式的计算复杂度保持在矩形面积的顺序，而预因子较低。但是问题可以归结为只看圆周的边界。并决定哪一个子集在边界内。
https://stackoverflow.com/questions/64403264
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号