pairs of closest points

Hi all,

I am wondering if anyone has any advice on the problem of finding pairs of closest points in a collection of points.

By this I mean, different from what Proximity2D does, for example, if there is a cloud of 100 points, there will be 50 pairs of points, with 50 lines that are not connected to one another; or in other words, each point is only "used" once.

Thanks a lot!

Replies to This Discussion

Permalink Reply by peter fotiadis on January 17, 2017 at 12:30pm

Take one point.

Using Rhino.Collections.Point3dList find the prox point (closest) and store both in a DataTree<Point3d> branch.

remove both points from the list and continue.

Permalink Reply by peter fotiadis on January 17, 2017 at 1:47pm

For instance

Attachments:

Closest_pairs_V1.gh, 116 KB

Permalink Reply by Timothy Tai on January 17, 2017 at 2:11pm

Hi Peter,

Thanks a lot!

I'll have to take some time to take a look into the code thoroughly, but it's looking great.

Permalink Reply by peter fotiadis on January 17, 2017 at 2:55pm

And the trad update that does ... er ... hmm ... "better" things (plus a Ducati promo: makes all the difference).

Attachments:

Closest_pairs_V2.gh, 123 KB

Permalink Reply by peter fotiadis on January 18, 2017 at 12:23am

And given the opportunity ... the attached finds the closest pair between 2 point Lists. Useful in quite a few cases (for instance random trusses and the likes).

If user provides data then these are used ... if not an internal demo is on duty.

Attachments:

closest_pair_between_2Lists_V1.gh, 123 KB

Permalink Reply by Timothy Tai on February 6, 2017 at 3:40pm

Thanks a lot, Peter, this is great!

Would you have any suggestion to do the closest pairs between the two lists? instead of only one single closest pair (for example, finding next closest pair until the smaller of the lists exhaust)?

Thanks again!

Permalink Reply by peter fotiadis on February 7, 2017 at 12:05am

That's simply a case of a "bigger" loop that repeats (each previous one removes the point found per List) until the smaller List has no cookies to offer (for instance: if (!ListSmaller.Any()) break; or using a crude try{} catch{} combo or ... counting the beans etc etc).

Try it and if you hit the wall drop a word.

Permalink Reply by peter fotiadis on January 18, 2017 at 12:48am

And this finds the closest pair using 3 Methods (ranging from ultra stupid to the classic divide and conquer).

BTW: This is the ultra stupid:

Attachments: