Nuestro grupo especializado despúes de días de investigación y de recopilar de datos, obtuvieron los datos necesarios, nuestro deseo es que resulte de gran utilidad para tu plan.
Ejemplo: cómo encontrar la distancia más cercana para puntos dados
# A divide and conquer program in Python3 # to find the smallest distance from a # given set of points. import math
import copy
# A class to represent a Point in 2D plane classPoint():def__init__(self, x, y):
self.x = x
self.y = y
# A utility function to find the # distance between two points defdist(p1, p2):return math.sqrt((p1.x - p2.x)*(p1.x - p2.x)+(p1.y - p2.y)*(p1.y - p2.y))# A Brute Force method to return the # smallest distance between two points # in P[] of size n defbruteForce(P, n):
min_val =float('inf')for i inrange(n):for j inrange(i +1, n):if dist(P[i], P[j])< min_val:
min_val = dist(P[i], P[j])return min_val
# A utility function to find the # distance beween the closest points of # strip of given size. All points in # strip[] are sorted accordint to # y coordinate. They all have an upper # bound on minimum distance as d. # Note that this method seems to be # a O(n^2) method, but it's a O(n) # method as the inner loop runs at most 6 times defstripClosest(strip, size, d):# Initialize the minimum distance as d
min_val = d
# Pick all points one by one and # try the next points till the difference # between y coordinates is smaller than d. # This is a proven fact that this loop # runs at most 6 times for i inrange(size):
j = i +1while j < size and(strip[j].y -
strip[i].y)< min_val:
min_val = dist(strip[i], strip[j])
j +=1return min_val
# A recursive function to find the # smallest distance. The array P contains # all points sorted according to x coordinate defclosestUtil(P, Q, n):# If there are 2 or 3 points, # then use brute force if n <=3:return bruteForce(P, n)# Find the middle point
mid = n //2
midPoint = P[mid]# Consider the vertical line passing # through the middle point calculate # the smallest distance dl on left # of middle point and dr on right side
dl = closestUtil(P[:mid], Q, mid)
dr = closestUtil(P[mid:], Q, n - mid)# Find the smaller of two distances
d =min(dl, dr)# Build an array strip[] that contains # points close (closer than d) # to the line passing through the middle point
strip =[]for i inrange(n):ifabs(Q[i].x - midPoint.x)< d:
strip.append(Q[i])# Find the closest points in strip. # Return the minimum of d and closest # distance is strip[] returnmin(d, stripClosest(strip,len(strip), d))# The main function that finds # the smallest distance. # This method mainly uses closestUtil() defclosest(P, n):
P.sort(key =lambda point: point.x)
Q = copy.deepcopy(P)
Q.sort(key =lambda point: point.y)# Use recursive function closestUtil() # to find the smallest distance return closestUtil(P, Q, n)# Driver code
P =[Point(2,3), Point(12,30),
Point(40,50), Point(5,1),
Point(12,10), Point(3,4)]
n =len(P)print("The smallest distance is",
closest(P, n))# This code is contributed # by Prateek Gupta (@prateekgupta10)
Si haces scroll puedes encontrar las ilustraciones de otros administradores, tú además puedes insertar el tuyo si te apetece.
¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)