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

Published on 12 May 2024 09:40 PM
#Autohotkey

How to resolve the algorithm Closest-pair problem step by step in the AutoHotkey 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 AutoHotkey programming language

Source code in the autohotkey programming language

ClosestPair(points){
	if (points.count() <= 3)
		return bruteForceClosestPair(points)
	split := xSplit(Points)
	LP := split.1			; left points
	LD := ClosestPair(LP)		; recursion : left closest pair
	RP := split.2			; right points
	RD := ClosestPair(RP)		; recursion : right closest pair
	minD := min(LD, RD)		; minimum of LD & RD
	xmin := Split.3 - minD		; strip left boundary
	xmax := Split.3 + minD		; strip right boundary
	S := strip(points, xmin, xmax)
	if (s.count()>=2)
	{
		SD := ClosestPair(S)	; recursion : strip closest pair
		return min(SD, minD)
	}
	return minD
}
;---------------------------------------------------------------
strip(points, xmin, xmax){
	strip:=[]
	for i, coord in points
		if (coord.1 >= xmin) && (coord.1 <= xmax)
			strip.push([coord.1, coord.2])
	return strip
}
;---------------------------------------------------------------
bruteForceClosestPair(points){
	minD := []
	loop, % points.count()-1{
		p1 := points.RemoveAt(1)
		loop, % points.count(){
			p2 := points[A_Index]
			d := dist(p1, p2)
			minD.push(d)
		}
	}
	return min(minD*)
}
;---------------------------------------------------------------
dist(p1, p2){
	return Sqrt((p2.1-p1.1)**2 + (p2.2-p1.2)**2)
}
;---------------------------------------------------------------
xSplit(Points){
	xL := [], xR := []
	p := xSort(Points)
	Loop % Ceil(p.count()/2)
		xL.push(p.RemoveAt(1))
	while p.count()
		xR.push(p.RemoveAt(1))
	mid := (xL[xl.count(),1] + xR[1,1])/2
	return [xL, xR, mid]
}
;---------------------------------------------------------------
xSort(Points){
	S := [], Res :=[]
	for i, coord in points
		S[coord.1, coord.2] := true
	for x, coord in S
		for y, v in coord
			res.push([x, y])
	return res
}
;---------------------------------------------------------------


points := [[1, 1], [12, 30], [40, 50], [5, 1], [12, 10], [3, 4], [17,25], [45,50],[51,34],[2,1],[2,2],[10,10]]
MsgBox % ClosestPair(points)

You may also check:How to resolve the algorithm Loops/Foreach step by step in the Ruby programming language
You may also check:How to resolve the algorithm Matrix transposition step by step in the GAP programming language
You may also check:How to resolve the algorithm RCRPG step by step in the Ruby programming language
You may also check:How to resolve the algorithm Copy stdin to stdout step by step in the Ruby programming language
You may also check:How to resolve the algorithm Sorting algorithms/Shell sort step by step in the Ruby programming language