How would you find the shortest distance in a set of points?

General FreeBASIC programming questions.
jj2007
Posts: 1645
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: How would you find the shortest distance in a set of points?

Postby jj2007 » Jun 29, 2020 19:41

fxm wrote:X1 = 1, X2 = 6
SUMi(Xi^2) = 37
SUMi(SQR(Xi^2)) = 7

X1 = 3, X2 = 5
SUMi(Xi^2) = 34
SUMi(SQR(Xi^2)) = 8

Between these two examples, SUMi(Xi^2) decreases while SUMi(SQR(Xi^2)) increases.
Sorry, I can't follow you. What exactly is SUMi?
fxm
Posts: 9833
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: How would you find the shortest distance in a set of points?

Postby fxm » Jun 29, 2020 19:55

fxm wrote:@dodicat,

Let SUMi(Yi) = Y1 + Y2 + Y3 + .....

We can not compare:
SUMi(Xi^2) = X1^2 + X2^2 + .....
with:
SUMi(SQR(Xi^2)) = SQR(X1^2) + SQR(X2^2) + .....
because the SQR function induces a non-linearity in the sum.

Examples (with a sum of 2 terms) where that fails:

X1 = 1, X2 = 6
SUMi(Xi^2) = 1^2 + 6^2 = 37
SUMi(SQR(Xi^2)) = 1 + 6 = 7

X1 = 3, X2 = 5
SUMi(Xi^2) = 3^2 + 5^2 = 34
SUMi(SQR(Xi^2)) = 3 + 5 = 8

Between these two examples, SUMi(Xi^2) decreases while SUMi(SQR(Xi^2)) increases.

This is what the dodicat's code does (viewtopic.php?p=273613#p273613).
jj2007
Posts: 1645
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: How would you find the shortest distance in a set of points?

Postby jj2007 » Jun 29, 2020 20:28

Thanks, that is much clearer now. Are you sure that dodicat's code sums up the elements (wrongly) as SQR(X1^2) + SQR(X2^2)?

Code: Select all

#define rawlength(a,b) ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
To me, it looks like the correct Pythagoras: A²+B²=C² or rather dx²+dy²=dist²
fxm
Posts: 9833
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: How would you find the shortest distance in a set of points?

Postby fxm » Jun 29, 2020 20:41

I'm talking about this line of code:
if f=0 then total+=sqr(L) else total+=L
in the function 'distance(points() As pt,f as long=0) As double'.

He then compares (in viewtopic.php?p=273613#p273613) the results ('total') obtained with f=0 or f=1:

Code: Select all

original distance  353607.8960705228
pseudo dist   array dist
 1e+020
 157149997     358751.941673827            1
 156502903     355714.6772599964           3
 150981928     348062.2103850992           6
 149868626     345199.2785204384           34
 148818352     347659.1081542731           184
 148261510     343807.2098599597           400
 146532917     340238.0074669157           572
 146378242     342773.662772364            2215
 146264168     342588.527484985            6106
 146006296     343279.4116236997           13841

optimized distance 343279.4116236997

 1.352633499987817 seconds
 
deltarho[1859]
Posts: 2583
Joined: Jan 02, 2017 0:34
Location: UK

Re: How would you find the shortest distance in a set of points?

Postby deltarho[1859] » Jun 29, 2020 21:35

I am a bit pushed for time at the moment but this may be useful. It simply calculates the square root of four singles in parallel and is faster than the FPU with one single. The asm is by Paul Dixon at the PowerBASIC forum in a thread discussing a very different topic.

On my machine 100,000 Sqrt4() comes in at just less than half a millisecond.

Code: Select all

'#Console On
 
Type Single4
  first AS Single
  second AS Single
  third AS Single
  fourth AS Single
End Type
 
#macro Sqrt4(a)
  Asm
    movups xmm0, a
    sqrtps xmm0,xmm0
    movups a, xmm0
  End ASm
#endmacro
 
Dim As Single4 a
 
a.first = 123.456
a.second = 234.567
a.third = 345.678
a.fourth = 456.789
 
Sqrt4(a)
 
Print a.first, a.second, a.third, a.fourth
 
Sleep
Last edited by deltarho[1859] on Jun 29, 2020 21:51, edited 1 time in total.
dodicat
Posts: 6648
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How would you find the shortest distance in a set of points?

Postby dodicat » Jun 29, 2020 21:48

Thanks fxm.
Just because a sum of squared distances through points might be greater than another sum of squared distances doesn't mean that the actual distance is also greater.
So the squared distances can be used for comparisons with each other, and have no direct associations with actual distances.
So they shouldn't be mixed.
Yea, that's it fxm, your simple example shows this.
Thanks again.
jj2007
Posts: 1645
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: How would you find the shortest distance in a set of points?

Postby jj2007 » Jun 29, 2020 22:54

@dodicat: I've tried to understand your code, and especially why you sum up the "total distance". You are not doing two loops as shown below, how will you identify the two closest points?

Below pts() is the array of points. It's Assembly but I hope it's understandable. The instructions mov and mrm assign values to the first operand; mul eax is like x=eax*eax

Code: Select all

  For_ ecx=0 To points-1   ; setup
   mov pts(ecx, x), Rand(GuiWidth)   ; assign random
   mov pts(ecx, y), Rand(GuiHeight)   ; x+y values
  Next
  mov minDist, 9999   ; start with a high value to trigger the comparisons
  For_ ct=0 To points-1   ; outer loop
   mrm px, pts(ct, x)   ; get x and y of
   mrm py, pts(ct, y)   ; the current point
   mov ecx, ct   ; take the index of the current point...
   .Repeat
      inc ecx   ; ... and compare to all following points
      mov eax, pts(ecx, x)   ; get x of inner loop point
      sub eax, px   ; subtract x of outer loop point
      mul eax   ; square it: dx^2
      push eax   ; save dx^2
      mov eax, pts(ecx, y)   ; get y of inner loop point
      sub eax, py   ; subtract y of outer loop point
      mul eax   ; square it: dy^2
      pop edx   ; get dx^2 back
      add eax, edx   ; dx^2+dy^2 to eax
      .if eax<minDist
         mov pointB, ecx   ; remember the index of the inner loop point
         m2m pointA, ct      ; remember the index of the outer loop point
         mov minDist, eax   ; and the distance, of course
      .endif
   .Until ecx>=points   ; end of inner loop
  Next
Lost Zergling
Posts: 326
Joined: Dec 02, 2011 22:51
Location: France

Re: How would you find the shortest distance in a set of points?

Postby Lost Zergling » Jun 29, 2020 23:18

I just try to thought a little around this problematic, not seeking for solutions around the web. I tried to think about ideas but,... Not around mathematics, just logic. Am I wrong or this problem may be far more complex than what it could looks like at first sight ?
dodicat
Posts: 6648
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How would you find the shortest distance in a set of points?

Postby dodicat » Jun 29, 2020 23:55

jj2007
My distance function simply returns the total distance through the array.
I must use total the sqr(L) of course and not the L, for reasons discussed (fxm).

My own (mov minDist, 9999) is actually 1e20 to start,and the minimum is found in the 1 to 20000 loop.
I don't need two loops for this.
As soon as a new minimum (distance, not squared distance) is found the array configuration is saved in the opt() array.
To get the (distance, not squared distance), the distance function is called with
distance(p(),0). (I have it distance(p(),1) in the code which is in error because it yields the squared distance with the flag 1.
A rule of thumb I will remember is that If I find the smallest squared or Manhattan distance then I will have found the smallest squared or Manhattan distance, and not the smallest distance, it is elementary really, but I got a bit caught out.
The whole thing comes under the travelling salesman problem which has a non analytic brute force solution.

The second piece of code (to get the two closest points) is a bit easier, just use bubble sort loops (two) to bring every array point to every other array point just once and measure the squared distance each time and get a minimum yielding the two array indices of the closest two when the loops are completed
I think your asm code does this.

Return to “General”

Who is online

Users browsing this forum: Google [Bot] and 3 guests