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

jj2007

  • Moderator
  • Member
  • *****
  • Posts: 10447
  • Assembler is fun ;-)
    • MasmBasic
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
               add eax, 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: 10447
  • Assembler is fun ;-)
    • MasmBasic
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