Jump to content

How to find closest point that hasn't already been found

Recommended Posts

Can anyone give me a pointer as to how to approach this.

I have two point clouds with the same number of points. I want to pair the points based on proximity so that each point in each cloud is paired. The sticking point of course is that if I just do a point cloud look up and pick the closest point I get multiple points in point cloud A paired with the same point in point cloud B.

My vague idea, which sounds very clumsy and slow is to do something like this in a solver:

1 - group all points in both point clouds, say unpaired_A_grp and unpaired_B_grp

2 - For each point in unpaired_A_grp find the distance to the closest point in unpaired_B_grp and store them in an array, also store the point numbers

3 - get the indices for the distance array using argsort

4 - reorder the point numbers with the indices, set an integer nearest_point attribute on the relevant point in point cloud A and move it from unpaired_A_grp to paired_grp_A.

5 - from point cloud B look up points in paired_grp_A and if ptnum is found in nearest_point set the same attribute and move point from unpaired_B_grp to paired_grp_B.

6 - clear 

7 - repeat until all points are paired.


I think this would work with a small number of points but if I have a million I have to run it a million times and it sounds very slow... Any ideas greatly appreciated

Share this post

Link to post
Share on other sites

Check out this thread, there are several variations finding nearest points that have not been found yet.

Share this post

Link to post
Share on other sites

Ah great thanks very much! I will have a dig around in there.

I did search the forum but obviously not well enough...



Share this post

Link to post
Share on other sites

Idk if you've already solved this, but it should be relatively easy and super duper fast to do in VOPs. I haven't looked through that other thread, but off the top of my head you could do the following:

1. Give all your B points an attribute initialized to 0 (let's say "matched"=0).
2. In VOPs, find the closest B point to the current A point, and measure it against your "matched" attribute (eg, 'And "matched" < 1').
3. Then just set the closest B point's "matched" attribute to 1, so it will fail the logic test in step 2 the next time around and won't get paired again.

Hope that helps :)

Share this post

Link to post
Share on other sites

Thanks for that.

I haven't actually got chance to look into it yet, I got given another task before I got to finish that so I'm hoping to have chance to investigate at the weekend..

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now