Let's say we've two parallel galaxies with same amount of stars. What I want to do is to find the nearest neighbour of GalaxyA in GalaxyB. But if that particular neighbour is shared by other star(closer to another GalaxyA star) then look another nearest neighbour. This way we will get unique nearest neighbour for each star. I've implemented this logic in using 4-5 different algorithms. So far below one is fastest one:
node = hou.pwd()
geo = node.geometry()
pts = geo.points()
targetpts = node.inputs()[1].geometry().points()
if len(targetpts) >= len(pts):
from operator import itemgetter
# add 'uniqueNeighbour' attribute
geo.addAttrib(hou.attribType.Point, 'uniqueNeighbour', -1)
# setup targetpts list
targetptslist = []
targetptslist = [(n, targetpt.position()) for n, targetpt in enumerate(targetpts)]
# get the distance to every point in target geo
for pt in pts:
neardistlist = []
p1 = pt.position()
neardistlist = [(targetptslist[i][0], (p1 - targetptslist[i][1]).length()) for i in range(len(targetptslist))]
# sort the list by min distance
neardistlist.sort(key = itemgetter(1))
# check the neardistlist to see if this point has already been taken then remove this from the targetptslist
nearestpt = (neardistlist[0][0])
for j in range(len(targetptslist)):
ptn = targetptslist[j][0]
if ptn == nearestpt:
del targetptslist[j]
break
if hou.updateProgressAndCheckForInterrupt(): break # respect keyboard interruption
# update 'uniqueNeighbour' attribute
pt.setAttribValue('uniqueNeighbour', nearestpt)
if hou.updateProgressAndCheckForInterrupt(): break # respect keyboard interruption
else:
raise hou.NodeError('Target points must be equal or more than source points!')
Where pts are GalaxyA stars and targetpts are GalaxyB stars. hou is software dependent module.
More readable code(same as above) without list comprehension:
node = hou.pwd()
geo = node.geometry()
pts = geo.points()
targetpts = node.inputs()[1].geometry().points()
if len(targetpts) >= len(pts):
from operator import itemgetter
# add 'uniqueNeighbour' attribute
geo.addAttrib(hou.attribType.Point, 'uniqueNeighbour', -1)
# setup targetpts list
targetptslist = []
#targetptslist = [(n, targetpt.position()) for n, targetpt in enumerate(targetpts)] # short n fast version of below loop
for n, targetpt in enumerate(targetpts):
targetptinfo = (n, targetpt.position())
targetptslist.append(targetptinfo)
if hou.updateProgressAndCheckForInterrupt(): break # respect keyboard interruption
# get the distance to every point in target geo
for pt in pts:
neardistlist = []
p1 = pt.position()
#neardistlist = [(targetptslist[i][0], (p1 - targetptslist[i][1]).length()) for i in range(len(targetptslist))] # short n fast version of below loop
for i in range(len(targetptslist)):
tptinfo = targetptslist[i]
p2 = tptinfo[1]
distance = (p1 - p2).length()
targetinfo = (tptinfo[0], distance)
neardistlist.append(targetinfo)
if hou.updateProgressAndCheckForInterrupt(): break # respect keyboard interruption
# sort the list by min distance
#neardistlist.sort(key = lambda ptdist: ptdist[1])
neardistlist.sort(key = itemgetter(1)) # faster than lambda sorting
# check the neardistlist to see if this point has already been taken then remove this from the targetptslist
nearestpt = (neardistlist[0][0])
for j in range(len(targetptslist)):
ptn = targetptslist[j][0]
if ptn == nearestpt:
del targetptslist[j]
break
if hou.updateProgressAndCheckForInterrupt(): break # respect keyboard interruption
# update 'uniqueNeighbour' attribute
pt.setAttribValue('uniqueNeighbour', nearestpt)
if hou.updateProgressAndCheckForInterrupt(): break # respect keyboard interruption
else:
raise hou.NodeError('Target points must be equal or more than source points!')
My question is: Can we optimize it more so it will be faster? Current version takes around 90 seconds for only 6000 stars, and I'm talking about millions. Using current algorithm forget about millions, it'll take just forever.
EDIT: This question is to refine algorithm. I need better way to sort and iterate over.
current algorithm: step 1 (if len(targetpts) >= len(pts)): Only run if GalaxyB have same or more number of stars. Initialize uniqueNeighbour to -1.
step 2 (targetptslist = [(n, targetpt.position()) for n, targetpt in enumerate(targetpts)]): Store GalaxyB star position in a list.
step3 (for l, pt in enumerate(pts)): Loop over GalaxyA stars to store each GalaxyB star distance in a list(neardistlist). Then sort it by minimum distance.
step 4 (for j in range(len(targetptslist))): Loop over targetptslist(outcome of step 2) to compare each element to currently added element in neardistlist(which is nearestpt) if matches then delete it from targetptslist and break out of loop
step 5: Update uniqueNeighbour variable.
EDIT 02: Now let's assume there're 5 stars in both galaxies. GalaxyA neighbour list(let's call it closestNeighbourList) in GalaxyB starting from closest to fartherest...
star 0: [4, 1, 0, 3, 2]
star 1: [2, 0, 4, 3, 1]
star 2: [2, 1, 3, 0, 4]
star 3: [0, 3, 2, 4, 1]
star 4: [0, 3, 1, 4, 2]
from these lists default first neighbour list:
star 0: [4]
star 1: [2]
star 2: [2]
star 3: [0]
star 4: [0]
Since I want unique neighbour in GalaxyB, but here you see a problem, star 2 in GalaxyB is closest to two GalaxyA stars 1 & 2 and same for star 0. So these are not unique neighbour as shared by two or more stars. So to overcome this problem what I'm doing first storing all neighbours in a list(closestNeighbourList) then looping over those to check if it's closer to(shared by) some other star then go to next neighbour and when it's find unique neighbour break out of the loop.
after applying unique neighbour algorithm first neighbour list will be:
star 0: [4]
star 1: [2]
star 2: [1]
star 3: [3]
star 4: [0]
ifblock. \$\endgroup\$