在我的代码中，我不断收到一个3D整数坐标流(x，y，z)。每个坐标都必须对照区域列表进行检查，以查看它是否在这些区域中。每个区域由相对的高坐标和低坐标定义。如果代码发现坐标在一个区域中，它将采取进一步的操作，否则它只需退出以继续寻找与另一个区域的匹配，或者如果没有匹配的区域，则完全退出。
由于这种情况发生得太快了，我想尽快浏览整个区域列表，创建一个匹配项，或者确定它不匹配任何区域，然后转到下一个坐标。我目前正在做的事情"有效"，(对我来说)很好，可读性很强，但需要一些优化：
firstcorner = self.regions["regions"][name]["pos1"]
secondcorner = self.regions["regions"][name]["pos2"]
Xmin = firstcorner[0] - 1 # XXXXXXX
Ymin = firstcorner[1] - 1
Zmin = firstcorner[2] - 1
Xmax = secondcorner[0] + 1 # XXXXXXXX
Ymax = secondcorner[1] + 1
Zmax = secondcorner[2] + 1
BX = position[0] # XXXXXXX
BY = position[1]
BZ = position[2]
inX = (BX > Xmin) and (BX < Xmax) # XXXXXXXX
inZ = (BZ > Zmin) and (BZ < Zmax)
inY = (BY > Ymin) and (BY < Ymax)
if inX and inY and inZ:
我想过嵌套这个，这样它会首先匹配X项；如果X落在坐标内，然后试着看看Z，最后是Y…
我可以做些什么来创建最快的Python 2.7代码？
您可以使用all将条件串在一起(并适当地短路)。
def point_inside(rectangle, point):
firstcorner, secondcorner = rectangle
xmin, xmax = firstcorner[0]-1, secondcorner[0]+1
yield xmin < point[0] < xmax
ymin, ymax = firstcorner[1]-1, secondcorner[1]+1
yield ymin < point[1] < ymax
zmin, zmax = firstcorner[2]-1, secondcorner[2]+1
yield zmin < point[2] < zmax
rect = (firstcorner, secondcorner)
if all(point_inside(rect, position)):
# it's inside the cube
然而，如果你只写一些类定义并将它们称为对象，这会更容易理解。
class Rectangle(object):
def __init__(self, xrange, yrange, zrange):
self.xrange = xrange # (xmin, xmax)
self.yrange = yrange
self.zrange = zrange
def contains_point(self, p):
if not all(hasattr(p, loc) for loc in 'xyz'):
raise TypeError("Can only check if 3D points are in the rect")
return all([self.xrange[0] <= p.x <= self.xrange[1],
self.yrange[0] <= p.y <= self.yrange[1]
self.zrange[0] <= p.z <= self.zrange[1]])
# BONUS!
@classmethod
def from_points(cls, firstcorner, secondcorner):
"""Builds a rectangle from the bounding points
Rectangle.from_points(Point(0, 10, -10),
Point(10, 20, 0)) ==
Rectangle((0, 10), (10, 20), (-10, 0))
This also works with sets of tuples, e.g.:
corners = [(0, 10, -10), (10, 20, 0)]
Rectangle.from_points(*corners) ==
Rectangle((0, 10), (10, 20), (-10, 0))
"""
return cls(*zip(firstcorner, secondcorner))
class Point(object):
def __init__(self, x, y z):
self.x = x
self.y = y
self.z = z
def __iter__(self):
yield from (self.x, self.y, self.z)
rect = Rectangle((0, 10), (10, 20), (-10, 0))
# firstpoint, secondpoint in this analogy would be:
# # (0, 10, -10), (10, 20, 0)
inside_point = Point(3, 15, -8)
outside_point = Point(11, 15, -8)
rect.contains_point(inside_point) # True
rect.contains_point(outside_point) # False
我发现的最简单的方法是通过检查是否有任何坐标大于两个角来询问点是否在立方体的外部：
import numpy as np
def inCube(X, corners):
"""
Check if a point `X` is inside of rectangular prison with `corners` (two points)
"""
# Where is X > corners?
greater = X > corners
# If X is greater than both corners of any axis, it is outside
inside = ~np.any(np.equal(*greater))
corners = [[0, 0, 0], [1, 1, 1]]
Xs = np.array([[.5, .5, .5],
[-.5, .5, .5]])
[inCube(X, corners) for X in Xs] # [True, False]
1.1)当您检查坐标是否在一个区域中时，您需要计算六个比较(每个边界一个)。一个可能有帮助的想法是嵌套所说的比较，这样如果其中一个是错误的，那么你就不用去检查其他的了。平均而言，每个区域计算的比较不到六个(可能是三个？)。这里有一个伪代码的例子：
# for a region that has the following bounds: ((X1,X2),(Y1,Y2),(Z1,Z2))
if(check X1):
if(check X2):
if(check Y1):
if(check Y2):
if(check Z1):
if(check Z2):
return "found it!!"
考虑一个一维坐标空间(只有x轴)划分为N个区域的情况。在问题中发布的方法中，您需要对每个地区进行2次比较，总共2N次比较。使用所提出的方法，平均可以进行1.5N的比较。对于N³相同的立方体区域形成N边区域的更大立方体的情况，最初需要6N³比较，现在需要2N³+3N²+3N+1比较。
1.2)如果共享相同边界的区域嵌套在同一条件下，则可以评估较少的比较。例如：
# regions A and B share bounds (X1,X2)
if(check X1):
if(check X2):
if(check Y1):
if(check Y2):
if(check Z1):
if(check Z2):
return "found it in region A!!"
if(check Y3):
if(check Y4):
if(check Z3):
if(check Z4):
return "found it in region B!!"
在立方体区域形成更大立方体的情况下，这应该会显著降低计算成本，但我没有费心进行计算。
2) 您可以通过使用搜索树来加快区域列表的搜索速度(如果区域没有像立方体区域那样高度组织，则特别有用)。我建议您将区域索引为属于父区域。检查坐标是否在父区域中；如果是，则仅检查它是否属于在所述父项下索引的区域。在某种程度上，这在概念上类似于(1.2)中所做的操作