ordering a list of vectors into a line

poopipe · Aug 2022

before I injure myself from repeated desk/head contact ...

I've got an array/list/whatever of vectors,

I want them ordered into a line based on proximity to the next nearest point.

i.e

point 0 connects to the nearest point,

point 1 connects to the nearest point that isn't point 0 -- and so on

I don't need to worry about closing the shape, convexity or crossing lines, I just want them sorted by the next nearest point.

I'm doing this in Java which I'm not very good at and keep getting myself tied in knots because it doesn't let me abuse the system.

stack overflow hasn't been particularly helpful which usually means it's either so simple nobody bothers asking or I'm describing the problem wrong.

If anyone knows of any sort of established algorithm in a grownup language that would probably do fine - it's not like I don't understand the problem, I'm just too bad at writing code to solve it ;)

cheers

PolyHertz · Aug 2022

If this is only for a very small number of points you can just loop through them one at a time while checking distance (via Pythagorean Theorem or whatever existing distance function you have access to) to all others you haven't already checked. If it's for a large number of positions then you may want to look into acceleration structures like a quadtree (for 2D positions) or octree (for 3D positions).

poopipe · Aug 2022

we're comfortably well under 100 points even in the worst plausible cases so that should be fine - I'm familiar enough with that sort of thing if i need to anyway.

what i'm struggling with is the algorithm . Finding the nearest point (pointB) to a point (pointA) is simple, working out how to structure the data so I can find the nearest remaining point to pointB when there are <n> points is troublesome - not least cos java doesn't let me do dirty things and I am a terrible hack.

PolyHertz · Aug 2022

I'm not really familiar with Java, but here's an example in Maxscript with a method that should be easily transferrable to other languages (assumes first position in array is the one we want to start the line with):

allPositions = for obj in selection collect obj.pos --this line can just be replaced with any list/array of positions
viableStates = #(false)
for i=2 to allPositions.count do append viableStates true

sortedPositions = #(allPositions[1])
while sortedPositions.count < allPositions.count do (
    curPnt = sortedPositions[sortedPositions.count]
    closestDist = 99999.9
    closestPnt = [0,0,0]
    closestIdx = 1
    for i=1 to allPositions.count do (
        if viableStates[i] == true do (
            curDist = distance curPnt allPositions[i]
            if curDist <= closestDist do (
                closestDist = curDist
                closestPnt = allPositions[i]
                closestIdx = i
            )
        )
    )
    if closestIdx != 1 then (
        append sortedPositions allPositions[closestIdx]
        viableStates[closestIdx] = false
    )
    else (break)
)

poopipe · Aug 2022

Thanks, that looks like it'll port over fine ..

I'd been trying to take a list of points to visit and remove things from it - which (now i'm looking at it with a hangover) is ass backwards and obviously wouldn't work.

very much appreciated :)

this

becomes this

which is what I was after

ordering a list of vectors into a line

Replies