CODEWITHSUNDEEP
pythonspatial
TkTech
TkTech

Reputation: 4996

Efficiently finding nearest point along a specific axis in 3D space

I have been playing with this one for a few days now, and keep running into performance walls.

The data:

The structure:

I have found a possible solution in http://docs.scipy.org/doc/scipy/reference/spatial.html, however the K-d tree seems to be extremely wasteful for this type of data (suitable more for clusters of arbitrary points) and tuned for finding points within a radius. The primary use case for this data is often finding (and following) the nearest neighbour point along each.

Example Data (x, y, z):

[(4, 3, 0), (4, 4, 0), (5, 3, 0), (3, 3, 0), (4, 3, 1), ...]

Possibly my google-fu is failing me and an optimal structure exists already (preferably in Python), but I have not been able to find one.

Upvotes: 1

Views: 1125

Answers (3)

deinonychusaur
deinonychusaur

Reputation: 7304

If only the points are counted as nearest if they follow the axis with the other axis' values static e.g. that (1,1,0) would not qualify as nearest to (0,0,0) but (4,0,0) would you could:

import numpy as np
#The .T is ofcourse not neccesary here but then you have to fix it below as well.
points = np.asarray( [(4, 3, 0), (4, 4, 0), (5, 3, 0), (3, 3, 0), (4, 3, 1)]).T
#You have still to check thiss for all points just showing for pt 0
on_same_xy = (points[:-1,:].T == points[:-1,0]).all(axis=1)

z_distance =  (points[2,on_same_xy] - points[2,0])
z_distance_up = z_distance[np.where(z_distance > 0)]
if z_distance_up.size == 0:
    up = None
else:
    up = z_distance_up.min()

z_distance_down = z_distance[np.where(z_distance < 0)]
if z_distance_down.size == 0:
    down = None
else:
    down = z_distance_down.max()

print "Z-up-neighbour %s, Z-down-neighbour %s" % (str(up), str(down))

Since you have the two first coordinate-values just of points[-1,0] then position of the up-point and down-point as well as distance can be accessed from up and down.

I realize the code got a bit messy, but once a big data-set is inside nunpy it really should work faster. Also, again, it's a question of what your question asks for.

Upvotes: 0

segasai
segasai

Reputation: 8548

How about constructing 3 KD-trees for x,y,z axes respectively ? You need some kind of tree structure anyway IMO.

Upvotes: 3

tbd
tbd

Reputation: 126

Hmm, finding "nearest to the left" and whatnot would prove tricky as you have say multiple points on x=4., it would then need to find the closes on the other axes.

Will a more simple "closest point" such as the following not work?

for n in xrange(len(points)):
   diff = (((x0-points.x[n])**2) + ((y0-points.y[n])**2) + ((z0-points.z[n])**2))**0.5

Then just weed out the 'n' with the smallest diff (excluding current point if included).. :/

Upvotes: 0

Related Questions