Fastest way to find if the coordinate is inside a cube
In my code, I am constantly getting a stream of 3D integer coordinates (x, y, z). Each coordinate must be checked against a list of regions to see if it is in those regions. Each area is defined by opposite high and low coordinates. If the code detects that the coordinate is in a region, it requires additional action, otherwise it will simply exit to continue searching for a match to another region, or exit entirely if the region did not match.
Since this happens so quickly, I want to go through the entire list of regions as quickly as possible, create a match, or determine that it doesn't match any, and move on to the next coordinate. What I am currently doing "works" and is good and readable (to me), but needs some optimization:
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:
I thought about nesting this so that it matches the X elements first; if X falls inside the coordinates, only then try to see that Z, and finally Y ...
What can I do to generate the fastest Python 2.7 code?
source to share
You can use all
to concatenate (and short circuit properly) the conventions.
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 inside the cube
However, it is much more understandable if you just write some class definitions and call them objects.
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
source to share
1.1) When you check if a coordinate is in a region, you need to compute six comparisons (one for each border). An idea that might help is to nest the specified comparisons so that if one of them is false, you don't bother checking the others. On average, you will compute less than six comparisons in each region (maybe three?). Here's an example in pseudocode:
# 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!!"
Consider the case of a one-dimensional coordinate space (only the x-axis), divided into N regions. In the method posted in the question, you need to do 2 comparisons by region, adding up to 2N comparisons. With the proposed method, it averages 1.5N comparisons. For the case of N³ identical cubic regions forming a larger cube of lateral N regions, initially you would need 6N³ comparisons, and now you need 2N³ + 3N² + 3N + 1 comparisons.
1.2). You can evaluate fewer comparisons if regions that have the same boundaries are nested in the same condition. For example:
# 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!!"
This should significantly reduce the computational cost in the case of cubic regions forming a larger cube, but I did not bother with the calculations.
2) You can speed up the search in the list of regions using the search tree (especially useful if the regions are not very organized like a cube of cubic regions). I suggest that you specify the regions as belonging to the parent regions. Check if the coordinate is in parent regions; if so, only then check if it belongs to regions indexed under the specified parent. In a sense, this is conceptually similar to what was done in (1.2)
source to share