cartesian algorithm

einstein_7 · June 1, 2009, 11:23am

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?

dail · June 1, 2009, 11:46am

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.

Abidos · June 1, 2009, 12:09pm

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,

RickyBlender · June 1, 2009, 12:20pm

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

Thanks

Ricardo_arg · June 2, 2009, 11:09pm

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!

einstein_7 · June 24, 2009, 11:23am

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.

einstein_7 · June 24, 2009, 11:24am

can’t wait to see the quad tree code!

dail · June 24, 2009, 11:38am

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.

einstein_7 · July 2, 2009, 11:37am

Thanks! i’ll check it out.

einstein_7 · July 24, 2009, 11:24am

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!!

RickyBlender · July 24, 2009, 11:31am

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

karamelo · July 24, 2009, 11:36am

RickyBlender · July 24, 2009, 11:45am

i’m taking about this algo

BpyMesh_octree

where cani find this

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

Thanks

einstein_7 · August 15, 2009, 11:15am

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.

einstein_7 · September 26, 2009, 12:07pm

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
#========================================================

SPACIAL TREE - Seperate Class - use if you want to

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)

einstein_7 · September 26, 2009, 12:08pm

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):
	''' this was added
	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():

#print len(curve)

#curve=ob[0].data[0]

for p in [Vector(2,1.4,-0.94),Vector(-0.3,2,-0.32)]:

x,y,z=p

#print x,y,z

#meoctree.getVertsInRange(Vector(x,y,z),None,-10,clverts,‘2D’)

meoctree.findclstintsct(Vector(x,y,z),3,clverts,‘2D’)

clverts.sort()

print clverts[:]#[0][0].co#.co,clverts[1]

#def main():

Window.WaitCursor(1)

t = sys.time()

print

print ‘start’

print

exe()

# Timing the script is a good way to be aware on any speed hits when scripting

print ‘My Script finished in %.4f seconds’ % (sys.time()-t)

Window.WaitCursor(0)

#main()

andycircus · September 26, 2009, 3:26pm

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

Uncle_Entity · September 26, 2009, 5:45pm

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.