ejemplo de código python del par de puntos más cercano

Este grupo de trabajo ha pasado mucho tiempo investigando la solución a tus dudas, te regalamos la resolución así que deseamos servirte de mucha ayuda.

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)

Te mostramos comentarios y puntuaciones

Si entiendes que ha sido útil nuestro artículo, nos gustaría que lo compartas con otros entusiastas de la programación de esta forma contrubuyes a difundir este contenido.

---

---

Utiliza Nuestro Buscador