Use K-means++ to choose the initial centers.

@param points the points to choose the initial centers from
@return the initial centers
979504
function chooseInitialCenters(points) {

    // Convert to list for indexed access. Make it unmodifiable, since removal of items
    // would screw up the logic of this method.
    var pointList = points;
    // The number of points in the list.
    var numPoints = pointList.length;

    // Set the corresponding element in this array to indicate when
    // elements of pointList are no longer available.
    var taken = new Array(numPoints);
    for (var i = 0; i < taken.length; i++) {
      taken[i] = false;
    }

    // The resulting list of initial centers.
    var resultSet = [];

    // Choose one center uniformly at random from among the data points.
    var firstPointIndex = nextInt(numPoints);
    var firstPoint = pointList[firstPointIndex];
    resultSet.push(new CentroidCluster(firstPoint));
    // Must mark it as taken
    taken[firstPointIndex] = true;

    // To keep track of the minimum distance squared of elements of
    // pointList to elements of resultSet.

    var minDistSquared = new Float32Array(numPoints);

    // Initialize the elements.  Since the only point in resultSet is firstPoint,
    // this is very easy.
    for (var i = 0; i < numPoints; i++) {
      if (i !== firstPointIndex) { // That point isn't considered
        var d = distance(firstPoint, pointList[i]);
        minDistSquared[i] = d * d;
      }
    }

    while (resultSet.length < k) {
      // Sum up the squared distances for the points in pointList not
      // already taken.
      var distSqSum = 0.0;

      for (var i = 0; i < numPoints; i++) {
        if (!taken[i]) {
          distSqSum += minDistSquared[i];
        }
      }

      // Add one new data point as a center. Each point x is chosen with
      // probability proportional to D(x)2
      var r = nextDouble() * distSqSum;

      // The index of the next point to be added to the resultSet.
      var nextPointIndex = -1;

      // Sum through the squared min distances again, stopping when
      // sum >= r.
      var sum = 0.0;
      for (var i = 0; i < numPoints; i++) {
        if (!taken[i]) {
          sum += minDistSquared[i];
          if (sum >= r) {
            nextPointIndex = i;
            break;
          }
        }
      }

      // If it's not set to >= 0, the point wasn't found in the previous
      // for loop, probably because distances are extremely small.  Just pick
      // the last available point.
      if (nextPointIndex === -1) {
        for (var i = numPoints - 1; i >= 0; i--) {
          if (!taken[i]) {
            nextPointIndex = i;
            break;
          }
        }
      }

      // We found one.
      if (nextPointIndex >= 0) {

        var p = pointList[nextPointIndex];

        resultSet.push(new CentroidCluster(p));

        // Mark it as taken.
        taken[nextPointIndex] = true;

        if (resultSet.length < k) {
          // Now update elements of minDistSquared.  We only have to compute
          // the distance to the new center to do this.
          for (var j = 0; j < numPoints; j++) {
            // Only have to worry about the points still not taken.
            if (!taken[j]) {
              var d = distance(p, pointList[j]);
              var d2 = d * d;
              if (d2 < minDistSquared[j]) {
                minDistSquared[j] = d2;
              }
            }
          }
        }

      } else {
        // None found --
        // Break from the while loop to prevent
        // an infinite loop.
        break;
      }
    }
    return resultSet;
  }
528808
public static double getMeanSlope( List<ProfilePoint> points ) {
        double meanSlope = 0;

        int num = 0;
        for( int i = 0; i < points.size() - 1; i++ ) {
            ProfilePoint p1 = points.get(i);
            ProfilePoint p2 = points.get(i + 1);

            double dx = p2.progressive - p1.progressive;
            double dy = p2.elevation - p1.elevation;
            double tmpSlope = dy / dx;
            meanSlope = meanSlope + tmpSlope;
            num++;
        }
        meanSlope = meanSlope / num;
        return meanSlope;
    }
899396
static List<Point2D> grahamScan(final List<Point2D> points) {

        if (points.size() <= 3) return new ArrayList<Point2D>(points);

        Collections.sort(points, new CompareYThenX());
        Collections.sort(points, new PolarComparator(points.get(0)));

        Deque<Point2D> hull = new ArrayDeque<Point2D>();

        hull.push(points.get(0));
        hull.push(points.get(1));
        hull.push(points.get(2));

        for (int i = 3; i < points.size(); i++) {
            Point2D top = hull.pop();
            while (!hull.isEmpty() && !isLeftTurn(hull.peek(), top, points.get(i))) {
                top = hull.pop();
            }
            hull.push(top);
            hull.push(points.get(i));
        }

        return new ArrayList<Point2D>(hull);
    }
879691
function(points) {

                var centerPoints = {},
                    key = null;

                for (var i = 0, j = 0, len = points.length; i < len; i++) {

                    //j是下一个点的索引
                    j = i === (len - 1) ? 0 : i + 1;

                    key = i + ',' + j;

                    //计算中点坐标
                    centerPoints[key] = {
                        x: (points[i].x + points[j].y) / 2,
                        y: (points[i].x + points[j].y) / 2
                    };


                }

                return centerPoints;

            }
578709
public static  Atom centerOfMass(Atom[] points) {
		Atom center = new AtomImpl();

		float totalMass = 0.0f;
		for (Atom a : points) {
			float mass = a.getElement().getAtomicMass();
			totalMass += mass;
			center = scaleAdd(mass, a, center);
		}

		center = scaleEquals(center, 1.0f/totalMass);
		return center;
	}
26740
public static int numPoints(Clustering<? extends MeanModel> clustering) {
    int n = 0;
    for(Cluster<? extends MeanModel> aCluster : clustering.getAllClusters()) {
      n += aCluster.size();
    }
    return n;
  }
560025
public static GeoPoint calculateCenter(List<GeoPoint> geoPoints) {
        checkNotNull(geoPoints, "geoPoints cannot be null");
        checkArgument(geoPoints.size() > 0, "must have at least 1 geoPoints");
        if (geoPoints.size() == 1) {
            return geoPoints.get(0);
        }

        double x = 0.0;
        double y = 0.0;
        double z = 0.0;
        double totalAlt = 0.0;
        int altitudeCount = 0;
        for (GeoPoint geoPoint : geoPoints) {
            double latRad = Math.toRadians(geoPoint.getLatitude());
            double lonRad = Math.toRadians(geoPoint.getLongitude());
            x += Math.cos(latRad) * Math.cos(lonRad);
            y += Math.cos(latRad) * Math.sin(lonRad);
            z += Math.sin(latRad);

            if (geoPoint.getAltitude() != null) {
                totalAlt += geoPoint.getAltitude();
                altitudeCount++;
            }
        }

        x = x / (double) geoPoints.size();
        y = y / (double) geoPoints.size();
        z = z / (double) geoPoints.size();

        return new GeoPoint(
            Math.toDegrees(Math.atan2(z, Math.sqrt(x * x + y * y))),
            Math.toDegrees(Math.atan2(y, x)),
            altitudeCount == geoPoints.size() ? (totalAlt / (double) altitudeCount) : null
        );
    }
400198
private Coordinate[] getCenterPoints( double[][][] houghValues, int maxCircles ) {

        Coordinate[] centerPoints = new Coordinate[maxCircles];
        int xMax = 0;
        int yMax = 0;
        int rMax = 0;

        for( int c = 0; c < maxCircles; c++ ) {
            double counterMax = -1;
            for( int radius = radiusMin; radius <= radiusMax; radius = radius + radiusInc ) {

                int indexR = (radius - radiusMin) / radiusInc;
                for( int y = 0; y < height; y++ ) {
                    for( int x = 0; x < width; x++ ) {
                        if (houghValues[x][y][indexR] > counterMax) {
                            counterMax = houghValues[x][y][indexR];
                            xMax = x;
                            yMax = y;
                            rMax = radius;
                        }
                    }

                }
            }

            centerPoints[c] = new Coordinate(xMax, yMax, rMax);

            clearNeighbours(houghValues, xMax, yMax, rMax);
        }
        return centerPoints;
    }
1217432
public static ArrayList<IGeoPoint> pointsAsRect(GeoPoint center, double lengthInMeters, double widthInMeters){
		ArrayList<IGeoPoint> points = new ArrayList<IGeoPoint>(4);
		GeoPoint east = center.destinationPoint(lengthInMeters*0.5, 90.0f);
		GeoPoint south = center.destinationPoint(widthInMeters*0.5, 180.0f);
		double westLon = center.getLongitude()*2 - east.getLongitude();
		double northLat = center.getLatitude()*2 - south.getLatitude();
		points.add(new GeoPoint(south.getLatitude(), east.getLongitude()));
		points.add(new GeoPoint(south.getLatitude(), westLon));
		points.add(new GeoPoint(northLat, westLon));
		points.add(new GeoPoint(northLat, east.getLongitude()));
		return points;
	}
594658
public Coordinate[] getCoordinates() {
		if (isEmpty()) {
			return null;
		}
		Coordinate[] coordinates = new Coordinate[points.length];
		for (int i = 0; i < points.length; i++) {
			coordinates[i] = points[i].getCoordinate();
		}
		return coordinates;
	}
1343327
function cluster(points) {
    // number of clusters has to be smaller or equal the number of data points
    if (points.length < k) {
      throw 'Too many clusters';
    }

    // create the initial clusters
    var clusters = chooseInitialCenters(points);

    // create an array containing the latest assignment of a point to a cluster
    // no need to initialize the array, as it will be filled with the first assignment
    var assignments = new Int32Array(points.length);
    assignPointsToClusters(clusters, points, assignments);
    // iterate through updating the centers until we're done
    var max = (maxIterations < 0) ? Number.MAX_VALUE : maxIterations;
    for (var count = 0; count < max; count++) {
      var emptyCluster = false;
      var newClusters = [];
      for (var clusterIndex = 0; clusterIndex < clusters.length; clusterIndex++) {
        var cluster = clusters[clusterIndex];
        var newCenter;
        if (cluster.getPoints().length === 0) {
          newCenter = getPointFromLargestVarianceCluster(clusters);
          emptyCluster = true;
        } else {
          newCenter = centroidOf(cluster.getPoints(), cluster.getCenter().getPoint().size());
        }
        newClusters.push(new CentroidCluster(newCenter));
      }
      var changes = assignPointsToClusters(newClusters, points, assignments);
      clusters = newClusters;

      // if there were no more changes in the point-to-cluster assignment
      // and there are no empty clusters left, return the current clusters
      if (changes === 0 && !emptyCluster) {
        return clusters;
      }
    }
    return clusters;
  }
32763
public static Point getCorner (Point center, Point size)
    {
        return new Point(center.x - size.x/2, center.y - size.y/2);
    }
1177195
public static MultiPoint of(Stream<Point> points) {
        return of(points.collect(Collectors.toList()));
    }
688509
public static LabeledPoint pointOf(Collection<Writable> writables) {
        double[] ret = new double[writables.size() - 1];
        int count = 0;
        double target = 0;
        for (Writable w : writables) {
            if (count < writables.size() - 1)
                ret[count++] = Float.parseFloat(w.toString());
            else
                target = Float.parseFloat(w.toString());
        }

        if (target < 0)
            throw new IllegalStateException("Target must be >= 0");
        return new LabeledPoint(target, Vectors.dense(ret));
    }
449730
public PolygonOrientation getOrientation(List<LatLng> points) {
        return SphericalUtil.computeSignedArea(points) >= 0 ? PolygonOrientation.COUNTERCLOCKWISE : PolygonOrientation.CLOCKWISE;
    }
1127742
public double targetFunctionValue(int k, int n, Point[] centres, Point[] points){
		int i=0;
		double sum = 0.0;
		for(i=0;i<n;i++){
			double nearestCost = -1.0;
			int j=0;
			for(j=0;j<k;j++){
				double distance = 0.0;
				int l = 0;
				for(l=0;l<points[i].dimension;l++){
					//Centroid coordinate of the point
					double centroidCoordinatePoint;
					if(points[i].weight != 0.0){
						centroidCoordinatePoint = points[i].coordinates[l] / points[i].weight;
					} else {
						centroidCoordinatePoint = points[i].coordinates[l];
					}
					//Centroid coordinate of the centre
					double centroidCoordinateCentre;
					if(centres[j].weight != 0.0){
						centroidCoordinateCentre = centres[j].coordinates[l] / centres[j].weight;
					} else {
						centroidCoordinateCentre = centres[j].coordinates[l];
					}
					distance += (centroidCoordinatePoint-centroidCoordinateCentre) * 
							(centroidCoordinatePoint-centroidCoordinateCentre) ;

				}
				if(nearestCost <0 || distance < nearestCost) {
					nearestCost = distance;
				} 
			}
			sum += nearestCost * points[i].weight;
		}
		return sum;
	}
857455
protected void createSamplePoints(int numSamples) {
		for( int y = 0; y < numSamples; y++ ) {
			float regionY = (y/(numSamples-1.0f) - 0.5f);

			for( int x = 0; x < numSamples; x++  ) {
				float regionX = (x/(numSamples-1.0f) - 0.5f);
				samplePts.add( new Point2D_F32(regionX,regionY));
			}
		}
	}