Fastest way to do point search?

The forum is locked. These are the original blitzbasic.com forums, kept so they can still be read. No new topics, replies or edits can be made here. To join in, head over to the Blitz3D+ forums.

fredborg

You can also do a Bounding box + Squared distance search. It's the lower one of these two:

Open in online IDE

Type point
	Field x#,y#,z#
End Type

width#	= 100.0
height# = 100.0
depth#	= 100.0

For i = 0 To 4999
	point.point = New point
	point\x	= Rnd(width)
	point\y = Rnd(height)
	point\z = Rnd(depth)
Next

camx# = 50
camy# = 50
camz# = 50

ms = MilliSecs()
For loop = 1 To 1000
	d0# = 100000000.0
	np.point = Null
	For point.point = Each point
		dx# = point\x - camx
		dy# = point\y - camy
		dz# = point\z - camz
		d# = dx*dx + dy*dy + dz*dz
		If d<d0
			d0 = d
			np = point
		End If
	Next
Next
Print "Squared search : "+(MilliSecs()-ms)
Print "Nearest point : "+Str(np)
Print

ms = MilliSecs()
For loop = 1 To 1000
	d0# = 100000000.0
	np.point = Null
	For point.point = Each point
		d# = (point\x - camx) * (point\x - camx)
		If d<d0
			d# = d + ((point\y - camy) * (point\y - camy))
			If d<d0
				d# = d + ((point\z - camz) * (point\z - camz))
				If d<d0
					d0 = d
					np = point
				End If
			End If
		End If
	Next
Next
Print "Bound + Squared search : "+(MilliSecs()-ms)
Print "Nearest point : "+Str(np)
Print

WaitKey()
End

That seems to be at least marginally faster than doing a squared distance search. To get it much faster than that you will probably need to build a search tree :)

[edit] Ohh, I didn't really read your post :) So this one only finds the nearest point.