Author Topic: Shortest distance between points  (Read 534 times)

jj2007

• Moderator
• Member
• Posts: 11046
• Assembler is fun ;-)
Shortest distance between points
« on: June 29, 2020, 11:44:53 AM »
Find the two points that are closest to each other - source & exe attached.

GuiParas equ "Shortest distance between points", x0, w1366, h740, b Black      ; position, size, background
include \masm32\MasmBasic\Res\MbGui.asm
points=800                    ; 3ms (8,000: 330ms)
SetGlobals px, py, minDist, pointA, pointB, hNull
mov hNull, rv(GetStockObject, NULL_BRUSH)
MakePath MyCircle, Circle(9)
MakePen hPen1, RgbCol(255, 255, 255, 255)
MakePen hPen2, RgbCol(96, 255, 255, 0), width 9      ; yellow, half transparent
Dim pts() As POINT
Event Key
GuiCls                                ; hit any key to generate a new set of points
Event Paint
call MakePoints
For_ ct=0 To points-1
m2m px, pts(ct, x)
m2m py, pts(ct, y)
mov edx, ct
If_ edx==pointA || edx==pointB Then GuiDraw MyCircle, hPen2, px, py, 8000
GuiDraw MyCircle, hPen1, px, py
Next
GuiTextBox 99.9-100, 99.9-48, 96, 44, Cat\$(Str\$("A=%i", pts(pointA, x))+Str\$(":%i", pts(pointA, y))+CrLf\$+Str\$("B=%i", pts(pointB, x))+Str\$(":%i\n", pts(pointB, y))), bcol Yellow, font -14
EndOfEvents
MakePoints:
mov minDist, 9999
For_ ecx=0 To points-1
mov pts(ecx, x), Rand(GuiWidth)
mov pts(ecx, y), Rand(GuiHeight)
Next
For_ ct=0 To points-1
m2m px, pts(ct, x)
m2m py, pts(ct, y)
For_ ecx=0 To points-1
mov eax, pts(ecx, x)
sub eax, px
mul eax
push eax
mov eax, pts(ecx, y)
sub eax, py
mul eax
pop edx
.if eax<minDist
.if ct!=ecx
mov pointB, ecx         ; remember this point
m2m pointA, ct          ; remember the other one, too
mov minDist, eax        ; and the distance, of course
.endif
.endif
Next
Next
ret
GuiEnd

jj2007

• Moderator
• Member
• Posts: 11046
• Assembler is fun ;-)
Re: Shortest distance between points
« Reply #1 on: June 29, 2020, 11:15:40 PM »
New version, optimised for speed (2ms for 1,000 points):
Code: [Select]
`  For_ ct=0 To points-1 mrm px, pts(ct, x) mrm py, pts(ct, y) mov ecx, ct .Repeat inc ecx mov eax, pts(ecx, x) sub eax, px mul eax push eax mov eax, pts(ecx, y) sub eax, py mul eax pop edx add eax, edx .if eax<minDist && ct!=ecx mov pointB, ecx ; remember this point m2m pointA, ct ; remember the other one, too mov minDist, eax ; and the distance, of course .endif .Until ecx>=points  Next ; there is a retn 0 before the events`