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

[j00ey]

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

[Atom]

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

[j00ey]

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

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

 

 

[Shalinar]

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

[j00ey]

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