so as said in the tittle, how would you find the shortest distance in a set of points, in a fast way.

So far here is my try:

Code: Select all

`type POINT2D`

as single x

as single y

end type

dim as POINT2D xy(1 to 1000)

'set up 1000 points

randomize TIMER()

for index as integer = lBound(XY) to uBound(XY)

xy(index).x = 50 + 500*rnd()

xy(index).y = 50 + 500*rnd()

next index

#macro _dist(xy1, xy2)

sqr(((xy1.x) - (xy2.x))*((xy1.x) - (xy2.x)) + ((xy1.y) - (xy2.y))*((xy1.y) - (xy2.y)))

#endMacro

screenRes 600,600,32

dim as single dist

dim as single minDistanceSofar = 1e+9

for index as integer = lBound(XY) to uBound(XY) - 1

line (xy(index).x, xy(index).y)-(xy(index + 1).x, xy(index + 1).y), rgb(100,200,200)

if (xy(index + 1).x - xy(index).x)>minDistanceSofar then

continue for

end if

if (xy(index + 1).y - xy(index).y)>minDistanceSofar then

continue for

end if

'

dist = _dist(xy(index + 1), xy(index))

if dist<minDistanceSofar then

minDistanceSofar = dist

end if

next index

? "min distance found = ", minDistanceSofar

getKey()

Any other idea?

edit: Hum, yes there is something weird, missing a loop or something in the above example. Every couple of points should be tested, not only adjacent ones in index order of course.