Python Program to Implement Distance Calculation System Assignment Solution

Instructions

Objective

Write a program to implement distance calculation system in python.

Requirements and Specifications

Source Code

# CS4102 Spring 2022 - Unit A Programming

#################################

# Collaboration Policy: You are encouraged to collaborate with up to 3 other tudents, but all work submitted must be your own independently written solution. List the computing ids of all of your collaborators in the comments at the top of each submitted file. Do not share written notes, documents (including Google docs, Overleaf docs, discussion notes, PDFs), or code. Do not seek published or online solutions, including pseudocode, for this assignment. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite them. Do not submit a solution that you are unable to explain orally to a member of the course staff. Any solutions that share similar text/code will be considered in breach of this policy. Please refer to the syllabus for complete description of the collaboration policy.

#################################

# Your Computing ID: tzc2wh

# Collaborators: tef2nv, maw3rge, tjs9rrr

# Sources: Introduction to Algorithms, Cormen

#################################

import math import copy class Point: def __init__(self, x, y): self.x = x self.y = y def __str__(self): return f"({self.x},{self.y})" class ClosestPair: def __init__(self): return # This is the method that should set off the computation # of closest pair. It takes as input a list containing lines of input # as strings. You should parse that input and then call a # subroutine that you write to compute the closest pair distances # and return those values from this method # # @return the distances between the closest pair and second closest pair # with closest at position 0 and second at position 1 def compute(self, file_data): secondClosest = 0.1 # Parse all the data so we convert them from string to list of integers P = map(lambda s: Point(float(s.split()[0]), float(s.split()[1])), file_data) P = list(P) P.sort(key = lambda point: point.x) Q = copy.deepcopy(P) Q.sort(key = lambda point: point.y) n = len(P) #return [closest, secondClosest] self.distances =set() closest = self.closest(P, Q, n) self.distances = sorted(self.distances) secondClosest = self.distances[1] return [closest, secondClosest] def distance(self, p1: Point, p2: Point): """ Calculate the euclidean distance between two points :param p1: Point :param p2: Point :return: double """ return math.sqrt((p1.x - p2.x)**2 + (p1.y - p2.y)**2) def brute(self, points): """ Given a list of points, return the smallest distance between the closest two pair of points This method is used only for small amount of points :param points: List of Point object :return: tuple """ n = len(points) distances = [] # Compute all distances and add to the 'distances' list for i in range(n): for j in range(i+1, n): p1 = points[i] p2 = points[j] dist = self.distance(p1, p2) self.distances.add(dist) distances.append(dist) # Sort in ascending order distances = sorted(distances) # Return the first self.distances.add(distances[0]) return distances[0] def strip(self, points, n, d): """ This function receives a list of points and a maximum distance value 'd' :param points: List of points :param d: Maximum distance :return: double """ min_dist = d for i in range(n): j = i+1 while j < n and (points[j].y - points[i].y) < min_dist: min_dist = self.distance(points[i], points[j]) j += 1 self.distances.add(min_dist) return min_dist def closest(self, P, Q, n): if n <= 3: return self.brute(P) # Find middle mid = n//2 pmid = P[mid] # Split into left and right sides from mid Pl = P[:mid] Pr = P[mid:] # Now, get the smallest distances for left and right sides dl = self.closest(Pl, Q, mid) dr = self.closest(Pr, Q, n - mid) self.distances.add(dl) self.distances.add(dr) # Pick the smallest distance d = min(dl, dr) # Insert into two arrays the points closer than d to the middle point stripP = list() stripQ = list() lr = Pl + Pr for i in range(n): if abs(lr[i].x - pmid.x) < d: stripP.append(lr[i]) if abs(Q[i].x - pmid.x) < d: stripQ.append(Q[i]) # Sort in ascending by y coordinate stripP.sort(key = lambda point: point.y) min_a = min(d, self.strip(stripP, len(stripP), d)) min_b = min(d, self.strip(stripQ, len(stripQ), d)) self.distances.add(min_a) self.distances.add(min_b) # Return return min(min_a, min_b)