solution_054.py

#!/usr/bin/python3
# ==================================================================
# find two points that have the smallest distance between them
# (only the first minimum distance (points) found will be displayed)
# ==================================================================
#
# A thought - modify the program:
# keep an array of two point combinations and distance between
# them. sort the array and find the two points that have the second,
# third, forth, fifth, ... smallest between distance.
#
# ===================================================================
# Note:
# a. in this algorithm the points do not need to be sorted
# b. the distance from p1 to p2 is the same as p2 to p1
# ===================================================================

import sys
import numpy as np

# ---- test points list - no duplicates points allowed
# ---- points = []
# ---- points = [ (1,1), (4,5) ]

points = [ (1,1), (3,3), (4,2), (2,4), (0,0) ]


# -------------------------------------------------------------------
# ---- calculate distance between two points
# -------------------------------------------------------------------

def distance(p1,p2):
    dx = p1[0] - p2[0]
    dy = p1[1] - p2[1]
    d = np.sqrt(dx*dx + dy*dy)
    return d


# -------------------------------------------------------------------
# ---- minimum distance between any two points
# -------------------------------------------------------------------

def minimum_distance(pts):

    results = []

    pl = len(pts)              # points list length

    if pl < 2:
        return results

    for idx1 in range(pl-1):

        for idx2 in range(idx1+1,pl):

            print(f'({idx1},{idx2}) ',end='')

            p1 = pts[idx1]
            p2 = pts[idx2]
            d = distance(p1,p2)

            ##print('------------------------------')
            ##print(f'idx1 = {idx1}  p=({p1})')
            ##print(f'idx2 = {idx2}  p=({p2})')
            ##print(f'dist = {d:.3}')

            if idx1 == 0 and idx2 == 1:    # first time
                results = (p1,p2,d)
            else:                          # next time
                if d < results[2]:
                    results = (p1,p2,d)
        print()
        
    return results


# -------------------------------------------------------------------
# ----main ----------------------------------------------------------
# -------------------------------------------------------------------

if __name__ == '__main__':

    results = minimum_distance(points)

    if results == []:
        print()
        print('not enougn points')
        sys.exit()

    print()
    print('---- results ------------------')
    print(f'p1   = {results[0]}')
    print(f'p2   = {results[1]}')
    print(f'dist = {results[2]:.3}')
    print()