Finds the index of the point which has the smallest Euclidean distance to 'p' and is {@code <} maxDistance
away.

@param p A point.
@param maxDistance The maximum distance (Euclidean squared) the neighbor can be.
@return Index of the closest point.
433655
public int findClosest( P p , double maxDistance ) {
		int best = -1;
		bestDistance = maxDistance;

		for( int i = 0; i < points.size(); i++ ) {
			P c = points.get(i);

			double distanceC = distance.distance(p,c);

			if( distanceC <= bestDistance ) {
				bestDistance = distanceC;
				best = i;
			}
		}

		return best;
	}
1291055
static int closestCorner4(Grid g ) {
		double bestDistance = g.get(0,0).center.normSq();
		int bestIdx = 0;

		double d = g.get(0,g.columns-1).center.normSq();
		if( d < bestDistance ) {
			bestDistance = d;
			bestIdx = 3;
		}
		d = g.get(g.rows-1,g.columns-1).center.normSq();
		if( d < bestDistance ) {
			bestDistance = d;
			bestIdx = 2;
		}
		d = g.get(g.rows-1,0).center.normSq();
		if( d < bestDistance ) {
			bestIdx = 1;
		}

		return bestIdx;
	}
536010
function(p, opt) {

        opt = opt || {};
        var precision = (opt.precision === undefined) ? this.PRECISION : opt.precision;
        var subdivisions = (opt.subdivisions === undefined) ? this.getSubdivisions({ precision: precision }) : opt.subdivisions;
        // does not use localOpt

        // identify the subdivision that contains the point:
        var investigatedSubdivision;
        var investigatedSubdivisionStartT; // assume that subdivisions are evenly spaced
        var investigatedSubdivisionEndT;
        var distFromStart; // distance of point from start of baseline
        var distFromEnd; // distance of point from end of baseline
        var chordLength; // distance between start and end of the subdivision
        var minSumDist; // lowest observed sum of the two distances
        var n = subdivisions.length;
        var subdivisionSize = (n ? (1 / n) : 0);
        for (var i = 0; i < n; i++) {

            var currentSubdivision = subdivisions[i];

            var startDist = currentSubdivision.start.distance(p);
            var endDist = currentSubdivision.end.distance(p);
            var sumDist = startDist + endDist;

            // check that the point is closest to current subdivision and not any other
            if (!minSumDist || (sumDist < minSumDist)) {
                investigatedSubdivision = currentSubdivision;

                investigatedSubdivisionStartT = i * subdivisionSize;
                investigatedSubdivisionEndT = (i + 1) * subdivisionSize;

                distFromStart = startDist;
                distFromEnd = endDist;

                chordLength = currentSubdivision.start.distance(currentSubdivision.end);

                minSumDist = sumDist;
            }
        }

        var precisionRatio = pow(10, -precision);

        // recursively divide investigated subdivision:
        // until distance between baselinePoint and closest path endpoint is within 10^(-precision)
        // then return the closest endpoint of that final subdivision
        while (true) {

            // check if we have reached at least one required observed precision
            // - calculated as: the difference in distances from point to start and end divided by the distance
            // - note that this function is not monotonic = it doesn't converge stably but has "teeth"
            // - the function decreases while one of the endpoints is fixed but "jumps" whenever we switch
            // - this criterion works well for points lying far away from the curve
            var startPrecisionRatio = (distFromStart ? (abs(distFromStart - distFromEnd) / distFromStart) : 0);
            var endPrecisionRatio = (distFromEnd ? (abs(distFromStart - distFromEnd) / distFromEnd) : 0);
            var hasRequiredPrecision = ((startPrecisionRatio < precisionRatio) || (endPrecisionRatio < precisionRatio));

            // check if we have reached at least one required minimal distance
            // - calculated as: the subdivision chord length multiplied by precisionRatio
            // - calculation is relative so it will work for arbitrarily large/small curves and their subdivisions
            // - this is a backup criterion that works well for points lying "almost at" the curve
            var hasMinimalStartDistance = (distFromStart ? (distFromStart < (chordLength * precisionRatio)) : true);
            var hasMinimalEndDistance = (distFromEnd ? (distFromEnd < (chordLength * precisionRatio)) : true);
            var hasMinimalDistance = (hasMinimalStartDistance || hasMinimalEndDistance);

            // do we stop now?
            if (hasRequiredPrecision || hasMinimalDistance) {
                return ((distFromStart <= distFromEnd) ? investigatedSubdivisionStartT : investigatedSubdivisionEndT);
            }

            // otherwise, set up for next iteration
            var divided = investigatedSubdivision.divide(0.5);
            subdivisionSize /= 2;

            var startDist1 = divided[0].start.distance(p);
            var endDist1 = divided[0].end.distance(p);
            var sumDist1 = startDist1 + endDist1;

            var startDist2 = divided[1].start.distance(p);
            var endDist2 = divided[1].end.distance(p);
            var sumDist2 = startDist2 + endDist2;

            if (sumDist1 <= sumDist2) {
                investigatedSubdivision = divided[0];

                investigatedSubdivisionEndT -= subdivisionSize; // subdivisionSize was already halved

                distFromStart = startDist1;
                distFromEnd = endDist1;

            } else {
                investigatedSubdivision = divided[1];

                investigatedSubdivisionStartT += subdivisionSize; // subdivisionSize was already halved

                distFromStart = startDist2;
                distFromEnd = endDist2;
            }
        }
    }
1038797
public static void limitDistance(DenseMatrix64F p0, DenseMatrix64F pr, double min, double max)
    {
        double x0 = p0.data[0];
        double y0 = p0.data[1];
        double xr = pr.data[0];
        double yr = pr.data[1];
        double dx = xr-x0;
        double dy = yr-y0;
        double r = Math.sqrt(dx*dx+dy*dy);
        if (r < min || r > max)
        {
            if (r < min)
            {
                r = min;
            }
            else
            {
                r = max;
            }
            double m = dy/dx;
            if (Double.isInfinite(m))
            {
                if (m > 0)
                {
                    pr.data[1] = y0 +  r;
                }
                else
                {
                    pr.data[1] = y0 -  r;
                }
            }
            else
            {
                double x = Math.sqrt((r*r)/(m*m+1));
                double y = m*x;
                pr.data[0] = x0 +  x;
                pr.data[1] = y0 +  y;
            }
        }
    }
594653
function (p) {
        var _min = this.min.array;
        var _max = this.max.array;

        var _p = p.array;

        return _min[0] <= _p[0] && _min[1] <= _p[1] && _min[2] <= _p[2]
            && _max[0] >= _p[0] && _max[1] >= _p[1] && _max[2] >= _p[2];
    }
1102428
public double getDistance(Coordinate coordinate) {
		double distance = Double.MAX_VALUE;
		if (!isEmpty()) {
			for (Polygon polygon : polygons) {
				double d = polygon.getDistance(coordinate);
				if (d < distance) {
					distance = d;
				}
			}
		}
		return distance;
	}
1063892
protected ApproximationLine progressiveKnnDistanceApproximation(int k_max) {
    if(!isLeaf()) {
      throw new UnsupportedOperationException("Progressive KNN-distance approximation " + "is only vailable in leaf nodes!");
    }

    // determine k_0, y_1, y_kmax
    int k_0 = 0;
    double y_1 = Double.POSITIVE_INFINITY;
    double y_kmax = Double.POSITIVE_INFINITY;

    for(int i = 0; i < getNumEntries(); i++) {
      MkCoPLeafEntry entry = (MkCoPLeafEntry) getEntry(i);
      ApproximationLine approx = entry.getProgressiveKnnDistanceApproximation();
      k_0 = Math.max(approx.getK_0(), k_0);
    }

    for(int i = 0; i < getNumEntries(); i++) {
      MkCoPLeafEntry entry = (MkCoPLeafEntry) getEntry(i);
      ApproximationLine approx = entry.getProgressiveKnnDistanceApproximation();
      y_1 = Math.min(approx.getValueAt(k_0), y_1);
      y_kmax = Math.min(approx.getValueAt(k_max), y_kmax);
    }

    // determine m and t
    double m = (y_kmax - y_1) / (FastMath.log(k_max) - FastMath.log(k_0));
    double t = y_1 - m * FastMath.log(k_0);

    return new ApproximationLine(k_0, m, t);
  }
282833
private static double findPrototype(DistanceQuery<?> dq, DBIDs cx, DBIDs cy, DBIDVar prototype, double minMaxDist) {
    for(DBIDIter i = cx.iter(); i.valid(); i.advance()) {
      // Maximum distance of i to all elements in cy
      double maxDist = findMax(dq, i, cy, 0., minMaxDist);
      if(maxDist >= minMaxDist) {
        // We already have an at least equally good candidate.
        continue;
      }
      // Maximum distance of i to all elements in cx
      maxDist = findMax(dq, i, cx, maxDist, minMaxDist);

      // New best solution?
      if(maxDist < minMaxDist) {
        minMaxDist = maxDist;
        prototype.set(i);
      }
    }
    return minMaxDist;
  }
624473
public double getDistance(Coordinate coordinate) {
		double distance = Double.MAX_VALUE;
		if (!isEmpty()) {
			for (LineString lineString : lineStrings) {
				double d = lineString.getDistance(coordinate);
				if (d < distance) {
					distance = d;
				}
			}
		}
		return distance;
	}
1192679
private void computeMaxDistance() {
        HashSet<Coordinate> coordinatesA = new HashSet<Coordinate>(Arrays.asList(geomA.convexHull().getCoordinates()));
        Geometry fullHull = geomA.getFactory().createGeometryCollection(new Geometry[]{geomA, geomB}).convexHull();
        maxDistanceFilter = new MaxDistanceFilter(coordinatesA);
        fullHull.apply(maxDistanceFilter);
    }
1247440
void findVertexNeighbors(Vertex target  , List<ChessboardCorner> corners ) {
//		if( target.index == 18 ) {
//			System.out.println("Vertex Neighbors "+target.index);
//		}

		ChessboardCorner targetCorner = corners.get(target.index);
		// distance is Euclidean squared
		double maxDist = Double.MAX_VALUE==maxNeighborDistance?maxNeighborDistance:maxNeighborDistance*maxNeighborDistance;
		nnSearch.findNearest(corners.get(target.index),maxDist,maxNeighbors,nnResults);

		// storage distances here to find median distance of closest neighbors
		distanceTmp.reset();

		for (int i = 0; i < nnResults.size; i++) {
			NnData<ChessboardCorner> r = nnResults.get(i);
			if( r.index == target.index) continue;

			distanceTmp.add( r.distance );

			double oriDiff = UtilAngle.distHalf( targetCorner.orientation , r.point.orientation );

			Edge edge = edges.grow();
			boolean parallel;
			if( oriDiff <= orientationTol) { // see if it's parallel
				parallel = true;
			} else if( Math.abs(oriDiff-Math.PI/2.0) <= orientationTol) { // see if it's perpendicular
				parallel = false;
			} else {
				edges.removeTail();
				continue;
			}

			// Use the relative angles of orientation and direction to prune more obviously bad matches
			double dx = r.point.x - targetCorner.x;
			double dy = r.point.y - targetCorner.y;

			edge.distance = Math.sqrt(r.distance);
			edge.dst = vertexes.get(r.index);
			edge.direction = Math.atan2(dy,dx);

			double direction180 = UtilAngle.boundHalf(edge.direction);
			double directionDiff = UtilAngle.distHalf(direction180,r.point.orientation);
			boolean remove;
			EdgeSet edgeSet;
			if( parallel ) {
				// test to see if direction and orientation are aligned or off by 90 degrees
				remove = directionDiff > 2* directionTol && Math.abs(directionDiff-Math.PI/2.0) > 2* directionTol;
				edgeSet = target.parallel;
			} else {
				// should be at 45 degree angle
				remove = Math.abs(directionDiff-Math.PI/4.0) > 2* directionTol;
				edgeSet = target.perpendicular;
			}

			if( remove ) {
				edges.removeTail();
				continue;
			}

			edgeSet.add(edge);
		}

		// Compute the distance of the closest neighbors. This is used later on to identify ambiguous corners.
		// If it's a graph corner there should be at least 3 right next to the node.
		if( distanceTmp.size == 0 ) {
			target.neighborDistance = 0;
		} else {
			sorter.sort(distanceTmp.data, distanceTmp.size);
			int idx = Math.min(3,distanceTmp.size-1);
			target.neighborDistance = Math.sqrt(distanceTmp.data[idx]); // NN distance is Euclidean squared
		}
	}
985392
static int maximumDistance(List<Point2D_I32> contour , int indexA , int indexB ) {
		Point2D_I32 a = contour.get(indexA);
		Point2D_I32 b = contour.get(indexB);

		int best = -1;
		double bestDistance = -Double.MAX_VALUE;

		for (int i = 0; i < contour.size(); i++) {
			Point2D_I32 c = contour.get(i);
			// can't sum sq distance because some skinny shapes it maximizes one and not the other
//			double d = Math.sqrt(distanceSq(a,c)) + Math.sqrt(distanceSq(b,c));
			double d = distanceAbs(a,c) + distanceAbs(b,c);
			if( d > bestDistance ) {
				bestDistance = d;
				best = i;
			}
		}

		return best;
	}
600863
static int computeRadius(final Dimension dimension, final Point start) {
        final int maxDistanceX = Math.max(start.x, dimension.width - start.x) + 1;
        final int maxDistanceY = Math.max(start.y, dimension.height - start.y) + 1;
        
        // we use the pythagorean theorem to determinate the maximum radius
        return (int) Math.ceil(Math.sqrt(maxDistanceX * maxDistanceX + maxDistanceY * maxDistanceY));
    }
1042859
protected int findBestMatch(double[] p) {
		int bestCluster = -1;
		bestDistance = Double.MAX_VALUE;

		for (int j = 0; j < clusters.size; j++) {
			double d = distanceSq(p,clusters.get(j));
			if( d < bestDistance ) {
				bestDistance = d;
				bestCluster = j;
			}
		}
		return bestCluster;
	}
1278222
public static double pointRectDistance (IRectangle r, IPoint p) {
        return Math.sqrt(pointRectDistanceSq(r, p));
    }
1061259
int subSimplify(PointList points, int fromIndex, int lastIndex) {
        if (lastIndex - fromIndex < 2) {
            return 0;
        }
        int indexWithMaxDist = -1;
        double maxDist = -1;
        double firstLat = points.getLatitude(fromIndex);
        double firstLon = points.getLongitude(fromIndex);
        double lastLat = points.getLatitude(lastIndex);
        double lastLon = points.getLongitude(lastIndex);
        for (int i = fromIndex + 1; i < lastIndex; i++) {
            double lat = points.getLatitude(i);
            if (Double.isNaN(lat)) {
                continue;
            }
            double lon = points.getLongitude(i);
            double dist = calc.calcNormalizedEdgeDistance(lat, lon, firstLat, firstLon, lastLat, lastLon);
            if (maxDist < dist) {
                indexWithMaxDist = i;
                maxDist = dist;
            }
        }

        if (indexWithMaxDist < 0) {
            throw new IllegalStateException("maximum not found in [" + fromIndex + "," + lastIndex + "]");
        }

        int counter = 0;
        if (maxDist < normedMaxDist) {
            for (int i = fromIndex + 1; i < lastIndex; i++) {
                points.set(i, Double.NaN, Double.NaN, Double.NaN);
                counter++;
            }
        } else {
            counter = subSimplify(points, fromIndex, indexWithMaxDist);
            counter += subSimplify(points, indexWithMaxDist, lastIndex);
        }
        return counter;
    }
1351087
function findClosestPointIndexWithinRadius(points, x, y, radiusThreshold) {
    let closestIdx;
    let closestDist = Number.MAX_VALUE;
    points.forEach((d, idx) => {
      let distSqrd = Math.pow(d.x - x, 2) + Math.pow(d.y - y, 2); // changeto: (d.x - x)**2 + (d.y - y)**2;
      if (distSqrd < closestDist && distSqrd < radiusThreshold) {
        closestIdx = idx;
        closestDist = distSqrd;
      }
    });
    return closestIdx;
  }