> I changed to KDTree in the latest commit, but using the code in this gist, taken from the tests, the new version takes about twice as long as the old one. Did I do something wrong, or can someone confirm?

hum. The code seems correct. Can you make a smaller gist that just times

Y = cdist(src_pts, tgt_pts, 'euclidean')
dist = Y.min(axis=1)

versus:

dist, _ = tgt_kdtree.query(src_pts)

?