# cartesian algorithm

H’mm i’m looking for the fastest python algorithm for finding a vert in a potentially loooong list of verts that is closest to some other point- could be origin or another vert. It seems that the main problem that I run into is that coordinates are represented by a set of numbers which means you cant use a boolean type search to locate the closest points; when then leaves the only alternative searching through the entire list!! any way to convert cartesian coords to a single number?

Here are some ideas. First of all here is the quickest way to see if a particular point is in a list. But instead of a list, use a dictionary. A dictionary uses a hash code to look up an index. Here is some psuedo code.

``````
points = {}
for vert in mesh:
x,y,z = vert.loc
points[(x,y,z)] = "" # we dont care what we associate the tuple with

# Do stuff
x = 1.0
y = 2.5
z = .005

# This is much faster than using a list, especially with alot of data
if (x,y,z) in points:
# :) Point in list
else:
# :( Point not in list

``````

This is something to keep in mind since it is faster than a list.
However, this just tells you if the point is IN the dictionary. It does not tell you what the closest point in the list is to the point. This is something I’m not experienced at. I have heard of a concept called a quad tree. It is used alot in 2D(maybe 3D) to check collisions when there is alot to check.

I suppose, you will take data from a mesh, so using

``````    lst = []
for i in range(len(me.verts)):
v = me.verts[i].co
lst.append([v.x,v.y,v.z])
lst.sort()

``````

you will strip values from verts coords into a list which is sorted at the end. This sorts the list on X,Y and Z so potentially your list will look like this:

``````
[0.10132741928100586, 2.0, 0.0]
[0.21674680709838867, 1.5, 0.0]
[0.25343704223632813, 2.5, 0.0]
[0.32291173934936523, 6.0, 0.0]
[0.5, 1.2818553447723389, 0.0]
[0.5, 1.5, 0.0]
[0.5, 2.0, 0.0]
[0.5, 2.5, 0.0]
[0.5, 2.9661068916320801, 0.0]
[0.5, 5.8457174301147461, 0.0]
[0.5, 6.0, 0.0]
[0.5, 6.2464179992675781, 0.0]
[0.54273796081542969, 3.0, 0.0]
[0.68223714828491211, 6.5, 0.0]
[0.86597919464111328, 1.0, 0.0]
[1.0, 0.89678502082824707, 0.0]
[1.0, 1.0, 0.0]
[1.0, 1.5, 0.0]
[1.0, 2.0, 0.0]
[1.0, 2.5, 0.0]
[1.0, 3.0, 0.0]
[1.0, 3.36263108253479, 0.0]
[1.0, 5.5857415199279785, 0.0]
[1.0, 6.0, 0.0]
[1.0, 6.5, 0.0]
[1.0, 6.9421653747558594, 0.0]
[1.0415630340576172, 7.0, 0.0]
[1.1649026870727539, 5.5, 0.0]
[1.1732163429260254, 3.5, 0.0]
[1.3508620262145996, 1.0, 0.0]
[1.4972610473632813, 4.0, 0.0]
[1.5, 1.4223089218139648, 0.0]

``````

Then using the algorithm for binary search in a sorted array, you’d find your value fairly quickly. In fact, that is the quickest search algorithm!!! :spin: Please note that you need to apply the search three time with a decreasing range - on X,Y and Z

Regards,

is there a way to do a B -tree search for a list ?

Thanks

the quad tree concept is the key, i am develop an script to search a point nearstest to another point, but i didnt kow that is called like that, i have done some experiment with the origen only and it is fast! in a few days i will be finish and i will upload for sharing. salutation!

Thanks for the input - i’m not sure what you mean by stripping the val’s from the coords -like take the x,y,z cords and append them as separate items in the list or simply append them as a single list so they’re not in the vector format? Could you show example code of how to search the resulting list? I’ve tried the binary search but the real problem becomes the fact that the items in the list - like -[1,3,5] and [2,-4,1] are sorted only based on the x coord because it’s the first within the sub list meaning that the closest x is found in a binary but not necessarily the closest x and y- in my case i’m not using the z.

can’t wait to see the quad tree code!

Just thought i’d let you know. There is a BpyMesh_octree that you can import from blender. The script is located in \Blender.blender\scripts\bpymodules. You might take a look at it. I dont know if it does what you are needing.

Thanks! i’ll check it out.

This octree code is probably the fastest method i’ve seen yet- basicall it finds the origin of your mesh and devides it into eight 3D quadrants or volumes then if there are more than 128 verts in a quadrant it devides it further into eight subquadrants , essentially creating a tree structure. Testing it revealed that it could find the closest vert to any given point in roughly 0.003 seconds on a dual core!!

where can we find this algo for sorting fast?

and is there a sample test file we can play with?

seems interesting for other things too!

Thanks

BpyMesh_octree

where cani find this

and if there is a sample small file showing it’s use

Thanks

It can be found in your \Blender.blender\scripts\bpymodules directory - i’ll try to upload my modified version soon - it basically allows you to easily test it on any selected mesh all you need is a simple function that supplies the octree with the mesh data of the selected mesh.

Sorry for the delay - here’s the code!!! NOTE the post didn’t quite fit so the rest of the code is in the next post simply place it below this code to execute it.

import Blender
from Blender import*
import bpy
from bpy import*
#import BPyMesh_octree
#from BPyMesh_octree import*

from Blender.Mathutils import*
#from bpy.datascene import*
DotVecs= Mathutils.DotVecs
#========================================================

# USed for getting vert is a proximity

LEAF_SIZE = 128
class octreeNode:
def init(self, verts, parent,mtx):

``````	# Assunme we are a leaf node, until split is run.
self.verts = verts
self.children = []

if parent == None: # ROOT NODE, else set bounds when making children,
# BOUNDS
try:
v= verts[0].cent*mtx
#print v
except:
v=verts[0].co*mtx
maxx,maxy,maxz= v
minx,miny,minz= maxx,maxy,maxz

for v in verts:
try:
v=v.cent*mtx
except:
v=v.co*mtx
x,y,z= v
if x&gt;maxx: maxx= x
if y&gt;maxy: maxy= y
if z&gt;maxz: maxz= z

if x&lt;minx: minx= x
if y&lt;miny: miny= y
if z&lt;minz: minz= z

self.minx= minx
self.miny= miny
self.minz= minz

self.maxx= maxx
self.maxy= maxy
self.maxz= maxz

# We have no parent to split us so split ourselves.
#self.setCornerPoints()
self.splitNode()

def splitNode(self):
if len(self.verts) &gt; LEAF_SIZE:
self.makeChildren() # 8 new children,
self.verts = None
# Alredy assumed a leaf not so dont do anything here.

def makeChildren(self):
verts= self.verts
# Devide into 8 children.
axisDividedVerts = [[],[],[],[],[],[],[],[]] # Verts Only

divx = (self.maxx + self.minx) / 2
divy = (self.maxy + self.miny) / 2
divz = (self.maxz + self.minz) / 2
# Sort into 8
for v in verts:
try:
x,y,z=v.cent*mtx
except:
x,y,z = v.co*mtx

if x &gt; divx:
if y &gt; divy:
if z &gt; divz:
axisDividedVerts[0].append(v)
else:
axisDividedVerts[1].append(v)
else:
if z &gt; divz:
axisDividedVerts[2].append(v)
else:
axisDividedVerts[3].append(v)
else:
if y &gt; divy:
if z &gt; divz:
axisDividedVerts[4].append(v)
else:
axisDividedVerts[5].append(v)
else:
if z &gt; divz:
axisDividedVerts[6].append(v)
else:
axisDividedVerts[7].append(v)

# populate self.children
for i in xrange(8):
octNode = octreeNode(axisDividedVerts[i], self,mtx)
# Set bounds manually
if i == 0:
octNode.minx = divx
octNode.maxx = self.maxx
octNode.miny = divy
octNode.maxy = self.maxy
octNode.minz = divz
octNode.maxz = self.maxz
elif i == 1:
octNode.minx = divx
octNode.maxx = self.maxx
octNode.miny = divy
octNode.maxy = self.maxy
octNode.minz = self.minz #
octNode.maxz = divz #
elif i == 2:
octNode.minx = divx
octNode.maxx = self.maxx
octNode.miny = self.miny  #
octNode.maxy = divy #
octNode.minz = divz
octNode.maxz = self.maxz
elif i == 3:
octNode.minx = divx
octNode.maxx = self.maxx
octNode.miny = self.miny #
octNode.maxy = divy #
octNode.minz = self.minz #
octNode.maxz = divz #
elif i == 4:
octNode.minx = self.minx #
octNode.maxx = divx #
octNode.miny = divy
octNode.maxy = self.maxy
octNode.minz = divz
octNode.maxz = self.maxz
elif i == 5:
octNode.minx = self.minx #
octNode.maxx = divx #
octNode.miny = divy
octNode.maxy = self.maxy
octNode.minz = self.minz #
octNode.maxz = divz #
elif i == 6:
octNode.minx = self.minx #
octNode.maxx = divx #
octNode.miny = self.miny  #
octNode.maxy = divy #
octNode.minz = divz
octNode.maxz = self.maxz
elif i == 7:
octNode.minx = self.minx #
octNode.maxx = divx #
octNode.miny = self.miny  #
octNode.maxy = divy #
octNode.minz = self.minz #
octNode.maxz = divz #
#octNode.setCornerPoints()
octNode.splitNode() # Splits the node if it can.
self.children.append(octNode)``````

# GETS VERTS IN A Distance RANGE-

``````def getVertsInRange(self, loc, normal, range_val, vertList,D):
#loc= Mathutils.Vector(loc)			# MUST BE VECTORS
#normal= Mathutils.Vector(normal)

'''
loc: Vector of the location to search from
normal: None or Vector - if a vector- will only get verts on this side of the vector
range_val: maximum distance. A negative value will fill the list with teh closest vert only.
vertList: starts as an empty list
list that this function fills with verts that match
'''
xloc,yloc,zloc= loc
try :
self.verts[0]
try:
self.verts[0].co
except:
print 'must be called on a vert octree not face'
return
except:
d=' do nothing'

if range_val&lt;0:
range_val= -range_val
FIND_CLOSEST= True

else:
FIND_CLOSEST= False

if self.children:
# Check if the bounds are in range_val,
if FIND_CLOSEST and D=='3D':
for childNode in self.children:
# First test if we are surrounding the point.
if\
childNode.minx  &lt;= xloc and\
childNode.maxx  &gt;= xloc and\
childNode.miny  &lt;= yloc and\
childNode.maxy  &gt;= yloc and\
childNode.minz  &lt;= zloc and\
childNode.maxz  &gt;= zloc:
# Recurse down or get virts.
childNode.getVertsInRange(loc, normal, -range_val, vertList,D)
else:
print 'false'
elif FIND_CLOSEST and D=='2D':
for childNode in self.children:
# First test if we are surrounding the point.
if\
childNode.minx  &lt;= xloc and\
childNode.maxx  &gt;= xloc and\
childNode.miny  &lt;= yloc and\
childNode.maxy  &gt;= yloc :
# Recurse down or get virts.
childNode.getVertsInRange(loc, normal, -range_val, vertList,D)
elif not FIND_CLOSEST and D=='3D':
#print 'notp closest'
for childNode in self.children:
# First test if we are surrounding the point.
if\
childNode.minx - range_val &lt; xloc and\
childNode.maxx + range_val &gt; xloc and\
childNode.miny - range_val &lt; yloc and\
childNode.maxy + range_val &gt; yloc and\
childNode.minz - range_val &lt; zloc and\
childNode.maxz + range_val &gt; zloc:
# Recurse down or get virts.
childNode.getVertsInRange(loc, normal, range_val, vertList,D)
elif not FIND_CLOSEST and D=='2D':
for childNode in self.children:
# First test if we are surrounding the point.
if\
childNode.minx  &lt;= xloc and\
childNode.maxx  &gt;= xloc and\
childNode.miny  &lt;= yloc and\
childNode.maxy  &gt;= yloc :
# Recurse down or get virts.
childNode.getVertsInRange(loc, normal, range_val, vertList,D)

else: # we are a leaf node. Test vert locations.
#print self.verts[0]
if D=='2D':
loc=Vector(loc.x,loc.y,0)
if not normal:
# Length only check
best=None
for v in self.verts:
co=v.co*mtx
if D=='2D':
co=Vector(co.x,co.y,0)

length = (loc - co).length
if length &lt; range_val:
#print range_val
if FIND_CLOSEST:
# Just update the 1 vert
best= (length,co)
#print length
range_val= length # Shrink the length so we only get verts from their.

else:
vertList.append((length,co))

if best and FIND_CLOSEST== True:
``````

# co=best[1].co*mtx

``````				length,coords=best
vertList+=[length,coords]
#print best

else:
for v in self.verts:
co=v.co*mtx
if D=='2D':
co=Vector(co.x,co.y,0)
length = (loc - co).length
if length &lt; range_val:
# Check if the points in front
dot= DotVecs(normal, loc) - DotVecs(normal,co)
if dot&lt;0:
vertList.append((length,co))
def findclstintsct(self,loc,range,intersectlist,D):
loc:   Vector of the location to search from
range:   maximum distance to find any faces
intersectlist:   an empty list which will contain the intersection of the closest face after the function runs
D:   the space to operate in either '2D' or '3D' 2d finds the closest face based only on x,y 3d finds closest x,y,z
'''
try :
self.verts[0]
try:
self.verts[0].verts
except:
print 'must be called with a face octree not vert'
return
except:
d='do nothing'

if D =='2D':
loc=Vector(loc.x,loc.y,0)
xloc,yloc,zloc=loc
if self.children:
#print self.children
# Check if the bounds are in range_val,
if  D=='3D':
for childNode in self.children:
# First test if we are surrounding the point.
if\
childNode.minx  &lt;= xloc and\
childNode.maxx  &gt;= xloc and\
childNode.miny  &lt;= yloc and\
childNode.maxy  &gt;= yloc and\
childNode.minz  &lt;= zloc and\
childNode.maxz  &gt;= zloc:
# Recurse down or get virts.
childNode.findclstintsct(loc,range,intersectlist,D)
else:
print 'false'
elif  D=='2D':
for childNode in self.children:
# First test if we are surrounding the point.
if\
childNode.minx  &lt;= xloc and\
childNode.maxx  &gt;= xloc and\
childNode.miny  &lt;= yloc and\
childNode.maxy  &gt;= yloc :
# Recurse down or get virts.
childNode.findclstintsct(loc,range,intersectlist,D)
else: # we are a leaf node. Test vert locations.
``````

# print self.verts[0]

``````		best=None
for f in self.verts:
if D=='2D':
cent=Vector(f.cent.x,f.cent.y,0)*mtx
elif D=='3D':
cent=f.cent*mtx
length = (loc - cent).length
if length &lt; range:
# Just update the 1 vert
best= (length,f)
#print length
range= length # Shink the length so we only get verts from their.

if best:
f=best[1].verts
v1=f[0].co*mtx
v2=f[1].co*mtx
v3=f[2].co*mtx
point=Intersect(v1,v2,v3,Vector(0,0,-100),Vector(loc.x,loc.y,100),0)
intersectlist+=[best[0],point]
``````

# END TREE

#### THIS SECTION WILL CALL THE OCTREE ON A SELECTED MESH AND FIND THE CLOSEST VERT TO A GIVEN POINT

#clverts=[]
#sc=data.scenes.active
#ob=sc.objects
#me=ob.active.getData(mesh=1)
#verts=me.verts
#faces=me.faces
#mtx=ob.active.mat
#meoctree=octreeNode(faces,None,mtx)
#def exe():

#def main():

# Window.WaitCursor(0)

#main()

I thought cartesian coordinates were a pretty inventive plot element in the CUBE movie.

For future reference (or if you want to fix that post) if you enclose the sections of code in CODE tags it will keep the formatting.