Sorting position array by shortest distance

Submitted by Tweekazoid on Thu, 2015-04-09 00:57

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

‹ Duplicate a box to different sizes using table data. Please help. Need to get the z pos of vertex ›

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
pixamoon's picture
Submitted by pixamoon on Tue, 2015-04-14 22:50.

`

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's picture
Submitted by pixamoon on Wed, 2015-04-15 03:25.

`

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's picture
Submitted by barigazy on Sun, 2015-04-26 13:15.

...

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

bga

pixamoon's picture
Submitted by pixamoon on Mon, 2015-06-01 16:14.

`

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

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.