Closest pair of points

    :param S: list of points
    :requires: size of S at least 2
    :modifies: changes the order in S
    :returns: pair of points p,q from S with minimum Euclidean distance
    :complexity: expected linear time
482986
def closest_points(S):
    
    shuffle(S)
    assert len(S) >= 2
    p = S[0]
    q = S[1]
    d = dist(p, q)
    while d > 0:
        r = improve(S, d)
        if r:
            d, p, q = r
        else:
            break
    return p, q
969158
def distance(p1, p2):
    

    def xyz(some_pose):
        if isinstance(some_pose, PoseStamped):
            return some_pose.pose.position.x, some_pose.pose.position.y, some_pose.pose.position.z
        elif isinstance(some_pose, Pose):
            return some_pose.position.x, some_pose.position.y, some_pose.position.z
        elif _is_indexable(some_pose[0]):
            return some_pose[0][0], some_pose[0][1], some_pose[0][2]
        else:
            return some_pose[0], some_pose[1], some_pose[2]

    x1, y1, z1 = xyz(p1)
    x2, y2, z2 = xyz(p2)

    x = x1 - x2
    y = y1 - y2
    z = z1 - z2
    return sqrt(x * x + y * y + z * z)
554230
def hamming_distance(s1, s2):
    
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length")
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
822167
def pairwise_point_combinations(xs, ys, anchors):
    
    for i in xs:
        anchors.append((i, max(ys)))
        anchors.append((i, min(ys)))
    for i in ys:
        anchors.append((max(xs), i))
        anchors.append((min(xs), i))
300641
def _closest_location(self, location_map, target):
        """"""

        def dist(a, b):
            return math.sqrt(sum((a[k] - b[k]) ** 2 for k in a.keys()))

        paths = iter(location_map.keys())
        closest = next(paths)
        closest_dist = dist(target, location_map[closest])
        for path in paths:
            cur_dist = dist(target, location_map[path])
            if cur_dist < closest_dist:
                closest = path
                closest_dist = cur_dist
        return closest
39478
public ClusteringTreeNode nearestChild(double[] pointA) {
		assert (this.center.length == pointA.length);
		double minDistance = Double.POSITIVE_INFINITY;
		ClusteringTreeNode min = null;
		for (ClusteringTreeNode node : this.getChildren()) {
			double d = Metric.distance(pointA, node.getCenter());
			if (d < minDistance) {
				minDistance = d;
				min = node;
			}
		}
		return min;
	}
1191890
def _find_closest(self, n0):
        
        dmin = np.inf
        nclose = None

        ds = []
        nodes = []

        ds.append(np.inf)
        nodes.append(self)

        for n in self:
            if n is n0:
                continue
            try:
                if n._in_same_observation(n0):
                    continue
                ds.append(n.distance(n0))
                nodes.append(n)
            except AttributeError:
                pass

        inds = np.argsort(ds)
        ds = [ds[i] for i in inds]
        nodes = [nodes[i] for i in inds]

        for d,n in zip(ds, nodes):
            try:
                if d < n.resolution or n.resolution==-1:
                    return n
            except AttributeError:
                pass

        # If nothing else works
        return self
800857
function closestPoint0d(a, x, result) {
  var d = 0.0;
  for(var i=0; i<x.length; ++i) {
    result[i] = a[i];
    var t = a[i] - x[i];
    d += t * t;
  }
  return d;
}
207420
def pairwise_euclid_distance(A, B):
    
    batchA = tf.shape(A)[0]
    batchB = tf.shape(B)[0]

    sqr_norm_A = tf.reshape(tf.reduce_sum(tf.pow(A, 2), 1), [1, batchA])
    sqr_norm_B = tf.reshape(tf.reduce_sum(tf.pow(B, 2), 1), [batchB, 1])
    inner_prod = tf.matmul(B, A, transpose_b=True)

    tile_1 = tf.tile(sqr_norm_A, [batchB, 1])
    tile_2 = tf.tile(sqr_norm_B, [1, batchA])
    return (tile_1 + tile_2 - 2 * inner_prod)
1105164
def nearest_point(x, y, pts, mode='random'):
    
    dists = (pts.T[0] - x) ** 2 + (pts.T[1] - y) ** 2
    fx = dists.argmin()
    mindist = dists[fx]
    other_fx = np.where(mindist == dists)[0]
    if len(other_fx) > 0:
        if mode == 'random':
            np.random.shuffle(other_fx)
            fx = other_fx[0]
        if mode == 'all':
            fx = other_fx
        if mode == 'first':
            fx = fx
    return fx, mindist
866471
function closestPoint1d(a, b, x, result) {
  var denom = 0.0;
  var numer = 0.0;
  for(var i=0; i<x.length; ++i) {
    var ai = a[i];
    var bi = b[i];
    var xi = x[i];
    var dd = ai - bi;
    numer += dd * (xi - bi);
    denom += dd * dd;
  }
  var t = 0.0;
  if(Math.abs(denom) > EPSILON) {
    t = numer / denom;
    if(t < 0.0) {
      t = 0.0;
    } else if(t > 1.0) {
      t = 1.0;
    }
  }  
  var ti = 1.0 - t;
  var d = 0;
  for(var i=0; i<x.length; ++i) {
    var r = t * a[i] + ti * b[i];
    result[i] = r;
    var s = x[i] - r;
    d += s * s;
  }
  return d;
}
591020
int closestPoint( Point2D_F64 target ) {
		double bestDistance = Double.MAX_VALUE;
		int bestIndex = -1;
		for (int i = 0; i < contour.size(); i++) {
			Point2D_I32 c = contour.get(i);

			double d = UtilPoint2D_F64.distanceSq(target.x,target.y,c.x,c.y);
			if( d < bestDistance ) {
				bestDistance = d;
				bestIndex = i;
			}
		}
		return bestIndex;
	}
721015
def _jit_pairwise_distances(pos1, pos2):
        
        n1 = pos1.shape[0]
        n2 = pos2.shape[0]
        D = np.empty((n1, n2))

        for i in range(n1):
            for j in range(n2):
                D[i, j] = np.sqrt(((pos1[i] - pos2[j])**2).sum())
        return D
144769
def _one_contains_other(s1, s2):
    
    return min(len(s1), len(s2)) == len(s1 & s2)
720294
def distance2_to(self, other: "Point2"):
        """"""
        assert isinstance(other, Point2)
        return (self[0] - other[0]) ** 2 + (self[1] - other[1]) ** 2
637884
def faster_minimum_distance2(hull_a, center_a, hull_b, center_b):
    '''
    
    '''
    #
    # Find the farthest vertex in b from some point within A. Find the
    # vertices within A visible from this point in B. If the point in A
    # is within B or the farthest vertex in B is within A, then the objects
    # intersect.
    #
    if within_hull(center_a, hull_b):
        return 0
    farthest_b = find_farthest(center_a, hull_b)
    if within_hull(hull_b[farthest_b,:], hull_a):
        return 0
    visible_b = find_visible(hull_b, center_a, farthest_b)
    #
    # Do the same for B
    if within_hull(center_b, hull_a):
        return 0
    farthest_a = find_farthest(center_b, hull_a)
    if within_hull(hull_a[farthest_a,:], hull_b):
        return 0
    visible_a = find_visible(hull_a, center_b, farthest_a)
    #
    # Now go from the first in A and last in B measuring distances
    # which should decrease as we move toward the best
    #
    i = visible_a[0]
    i_next = (i+1) % hull_a.shape[0]
    j = visible_b[1]
    j_next = (j+hull_b.shape[0]-1) % hull_b.shape[0]
    a = hull_a[i,:]
    a_next = hull_a[i_next,:]
    b = hull_b[j,:]
    b_next = hull_b[j_next,:]
    d2_min = np.sum((a-b)**2)
    
    while i != visible_a[1] and j != visible_b[0]:
        if lines_intersect(a, a_next, b, b_next):
            return 0
        if (np.dot(b-b_next,a-b_next) > 0 and
            np.dot(b_next-b,a-b) > 0):
            # do the edge if better than the vertex
            d2a = distance2_to_line(b, a, a_next)
        else:
            # try the next vertex of a
            d2a = np.sum((a_next-b)**2)
        if (np.dot(a-a_next,b-a_next) > 0 and
            np.dot(a_next-a,b-a) > 0):
            d2b = distance2_to_line(a, b, b_next)
        else:
            d2b = np.sum((b_next-a)**2)
        if d2a < d2_min and d2a < d2b:
            # The edge of A is closer than the best or the b-edge
            # Take it and advance A
            d2_min = d2a
            a = a_next
            i = i_next
            i_next = (i+1) % hull_a.shape[0]
            a_next = hull_a[i_next,:]
        elif d2b < d2_min:
            # B is better. Take it and advance
            d2_min = d2b
            b = b_next
            j = j_next
            j_next = (j+hull_b.shape[0]-1) % hull_b.shape[0]
            b_next = hull_b[j_next,:]
        else:
            return d2_min
    #
    # Some more to do... either one more i or one more j
    #
    while i != visible_a[1]:
        d2_min = min(d2_min, np.sum((a_next-b)**2))
        a = a_next
        i = i_next
        i_next = (i+1) % hull_a.shape[0]
        a_next = hull_a[i_next,:]
        
    while j != visible_b[0]:
        d2_min = min(d2_min, np.sum((b_next-a)**2))
        b = b_next
        j = j_next
        j_next = (j+ hull_b.shape[0]-1) % hull_b.shape[0]
        b_next = hull_b[j_next,:]
    return d2_min
11969
def epsilon_net(points, close_distance):
  ''''''
  num_points = points.shape[0]
  indices = set(range(num_points))
  selected = []
  while indices:
    idx = indices.pop()
    nn_inds, = nearest_neighbors(points[idx], points, epsilon=close_distance)
    indices.difference_update(nn_inds)
    selected.append(idx)
  return selected