there was a very similar post from a few weeks ago, link it down here

the main point is, if for each point you want to find the closest destination point, the order in which you process the starting points matters a lot

for instance, in this stupid basic case, connecting start points 1, 2 with destination points A, B
if you process point 1 first, that point will connect to A generating line 1-A
but if you process point 2 first, itâ€™s point 2 that will connect to A generating line 2-A

so, for any given set of start and destination points with same amount of elements, the order in which the starting points are processed makes the world of difference

The 2nd C# â€¦ well â€¦ â€śbestâ€ť prox path itâ€™s a complex thing (the correct Method [kinda a variation of the MCMF algorithm] is used mostly in Steiner Graphs and the likes). Get the simple classic looped proximity that works â€¦ until it doesnâ€™t (from approx the mid of the collection and up).

thereâ€™s also a brute force algo, but you probably donâ€™t want that since it checks for every possible pair of points â†’ by permuting on list b â†’ meaning it takes forever to calculate AND for large lists it doesnâ€™t fit in comp memory-> then returning the list that has the smallest sum of distances (may not be unique) (does not check for intersection of lines)

to make this more managable, you could use a set number of random permutations (say max 100 000)

a smarter algorithm would be to iteratively remove the pair that gives the the smallest distance from the two lists â†’ but this might not return the smallest possible sum of distances â†’ however it should be good enough for most cases

Thanks, was thinking about that too. I have somewhere around ten points, but even then, if Iâ€™m not mistaken, that means quite a number of possibilities: 10! = 3628800

Interesting idea.

Genetic algorithm may also work, which would involve crossing over permutations.

To speed up things, one can precompute all possible distances and store them in a list. For ten points, thatâ€™s just: 10 Ă— 10 = 100

3rd option does that as follows: finds the prox pair, then marks both positions/pt indices as used (by removingâ€™m from the Point3dList) and goes on to the next pair. This means that every pair has unique pts/indices â€¦ or no pair shares pts/indices with any other.User controls the N of pairs computed.

Obviously I could very easily change that - as an option (â€śkindaâ€ť like the 1/2nd work).

# Finds the shortest connection between two lists of points where:
#
# * Each point is connected to exactly one point in the other list.
#
# * "Shortest" is defined as the shortest total length of all connections.
#
# Felix E. Klee <felix.klee@inka.de>
import ghpythonlib.treehelpers as th
import Rhino
import rhinoscriptsyntax as rs
def sumOfDistances(indexes):
sum = 0
for i, ds in enumerate(distances):
sum += ds[indexes[i]]
return sum
# Heap's algorithm
def permutation(a, size):
global bestSum, bestIndexes
if size == 1:
sum = sumOfDistances(a)
if (sum < bestSum):
bestSum = sum
bestIndexes = a.copy()
return
for i in range(size):
permutation(a, size - 1)
sizeIsOdd = size & 1
if sizeIsOdd:
a[0], a[size - 1] = a[size - 1], a[0]
else:
a[i], a[size - 1] = a[size - 1], a[i]
def computeDistances():
distances = []
for i, point1 in enumerate(points1):
distancesFromPoint1 = []
for j, point2 in enumerate(points2):
distancesFromPoint1.append(point1.DistanceTo(point2))
distances.append(distancesFromPoint1)
return distances
def findBestIndexes():
global bestSum, bestIndexes
bestIndexes = list(range(len(points1)))
bestSum = sumOfDistances(bestIndexes)
permutation(bestIndexes, len(bestIndexes))
def buildConnectionLines():
lines = []
for i, bestIndex in enumerate(bestIndexes):
line = rs.AddLine(points1[i], points2[bestIndex])
lines.append(line)
return lines
def validateInput():
if len(points1) != len(points2):
raise ValueError("Point list lengths don't match.")
validateInput()
distances = computeDistances()
findBestIndexes()
connection = buildConnectionLines()

In the 3rd option the order has no meaning at all.

Reason?

After findind the closest pair (where obviously thereâ€™s just one possible pair around no matter the pts order in the 2 collections) â€¦ then the next steps (up to the user defined N of pairs) simply donâ€™t include/compute the pts previously sampled. So for each â€śstepâ€ť the algo works as if the previously sampled pts (in pairs) are removed from the 2 collections.

Meaning: order has nothing to do in this gameâ€¦ Anyway I could include a LINQ jitter option (just one line of code) to prove the obvious â€¦ but why bother?

Plus: for prox Pts matters ALWAYS use Point3dList otherwise youâ€™ll wait toooo much for answers (if your collections are big). All that prior implementing a thread safe // approach (that may or may not be the faster bunny).