# how to search in a list of 2d points for a specific 2d point

I'm trying to develop an addon which takes all of the individual UV vertices of two meshes.
Then it compares the target UV to the source one.
If two UV vertices match, then I want to find the vertex's 3d source position.

I'm trying to find a more efficient way to look for each target UV vertex through source UVs.
Right now, for each target UV vertex, I'm looping through every UV vertex of source UVs until I find the same one.
I wanted to see if there is any better way to do it or not.

• Related blender.stackexchange.com/questions/170318/… ie make a 2D "UV bmesh" from the uv coordinates. Int layers are used to keep the corresponding index of the original. In hindsight the loop index could possibly more easily be matched to the original. A bmesh can be fed into a BVHTree to match coordinates of one to other. Nov 10, 2020 at 4:17
• stackoverflow.com/questions/7571635/… Nov 10, 2020 at 8:27

A KDTree is a structure for fast comparison/search based on 3D coordinates (more information here).

In your context, you can create a KDTree from the uvs of the first object (translating 2d coordinates into 3d for the KDTree).

Then loop over the uvs of the second and query the KDTree using find (or find_n, find_range depending on what you exactly need).

find will return a tuple of (coordinate, index, distance) of the vertex that is found.

The script.

import bpy
import time
from mathutils import Vector, kdtree

def make_kd_from_uvs(uvs):
#Create a kd tree
size = len(uvs)
kd = kdtree.KDTree(size)
#Populate it
for i, uv in enumerate(uvs):
kd.insert(uv.uv.to_3d(), i) #With 3d coordinates
#Prepare for querying
kd.balance()
return kd

def loop_to_vertex_map(obj):
#Create an array of loop indices to vertex indices
polygons = obj.data.polygons
return [v for p in polygons for v in p.vertices]

def compare_kd(obj1, uv_name1, obj2, uv_name2):
#Get uvs for each
uvs1 = obj1.data.uv_layers[uv_name1].data
uvs2 = obj1.data.uv_layers[uv_name2].data

#Get maps to look up from loop indices to vertex indices
map1 = loop_to_vertex_map(obj1)
map2 = loop_to_vertex_map(obj2)

#Make a kd tree from the first
kd = make_kd_from_uvs(uvs1)

#Loop over the second
for index2, uv2 in enumerate(uvs2):
co2 = uv2.uv.to_3d() #With 3d coordinates
#Query the kd tree
co1, index1, distance = kd.find(co2)
uv1 = uvs1[index1]

v1 = obj1.data.vertices[map1[index1]]
v2 = obj2.data.vertices[map2[index2]]

#print(v1.co, v2.co)
#print(uv1.uv, uv2.uv)

obj1 = bpy.data.objects["Cube"]
obj2 = bpy.data.objects["Cube.001"]

start = time.time()
compare_kd(obj1, "UVMap", obj2, "UVMap")
end = time.time()
print(end-start)

• Great! Thanks! but I wanted to find their 3d position as well. To be exact, I want to find the same UV in the source object, then find it's original 3d position. Nov 10, 2020 at 8:48
• Should mention that in the question... but answer edited. Nov 10, 2020 at 9:07
• Question edited. Thanks for mentioning. But I couldn't figure out the last function. How should I use that exactly? Nov 10, 2020 at 9:25