我有一组问题，我有多个坐标，我想快速检测该坐标在预制框列表中的位置。
我为这类问题提供了一个代码。但我使用的是"；对于循环"；迭代，考虑到我目前处理大数据的情况，我认为这相当缓慢。设置后，我可能会有数千个方框(矩形/正方形(和坐标。
我正在寻找任何其他可能高效快速解决此类问题的替代方案？
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
pad = 1
xn1 = np.linspace(0-(pad*2), 0+(pad*2), 3)
yn1 = np.linspace(0-(pad*2), 0+(pad*2), 3)
print(xn1, yn1)
xn1_list = []
yn1_list = []
xy1_list = []
# Create the coordinates
for p1 in range(0, len(xn1)):
for q1 in range(0, len(yn1)):
xn1_list.append(xn1[p1])
yn1_list.append(yn1[q1])
for pad1, coord1 in enumerate(zip(xn1_list, yn1_list)):
xy1_list.append(coord1)
print('nxy1_list',xy1_list)
# Plot
fig, (ax1) = plt.subplots(figsize = (8,8))
for i in range(0, len(xy1_list)):
# print(len(xy3_list))
plt.scatter(xy1_list[i][0],xy1_list[i][1])
ax1.add_patch(Rectangle(xy=(xy1_list[i][0]-(pad*2)/2, xy1_list[i][1]-(pad*2)/2) ,width=pad*2, height=pad*2,
linewidth=1, color='blue', fill=False))
ax1.annotate(i, xy=(xy1_list[i][0], xy1_list[i][1]), textcoords='data', fontsize = 15)
plt.xticks(np.arange(-3, 3.1, step=1))
plt.yticks(np.arange(-3, 3.1, step=1))
# Current coordinate
X_cur, Y_cur = 0.5,2
plt.scatter(X_cur, Y_cur, color='r', marker='x')
# Iterate every possible box in the list
for i in range(0,len(xy1_list)):
Xmin_temp, Xmax_temp = xy1_list[i][0]-pad, xy1_list[i][0]+pad
Ymin_temp, Ymax_temp = xy1_list[i][1]-pad, xy1_list[i][1]+pad
# Check if the current coordinate is in one of the boxes
if (Xmin_temp < X_cur <= Xmax_temp) & (Ymin_temp < Y_cur <= Ymax_temp):
print('Current Coordinate is in Box'+str(i)+' with a centre coordinate of ('+str(xy1_list[i][0])+', '+str(xy1_list[i][1])+')')
将结果可视化：在此处输入图像描述
根据@Green Cloak Guy创意编辑的版本
from math import floor, ceil
subdivisions = {} # hashtable of subdivisions of the graph
# key format: 2-tuple (x, y)
# value format: 4-tuple (left, right, bottom, top)
...
# Plot
fig, (ax1) = plt.subplots(figsize = (8,8))
for i in range(0, len(xy1_list)):
print('nCenter Coord of the box'+str(i)+' - '+str(xy1_list[i]))
# renaming your variables to be easier to work with
# assuming [x, y] is center of each square
width = height = pad * 2 # note that you could have differently-shaped rectangles
left = xy1_list[i][0] - (width / 2)
right = xy1_list[i][0] + (width / 2)
bottom = xy1_list[i][1] - (height / 2)
top = xy1_list[i][1] + (height / 2)
print('x1:'+str(left)+' x2: '+str(right)+' y1: '+str(bottom)+' y2: '+str(top))
# add rectangle to plot, as you do in your code
plt.scatter(xy1_list[i][0], xy1_list[i][1])
ax1.add_patch(Rectangle(xy=(xy1_list[i][0]-width/2, xy1_list[i][1]-height/2), width=width, height=height,
linewidth=1, color='blue', fill=False))
ax1.annotate(i, xy=(xy1_list[i][0], xy1_list[i][1]), textcoords='data', fontsize = 15)
# # add rectangle to the appropriate subdivision(s)
x, y = xy1_list[i][0], xy1_list[i][1]
subdivisions.setdefault((x,y), [])
subdivisions[(x,y)].append((left, right, bottom, top))
...
# Current coordinate
X_cur, Y_cur = 0.5,2
plt.scatter(X_cur, Y_cur, color='r', marker='x')
# find box(es) coordinate is in
# in this case, that would be the box going from (0, 0) to (2, 2),
# which, in the coordinate dictionary, would be (0, 0)
boxes_contained = [
box
for box in subdivisions.get((x,y),[])
if (box[0] <= X_cur <= box[1]) and (box[2] <= Y_cur <= box[3])
]
但它不会返回包含的框中的任何内容。如何根据新代码修复此问题？
我用于这类问题的解决方案是将整个网格细分为可管理的小片段，并在每个片段中跟踪哪些矩形(或其他对象(与它们相交。然后，当我们有一个点时，我们可以简单地找到该点在网格的哪一段，并且我们只需要对矩形总数的子集进行测试。通过在矩形列表上迭代一次，这相对容易做到。
from math import floor, ceil
sub_size_x, sub_size_y = 2, 2 # record the size of our subdivisions, e.g. 2x2
subdivisions = {} # hashtable of subdivisions of the graph
# key format: 2-tuple (x // sub_size_x, y // sub_size_y)
# value format: 4-tuple (left, bottom, width, height)
...
# Plot
fig, (ax1) = plt.subplots(figsize = (8,8))
for i in range(0, len(xy1_list)):
# renaming your variables to be easier to work with
# assuming [x, y] is center of each square
width = height = pad * 2 # note that you could have differently-shaped rectangles
left = xylist[i][0] - (width / 2)
bottom = xylist[i][1] - (height / 2)
right = xylist[i][0] + (width / 2)
top = xylist[i][1] + (height / 2)
# add rectangle to plot, as you do in your code
plt.scatter(left + (width / 2), bottom + (height / 2))
ax1.add_patch(Rectangle(xy=(left, top), width=width, height=height,
linewidth=1, color='blue', fill=False))
ax1.annotate(i, xy=(xy1_list[i][0], xy1_list[i][1]), textcoords='data', fontsize = 15)
# add rectangle to the appropriate subdivision(s)
for x in range(floor(left / sub_size_x), ceil(right / sub_size_x)):
for y in range(floor(bottom / sub_size_y), ceil(top / sub_size_y)):
subdivisions.setdefault((x, y), [])
subdivisions[(x, y)].append((left, bottom, width, height))
...
# Current coordinate
X_cur, Y_cur = 0.5,2
plt.scatter(X_cur, Y_cur, color='r', marker='x')
# find box(es) coordinate is in
# in this case, that would be the box going from (0, 0) to (2, 2),
# which, in the coordinate dictionary, would be (0, 0)
boxes_contained = [
box
for box in subdivisions.get((X_cur // sub_size_x, Y_cur // sub_size_y), [])
if (box[0] <= X_cur <= box[0] + box[2]) and (box[1] <= Y_cur <= box[1] + box[3])
]
(注意：我目前安装的python没有numpy或pyplot，我现在无法安装它们，所以我还没有测试这个代码。但你应该了解图片(
注意，这种方法适用于任意大小的细分，也适用于不同大小的矩形。如果要使用实际的Rectangle或其他Shape类而不是4元组值，那么可以修改代码以调用一个方法来检查交集。
理想情况下，细分的大小应确保不会复制太多信息，并且不会有太多方框与同一细分重叠。理想的尺寸取决于你正在处理的盒子的数据集，这是空间复杂性和时间复杂性之间的权衡。