How to resolve the algorithm Closest-pair problem step by step in the Pascal programming language

Published on 12 May 2024 09:40 PM
#Pascal

How to resolve the algorithm Closest-pair problem step by step in the Pascal programming language

Table of Contents

Problem Statement

Provide a function to find the closest two points among a set of given points in two dimensions,   i.e. to solve the   Closest pair of points problem   in the   planar   case. The straightforward solution is a   O(n2)   algorithm   (which we can call brute-force algorithm);   the pseudo-code (using indexes) could be simply: A better algorithm is based on the recursive divide&conquer approach,   as explained also at   Wikipedia's Closest pair of points problem,   which is   O(n log n);   a pseudo-code could be:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Closest-pair problem step by step in the Pascal programming language

Source code in the pascal programming language

program closestPoints;
{$IFDEF FPC}
   {$MODE Delphi}
{$ENDIF}
const
  PointCnt = 10000;//31623;
type
  TdblPoint = Record
               ptX,
               ptY : double;
              end;
  tPtLst =  array of TdblPoint;

  tMinDIstIdx  = record
                   md1,
                   md2 : NativeInt;
                 end;

function ClosPointBruteForce(var  ptl :tPtLst):tMinDIstIdx;
Var
  i,j,k : NativeInt;
  mindst2,dst2: double; //square of distance, no need to sqrt
  p0,p1 : ^TdblPoint;   //using pointer, since calc of ptl[?] takes much time
Begin
  i := Low(ptl);
  j := High(ptl);
  result.md1 := i;result.md2 := j;
  mindst2 := sqr(ptl[i].ptX-ptl[j].ptX)+sqr(ptl[i].ptY-ptl[j].ptY);
  repeat
    p0 := @ptl[i];
    p1 := p0; inc(p1);
    For k := i+1 to j do
    Begin
      dst2:= sqr(p0^.ptX-p1^.ptX)+sqr(p0^.ptY-p1^.ptY);
      IF mindst2 > dst2  then
      Begin
        mindst2 :=  dst2;
        result.md1 := i;
        result.md2 := k;
      end;
      inc(p1);
    end;
    inc(i);
  until i = j;
end;

var
  PointLst :tPtLst;
  cloPt : tMinDIstIdx;
  i : NativeInt;
Begin
  randomize;
  setlength(PointLst,PointCnt);
  For i := 0 to PointCnt-1 do
    with PointLst[i] do
    Begin
      ptX := random;
      ptY := random;
    end;
  cloPt:=  ClosPointBruteForce(PointLst) ;
  i := cloPt.md1;
  Writeln('P[',i:4,']= x: ',PointLst[i].ptX:0:8,
                     ' y: ',PointLst[i].ptY:0:8);
  i := cloPt.md2;
  Writeln('P[',i:4,']= x: ',PointLst[i].ptX:0:8,
                     ' y: ',PointLst[i].ptY:0:8);
end.

You may also check:How to resolve the algorithm Align columns step by step in the ZX Spectrum Basic programming language
You may also check:How to resolve the algorithm Shoelace formula for polygonal area step by step in the Ada programming language
You may also check:How to resolve the algorithm Zero to the zero power step by step in the Maple programming language
You may also check:How to resolve the algorithm Subtractive generator step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Read a file line by line step by step in the jq programming language