Sorting position array by shortest distance

By Tweekazoid · 2015-04-09

Description

hi,
i would like to ask how to make sorting faster.
lets say that the posArr is collection of random positions and I need to sort them by distances so that>
posArr[n + 1] asi clossest point to posArr[n]
and
posArr[n + 2] asi clossest point to posArr[n + 1]
and so on....


-- random positions 1000
posArr = for i = 1 to 1000 collect random [-100,-100,0] [100,100,200]

fn sortByMin v1 v2 mN:[-100,-100,0] = ---- sorting by minimum
(
local d1 = distance v1 mN
local d2 = distance v2 mN
case of
(
(d1 < d2) : -1
(d1 > d2) : 1
default: 0
)
)


fn compareDistance v1 v2 pA:#() pass:1 = --- sorting by distance to pos
(
if pass > 1 then
(
local p0 = pA[pass-1]
)
else local p0 = pA[pass]
local d1 = (distance v1 p0)
local d2 = (distance v2 p0)
case of
(
(d1 < d2) : -1
(d1 > d2) : 1
default: 0
)
)

fn compareNeighbArr pA = ( --- for loop for search at next array index
qsort pA sortByMin
for i in 1 to pA.count-1 do
(
qsort pA compareDistance pA:Pa pass:i start:i
)
)

clearlistener()

st = timestamp()
compareNeighbArr posArr
t= timestamp() - st

format "sorted in % s " (t / 1000.0)
format "%" (distance posArr[1] posArr[2]) -- test 1 2
format "%" (distance posArr[1] posArr[3]) -- test 1 3

----
right now it takes 11 seconds for 1000 member array
but 45 seconds for 2000 array

And I need to make it much much faster

Comments (4)

pixamoon · 2015-04-15

Hi,

If you still need it, I tried some sorting methods and I got to 2s for 1000 array and 10s for 2000 array,

but trying to sort :
posArr[n + 1] asi clossest point to posArr[n]
and
posArr[n + 2] asi clossest point to posArr[n + 1]
and so on....

In some point the closest pos to previous is totaly on other side of space/line...

When I quickly tried your method it sorted only in growing order starting closest to 0... (without finding smallest distance between 2 points)

For eg this random Z axis 0 to 200:

posArr = for i = 1 to 1000 collect random [100,100,0] [100,100,200]

It sorted only z positions like this: 0.1,0.5,1,1.25,5,10,15,16,22,28,39...

After some tests I got something like this:


(
	clearlistener()
	t = timestamp()

	posArr = for i = 1 to 2000 collect random [100,100,0] [100,100,200]
	distArr = #()
	sortedPosArr = #()

------------------------------------------------------------------- find smallest distance --   collect array with distance and 2 points  ---------------------------------------
	posArr2 = for o in posArr collect o
	for i = 1 to posArr2.count where posArr2[i] != undefined do (
		local shortestdist = 99999999
		local sub = #()
		for j = 1 to posArr2.count where i != j and posArr2[j] != undefined and (d = distance posArr[i] posArr[j]) < shortestdist do (
			shortestdist = d
			sub = (if i < j then #(shortestdist, i, j) else #(shortestdist, j, i))
		)
		if sub[1] != undefined then appendifUnique distArr sub
		posArr2[i] = undefined
	)
	posArr2 = for o in posArr collect o
------------------------------------------------------------------- finds next closest point --------------------------------------------------------------------------------------------
	fn findShortestDa a shortestdist:99999999 c: = (
		for j = 1 to posArr2.count where posArr2[j] !=undefined and (d = distance a posArr2[j]) < shortestdist do (shortestdist = d; c = j) 
		#(shortestdist, c)
	)
------------------------------------------------------------------ sort by distance -------- array with distance and 2 points ----------------------------------------------------------
	fn compareDist v1 v2 = 
		case of (
			(v1[1] > v2[1]): 1
			(v1[1] < v2[1]): -1
			default: 0
		)
	qsort distArr compareDist
----------------------------------------------------------------- collect 2 points of smallest distance	
	a = posArr2[(distArr[1][2])]
	b = posArr2[(distArr[1][3])]
----------------------------------------------------------------- remove them from pos array
	posArr2[(distArr[1][2])] = undefined
	posArr2[(distArr[1][3])] = undefined
----------------------------------------------------------------- find if a or b has closest point		
	c = (findShortestDa a)
	d = (findShortestDa b)
----------------------------------------------------------------- append 3 points to array
	if c[1] > d[1] then (
		append sortedPosArr a 
		append sortedPosArr b
		append sortedPosArr posArr2[d[2]]	
		posArr2[d[2]] = undefined
	)
	else (
		append sortedPosArr b 
		append sortedPosArr a
		append sortedPosArr posArr2[c[2]]
		posArr2[c[2]] = undefined
	)
------------------------------------------------------------------- collect and find next closest point   ------ delate used points from array
	
	for i = sortedPosArr.count+1 to posArr.count do (
		a = ((findShortestDa sortedPosArr[(sortedPosArr.count)])[2])
		append sortedPosArr posArr2[a]
		posArr2[a] = undefined
	)
	
	totalTime = ((timestamp() - t)/1000)

	print sortedPosArr
	print sortedPosArr.count
	print totalTime
)

Hope it helps a bit,
Best,

pixamoon · 2015-04-15

ah, maybe this is better
it sorts 2000 array in 9s

But it still find smallest distance on beggining and then look for next points.


(
	clearlistener()
	t = timestamp()

	posArr = for i = 1 to 2000 collect random [100,100,0] [100,100,200]
	distArr = #()
	sortedPosArr = #()

------------------------------------------------------------------- find smallest distance --   collect array with distance and 2 points  ---------------------------------------
	posArr2 = for o in posArr collect o
	for i = 1 to posArr2.count where posArr2[i] != undefined do (
		local shortestdist = 99999999
		local sub = #()
		for j = 1 to posArr2.count where i != j and posArr2[j] != undefined and (d = distance posArr[i] posArr[j]) < shortestdist do (
			shortestdist = d
			sub = (if i < j then #(shortestdist, i, j) else #(shortestdist, j, i))
		)
		if sub[1] != undefined then appendifUnique distArr sub
		posArr2[i] = undefined
	)
	posArr2 = for o in posArr collect o
------------------------------------------------------------------- finds next closest point --------------------------------------------------------------------------------------------
	fn findShortestDa a shortestdist:99999999 c: = (
		for j = 1 to posArr2.count where (d = distance a posArr2[j]) < shortestdist do (shortestdist = d; c = j) 
		#(shortestdist, c)
	)
------------------------------------------------------------------ sort by distance -------- array with distance and 2 points ----------------------------------------------------------
	fn compareDist v1 v2 = 
		case of (
			(v1[1] > v2[1]): 1
			(v1[1] < v2[1]): -1
			default: 0
		)
	qsort distArr compareDist
----------------------------------------------------------------- collect 2 points of smallest distance	
	a = posArr2[(distArr[1][2])]
	b = posArr2[(distArr[1][3])]
----------------------------------------------------------------- remove them from pos array
	deleteItem posArr2 distArr[1][2]
	deleteItem posArr2 distArr[1][2]
----------------------------------------------------------------- find if a or b has closest point		
	c = (findShortestDa a)
	d = (findShortestDa b)
----------------------------------------------------------------- append 3 points to array
	if c[1] > d[1] then (
		append sortedPosArr a 
		append sortedPosArr b
		append sortedPosArr posArr2[d[2]]	
		deleteItem posArr2 d[2]
	)
	else (
		append sortedPosArr b 
		append sortedPosArr a
		append sortedPosArr posArr2[c[2]]
		deleteItem posArr2 c[2]
	)
------------------------------------------------------------------- collect and find next closest point   ------ delete used points from array
	
	for i = sortedPosArr.count+1 to posArr.count do (
		a = ((findShortestDa sortedPosArr[(sortedPosArr.count)])[2])
		append sortedPosArr posArr2[a]
		deleteItem posArr2 a
		if posArr2.count == 0 do exit
	)
	
	totalTime = ((timestamp() - t)/1000)

	print sortedPosArr
	print sortedPosArr.count
	print totalTime
)

if you to declare 0 position [100,100,0]
then it can be 3s for 2000 array:


(
	clearlistener()
	t = timestamp()

	posArr = for i = 1 to 2000 collect random [100,100,0] [100,100,200]
	distArr = #()
	sortedPosArr = #()
	pos0 = [-100,-100,0]

	posArr2 = for o in posArr collect o
	sortedPosArr = #(pos0)
	
	fn findShortestDa a shortestdist:99999999 c: = (
		for j = 1 to posArr2.count where (d = distance a posArr2[j]) < shortestdist do (shortestdist = d; c = j) 
		#(shortestdist, c)
	)
	
	for i = 1 to posArr.count do (
			a = ((findShortestDa sortedPosArr[(sortedPosArr.count)])[2])
			append sortedPosArr posArr2[a]
			deleteItem posArr2 a
		if posArr2.count == 0 do exit
	)
	
	deleteItem sortedPosArr 1
	
	totalTime = ((timestamp() - t)/1000)

	print sortedPosArr
	print sortedPosArr.count
	print totalTime
)

Hope it helps,
Pixamoon

barigazy · 2015-04-26

What about this? I use 10000 pos


fn compareFN v1 v2 =
(
	local d = v1.dist - v2.dist
	case of
	(
		(d < 0.): -1
		(d > 0.):  1
		default:   0
	)
)

_min = [-100,-100,0]
_max = [100,100,200]
data = #()
num = (data.count = 10000)
data = for i = 1 to num collect dataPair pos:(number = random _min _max) dist:(distance number _min)

gc() ; t1 = timestamp() ; m1 = heapfree
qsort data compareFN
format "time:% memory:%\n" ((timestamp()- t1 as float)/1000) (m1-heapfree)

-->time:0.384 memory:1504L

pixamoon · 2015-06-01

I think he ask for faster sorting by distance between points in array, not to one _min point.
but maybe not
But I've just learned dataPair from your comment! good to know, Thanks