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

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

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

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: 9916
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

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

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: 1691
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

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

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: 9916
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

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

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.8960705228pseudo 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           13841optimized distance 343279.4116236997 1.352633499987817 seconds `
deltarho[1859]
Posts: 2608
Joined: Jan 02, 2017 0:34
Location: UK

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

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 SingleEnd Type #macro Sqrt4(a)  Asm    movups xmm0, a    sqrtps xmm0,xmm0    movups a, xmm0  End ASm#endmacro Dim As Single4 a a.first = 123.456a.second = 234.567a.third = 345.678a.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: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

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

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: 1691
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

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

@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: 331
Joined: Dec 02, 2011 22:51
Location: France

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

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: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

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

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.

### Who is online

Users browsing this forum: No registered users and 3 guests