Re: lingo-l Finding the closest point from a list of points in lingo
A little slow out of the blocks but maybe useful to someone anyway: For lists up to a certain size, doing the arithmetic using whole lists instead of individual elements is faster. On my machine, the first method is _way_ faster on lists with 500 or fewer items, and roughly 10% faster on lists of 1 items. global gPointList on makelist howMany gPointList =[] repeat with x = 1 to howMany gPointList.add(point(random(100),random(100))) end repeat end on test kount = gPointList.count -- The list of known points thePoint = point(10,10) -- the point in question ms = the milliseconds testlist = [] repeat with x = 1 to kount testList.add(thePoint) end repeat outlist = gPointList - testList now = the milliseconds put now - ms ms = the milliseconds testlist = [] repeat with x = 1 to kount outlist.add(gPointList[x] - thePoint) end repeat now = the milliseconds put now - ms end - Carl [To remove yourself from this list, or to change to digest mode, go to http://www.penworks.com/lingo-l.cgi To post messages to the list, email lingo-l@penworks.com (Problems, email [EMAIL PROTECTED]). Lingo-L is for learning and helping with programming Lingo. Thanks!]
lingo-l Finding the closest point from a list of points in lingo
Hi Guys, I'm hoping someone can help me out with a quick pointer, I've got a tight deadline and my minds gone a bit blank. I have a list of points [point(112,456), point(12,485), ...] list goes to about 50 These are actually co-ordinates of certain pixels on my stage. I need to find the closest one (radius) to any given point - i.e. the mouseLoc - it needs to be fairly efficient as I will need to do it every frame \ couple of frames. Can someone point me in the right direction please. Many thanks Tim [To remove yourself from this list, or to change to digest mode, go to http://www.penworks.com/lingo-l.cgi To post messages to the list, email lingo-l@penworks.com (Problems, email [EMAIL PROTECTED]). Lingo-L is for learning and helping with programming Lingo. Thanks!]
Re: lingo-l Finding the closest point from a list of points in lingo
Hi Tim, Just off the top of my head this might get you started (email lingo, watch for typos) on getNearestPoint aListOfPoints, aRefPoint d = the maxInteger tWhichPoint = 0 repeat with i in aListOfPoints a = aRefPoint[1] - i[1] b = aRefPoint[2] - i [2] c = a*a + b*b if c d then tWhichPoint = aListOfPoints.getOne(i) end if end repeat return tWhichPoint end hth, Rob On Tue, 11 Apr 2006 19:26:13 +0100, Tim Welford [EMAIL PROTECTED] wrote: I need to find the closest one (radius) to any given point - i.e. the mouseLoc - it needs to be fairly efficient as I will need to do it every frame \ couple of frames. Can someone point me in the right direction please. [To remove yourself from this list, or to change to digest mode, go to http://www.penworks.com/lingo-l.cgi To post messages to the list, email lingo-l@penworks.com (Problems, email [EMAIL PROTECTED]). Lingo-L is for learning and helping with programming Lingo. Thanks!]
Re: lingo-l Finding the closest point from a list of points in lingo
on getNearestPoint aListOfPoints, aRefPoint ... end depending on the exact characteristics of your project, you might be able to speed up the process of finding the minimal distance (as proposed by rob) by using vectors (with z=0) instead of points, and their distanceto method. but this means you first have to convert your poibnts to vectors, so it doesn't make sense if all of the points change all the time. here a simple speed comparison: on test p1 = point(1,2) p2 = point(6,10) put points: ms = the milliseconds repeat with i = 1 to 5 dq = (p1[1]-p2[1])*(p1[1]-p2[1]) + (p1[2]-p2[2])*(p1[2]-p2[2]) end repeat put the milliseconds-ms v1 = vector(1,2,0) v2 = vector(6,10,0) put vectors: ms = the milliseconds repeat with i = 1 to 5 d = v1.distanceto(v2) end repeat put the milliseconds-ms end result: -- points: -- 86 -- vectors: -- 30 valentin [To remove yourself from this list, or to change to digest mode, go to http://www.penworks.com/lingo-l.cgi To post messages to the list, email lingo-l@penworks.com (Problems, email [EMAIL PROTECTED]). Lingo-L is for learning and helping with programming Lingo. Thanks!]
RE: lingo-l Finding the closest point from a list of points in lingo
Just had a bet in the pub I can get the previous script shorter:))) It's using vector maths (not sure how quick it is but it's shorter code) on getNearest pList,pCenter pStartVector = vector(pCenter[1],pCenter[2],0) pCount = pList.count if pCount 0 then pNearest = 0 repeat with y = 1 to pCount pVector = vector(pList[y][1],pList[y][2],0) pDistance = pVector.distanceTo(pStartVector) if pDistance pNearest then pNearest = y end if end repeat return pNearest end if End Damn mobile phone...let me know if it works...beer is at stake:) [To remove yourself from this list, or to change to digest mode, go to http://www.penworks.com/lingo-l.cgi To post messages to the list, email lingo-l@penworks.com (Problems, email [EMAIL PROTECTED]). Lingo-L is for learning and helping with programming Lingo. Thanks!]
Re: lingo-l Finding the closest point from a list of points in lingo
On Tue, 11 Apr 2006 21:41:33 +0200, Valentin Schmidt [EMAIL PROTECTED] wrote: but this means you first have to convert your poibnts to vectors, so it doesn't make sense if all of the points change all the time. Hey, I took Valentin's code and threw in the point to vector conversion just to see what kind of time that gave but I also changed his long equation for the distance to a shorter one by storing a and b instead of calculating them twice. The results are: -- points long equation: -- 83 -- points using variables: -- 58 -- vectors: -- 30 -- pts to vectors: -- 116 on test p1 = point(1,2) p2 = point(6,10) put points long equation: ms = the milliseconds repeat with i = 1 to 5 dq = (p1[1]-p2[1])*(p1[1]-p2[1]) + (p1[2]-p2[2])*(p1[2]-p2[2]) end repeat put the milliseconds-ms p1 = point(1,2) p2 = point(6,10) put points using variables: ms = the milliseconds repeat with i = 1 to 5 a = p1[1]-p2[1] b = p1[2]-p2[2] dq = a*a + b*b end repeat put the milliseconds-ms v1 = vector(1,2,0) v2 = vector(6,10,0) put vectors: ms = the milliseconds repeat with i = 1 to 5 d = v1.distanceto(v2) end repeat put the milliseconds-ms put pts to vectors: ms = the milliseconds repeat with i = 1 to 5 v1 = vector(p1[1], p1[2], 0) v2 = vector(p2[1], p2[2], 0) d = v1.distanceto(v2) end repeat put the milliseconds-ms end [To remove yourself from this list, or to change to digest mode, go to http://www.penworks.com/lingo-l.cgi To post messages to the list, email lingo-l@penworks.com (Problems, email [EMAIL PROTECTED]). Lingo-L is for learning and helping with programming Lingo. Thanks!]
RE: lingo-l Finding the closest point from a list of points in lingo
Quoting Pedja [EMAIL PROTECTED]: Just had a bet in the pub I can get the previous script shorter:))) It's using vector maths (not sure how quick it is but it's shorter code) on getNearest pList,pCenter pStartVector = vector(pCenter[1],pCenter[2],0) pCount = pList.count -- if pCount 0 then pNearest = 0 repeat with y = 1 to pCount pVector = vector(pList[y][1],pList[y][2],0) pTemp = pVector.distanceTo(pStartVector) if pTemp pDistance then pNearest = y pDistance = pTemp end if end repeat return pNearest --end if End or on getNearest pList,pCenter pStartVector = vector(pCenter[1],pCenter[2],0) pDistance = 999 repeat with y in pList pVector = vector(y[1],y[2],0) pTemp = pVector.distanceTo(pStartVector) if pTemp pDistance then pNearest = pVector pDistance = pTemp end if end repeat return pNearest End - Ken [To remove yourself from this list, or to change to digest mode, go to http://www.penworks.com/lingo-l.cgi To post messages to the list, email lingo-l@penworks.com (Problems, email [EMAIL PROTECTED]). Lingo-L is for learning and helping with programming Lingo. Thanks!]
