This function generates a voronoi centroid point
    list from arrays of latitude and longitude
329271
def _get_voronoi_centroid_array(lsm_lat_array, lsm_lon_array, extent):
    
    YMin = extent[2]
    YMax = extent[3]
    XMin = extent[0]
    XMax = extent[1]

    ptList = []
    if (lsm_lat_array.ndim == 2) and (lsm_lon_array.ndim == 2):
        # generate point list with 2D lat lon lists
        if extent:
            # exctract subset within extent
            lsm_dx = np.max(np.absolute(np.diff(lsm_lon_array)))
            lsm_dy = np.max(np.absolute(np.diff(lsm_lat_array, axis=0)))

            # remove values with NaN
            lsm_lat_array = np.ma.filled(lsm_lat_array, fill_value=-9999)
            lsm_lon_array = np.ma.filled(lsm_lon_array, fill_value=-9999)

            lsm_lat_indices_from_lat, lsm_lon_indices_from_lat = \
                np.where((lsm_lat_array >= (YMin - 2*lsm_dy)) &
                         (lsm_lat_array <= (YMax + 2*lsm_dy)))
            lsm_lat_indices_from_lon, lsm_lon_indices_from_lon = \
                np.where((lsm_lon_array >= (XMin - 2*lsm_dx)) &
                         (lsm_lon_array <= (XMax + 2*lsm_dx)))

            lsm_lat_indices = np.intersect1d(lsm_lat_indices_from_lat,
                                             lsm_lat_indices_from_lon)
            lsm_lon_indices = np.intersect1d(lsm_lon_indices_from_lat,
                                             lsm_lon_indices_from_lon)

            lsm_lat_list = \
                lsm_lat_array[lsm_lat_indices, :][:, lsm_lon_indices]
            lsm_lon_list = \
                lsm_lon_array[lsm_lat_indices, :][:, lsm_lon_indices]
        # Create a list of geographic coordinate pairs
        for i in range(len(lsm_lat_indices)):
            for j in range(len(lsm_lon_indices)):
                ptList.append([lsm_lon_list[i][j], lsm_lat_list[i][j]])

    elif lsm_lat_array.ndim == 1 and lsm_lon_array.ndim == 1:
        # generate point list with 1D lat lon lists
        if extent:
            Ybuffer = 2 * abs(lsm_lat_array[0]-lsm_lat_array[1])
            Xbuffer = 2 * abs(lsm_lon_array[0]-lsm_lon_array[1])
            # Extract the lat and lon within buffered extent
            # (buffer with 2* interval degree)
            lsm_lat_list = lsm_lat_array[(lsm_lat_array >= (YMin - Ybuffer)) &
                                         (lsm_lat_array <= (YMax + Ybuffer))]
            lsm_lon_list = lsm_lon_array[(lsm_lon_array >= (XMin - Xbuffer)) &
                                         (lsm_lon_array <= (XMax + Xbuffer))]

        # Create a list of geographic coordinate pairs
        for ptX in lsm_lon_list:
            for ptY in lsm_lat_list:
                ptList.append([ptX, ptY])
    else:
        raise IndexError("Lat/Lon lists have invalid dimensions. "
                         "Only 1D or 2D arrays allowed ...")

    if len(ptList) <= 0:
        raise IndexError("The watershed is outside of the bounds of the"
                         " land surface model grid ...")

    return np.array(ptList)
158804
function pointsArray (buf, offset, numPoints) {
    var pointsData = []
    for (var i = offset; i < offset + numPoints * 12; i += 12) {
      pointsData.push([buf.readFloatLE(i + 0), buf.readFloatLE(i + 4), buf.readFloatLE(i + 8)])
    }
    return pointsData
  }
1015909
def _interval_to_bound_points(array):
    

    array_boundaries = np.array([x.left for x in array])
    array_boundaries = np.concatenate(
        (array_boundaries, np.array([array[-1].right])))

    return array_boundaries
382158
def _new_centroid(x, n, cumn)
      c = Centroid.new(x, n, cumn)
      @centroids[x] = c
      c
    end
230124
function generateArcPath (x, y, radius, startAngle, endAngle) {
  var start = polarToCartesian(x, y, radius, startAngle);
  var end = polarToCartesian(x, y, radius, endAngle);
  var arcSweep = endAngle - startAngle <= 180 ? '0' : '1';
  return [
    'M', start.x, start.y,
    'A', radius, radius, 0, arcSweep, 0, end.x, end.y
  ].join(' ');
}
821190
def centroid(X):
    
    C = np.sum(X, axis=0) / len(X)
    return C
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;
}
1182466
List<Integer> convexhull(List<Float> pts) {
        int npts = pts.size() / 3;
        List<Integer> out = new ArrayList<>();
        // Find lower-leftmost point.
        int hull = 0;
        for (int i = 1; i < npts; ++i) {
            float[] a = new float[] { pts.get(i * 3), pts.get(i * 3 + 1), pts.get(i * 3 + 2) };
            float[] b = new float[] { pts.get(hull * 3), pts.get(hull * 3 + 1), pts.get(hull * 3 + 2) };
            if (cmppt(a, b)) {
                hull = i;
            }
        }
        // Gift wrap hull.
        int endpt = 0;
        do {
            out.add(hull);
            endpt = 0;
            for (int j = 1; j < npts; ++j) {
                float[] a = new float[] { pts.get(hull * 3), pts.get(hull * 3 + 1), pts.get(hull * 3 + 2) };
                float[] b = new float[] { pts.get(endpt * 3), pts.get(endpt * 3 + 1), pts.get(endpt * 3 + 2) };
                float[] c = new float[] { pts.get(j * 3), pts.get(j * 3 + 1), pts.get(j * 3 + 2) };
                if (hull == endpt || left(a, b, c)) {
                    endpt = j;
                }
            }
            hull = endpt;
        } while (endpt != out.get(0));

        return out;
    }
1228288
def pointsToVoronoiGridShapefile(lat, lon, vor_shp_path, extent=None):
    
    voronoi_centroids = _get_voronoi_centroid_array(lat, lon, extent)

    # set-up output polygon shp
    log("Creating output polygon shp {0}"
        .format(os.path.basename(vor_shp_path)))
    if os.path.exists(vor_shp_path):
        os.remove(vor_shp_path)
    drv = ogr.GetDriverByName('ESRI Shapefile')
    outShp = drv.CreateDataSource(vor_shp_path)
    osr_geographic_proj = osr.SpatialReference()
    osr_geographic_proj.ImportFromEPSG(4326)
    layer = outShp.CreateLayer('', osr_geographic_proj, ogr.wkbPolygon)
    layer.CreateField(ogr.FieldDefn('GRID_LAT', ogr.OFTReal))
    layer.CreateField(ogr.FieldDefn('GRID_LON', ogr.OFTReal))
    layerDefn = layer.GetLayerDefn()

    # find nodes surrounding polygon centroid
    # sort nodes in counterclockwise order
    # create polygon perimeter through nodes
    log("Building Voronoi polygons...")
    # compute voronoi
    voronoi_manager = Voronoi(voronoi_centroids)
    voronoi_vertices = voronoi_manager.vertices
    voronoi_regions = voronoi_manager.regions
    for point_id, region_index in enumerate(voronoi_manager.point_region):
        vert_index_list = np.array(voronoi_regions[region_index])
        voronoi_centroid = voronoi_centroids[point_id]
        voronoi_poly_points = _get_voronoi_poly_points(vert_index_list,
                                                       voronoi_vertices,
                                                       voronoi_centroid)
        if len(voronoi_poly_points) == 4:
            poly = ogr.Geometry(ogr.wkbPolygon)
            ring = ogr.Geometry(ogr.wkbLinearRing)
            for node in voronoi_poly_points:
                ring.AddPoint(node[0], node[1])

            # grab first node to close ring
            ring.AddPoint(voronoi_poly_points[0][0], voronoi_poly_points[0][1])

            poly.AddGeometry(ring)
            feat = ogr.Feature(layerDefn)
            feat.SetField('GRID_LON', float(voronoi_centroid[0]))
            feat.SetField('GRID_LAT', float(voronoi_centroid[1]))
            feat.SetGeometry(poly)
            layer.CreateFeature(feat)
758857
def point_cloud(df, columns=[0, 1, 2]):
    """"""
    df = df if isinstance(df, pd.DataFrame) else pd.DataFrame(df)
    if not all(c in df.columns for c in columns):
        columns = list(df.columns)[:3]

    fig = plt.figure()
    ax = fig.add_subplot(111, projection='3d')  # noqa
    Axes3D.scatter(*[df[columns[i]] for i in range(3)], zdir='z', s=20, c=None, depthshade=True)
    return ax
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;
  }
413808
function closestPointnd(c, positions, x, result) {
  var D = numeric.rep([c.length, c.length], 0.0);
  var dvec = numeric.rep([c.length], 0.0);
  for(var i=0; i<c.length; ++i) {
    var pi = positions[c[i]];
    dvec[i] = numeric.dot(pi, x);
    for(var j=0; j<c.length; ++j) {
      var pj = positions[c[j]];
      D[i][j] = D[j][i] = numeric.dot(pi, pj);
    }
  }
  var A = numeric.rep([c.length, c.length+2], 0.0);
  var b = numeric.rep([c.length+2], 0.0);
  b[0] = 1.0-EPSILON;
  b[1] = -(1.0+EPSILON);
  for(var i=0; i<c.length; ++i) {
    A[i][0]   = 1;
    A[i][1]   = -1
    A[i][i+2] = 1;
  }
  for(var attempts=0; attempts<15; ++attempts) {
    var fortran_poop = numeric.solveQP(D, dvec, A, b);
    if(fortran_poop.message.length > 0) {
      //Quadratic form may be singular, perturb and resolve
      for(var i=0; i<c.length; ++i) {
        D[i][i] += 1e-8;
      }
      continue;
    } else if(isNaN(fortran_poop.value[0])) {
      break;
    } else {
      //Success!
      var solution = fortran_poop.solution;
      for(var i=0; i<x.length; ++i) {
        result[i] = 0.0;
        for(var j=0; j<solution.length; ++j) {
          result[i] += solution[j] * positions[c[j]][i];
        }
      }
      return 2.0 * fortran_poop.value[0] + numeric.dot(x,x);
    }
  }
  for(var i=0; i<x.length; ++i) {
    result[i] = Number.NaN;
  }
  return Number.NaN;
}
586281
def __geo_multipoint(lat, lon, elev):
        
        logger_noaa_lpd.info("enter geo_multipoint")
        geo_dict = OrderedDict()
        geometry_dict = OrderedDict()
        coordinates = []
        # bbox = []
        temp = [None, None]
        # 4 unique values
        # # Creates bounding box
        # for index, point in enumerate(lat):
        #     bbox.append(lat[index])
        #     bbox.append(lon[index])

        # Creates coordinates list
        for i in lat:
            temp[0] = i
            for j in lon:
                temp[1] = j
                coordinates.append(copy.copy(temp))
        if elev:
            coordinates = coordinates + elev
        # Create geometry block
        geometry_dict['type'] = 'Polygon'
        geometry_dict['coordinates'] = coordinates
        # Create geo block
        geo_dict['type'] = 'Feature'
        # geo_dict['bbox'] = bbox
        geo_dict['geometry'] = geometry_dict

        return geo_dict
1101101
def from_points(cls, list_of_lists):
        
        result = []
        for l in list_of_lists:
            curve = []
            for point in l:
                curve.append((point.lon, point.lat))
            result.append(curve)
        return Polygon(result)
940414
def init_cao(X, n_clusters, dissim):
    
    n_points, n_attrs = X.shape
    centroids = np.empty((n_clusters, n_attrs), dtype='object')
    # Method is based on determining density of points.
    dens = np.zeros(n_points)
    for iattr in range(n_attrs):
        freq = defaultdict(int)
        for val in X[:, iattr]:
            freq[val] += 1
        for ipoint in range(n_points):
            dens[ipoint] += freq[X[ipoint, iattr]] / float(n_points) / float(n_attrs)

    # Choose initial centroids based on distance and density.
    centroids[0] = X[np.argmax(dens)]
    if n_clusters > 1:
        # For the remaining centroids, choose maximum dens * dissim to the
        # (already assigned) centroid with the lowest dens * dissim.
        for ik in range(1, n_clusters):
            dd = np.empty((ik, n_points))
            for ikk in range(ik):
                dd[ikk] = dissim(X, centroids[ikk]) * dens
            centroids[ik] = X[np.argmax(np.min(dd, axis=0))]

    return centroids
1142394
def voronoi_filled(points_or_voronoi, colors, show_points=False,
                   padding_fraction=0.05, cmap=None, ax=None, alpha=None,
                   edgecolor=None):
  '''
  '''
  from scipy.spatial import Voronoi  # Late import; scipy is optional

  # Disambiguate the first parameter
  if isinstance(points_or_voronoi, Voronoi):
    vor = points_or_voronoi
  else:
    points = np.asanyarray(points_or_voronoi)
    assert points.shape[1] == 2, 'Input points must be 2D'
    vor = Voronoi(points)

  # Borrowed from http://nbviewer.ipython.org/gist/pv/8037100
  regions = []
  vertices = vor.vertices.tolist()

  center = vor.points.mean(axis=0)
  radius = vor.points.ptp().max()*2

  # Construct a map containing all ridges for a given point
  all_ridges = {}
  for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices):
    all_ridges.setdefault(p1, []).append((p2, v1, v2))
    all_ridges.setdefault(p2, []).append((p1, v1, v2))

  # Reconstruct infinite regions
  for p1, region in enumerate(vor.point_region):
    verts = vor.regions[region]
    if all(v >= 0 for v in verts):
      # finite region
      regions.append(verts)
      continue

    # reconstruct a non-finite region
    ridges = all_ridges[p1]
    new_region = [v for v in verts if v >= 0]

    for p2, v1, v2 in ridges:
      if v2 < 0:
        v1, v2 = v2, v1
      if v1 >= 0:
        # finite ridge: already in the region
        continue

      # Compute the missing endpoint of an infinite ridge
      t = vor.points[p2] - vor.points[p1]  # tangent
      t /= np.linalg.norm(t)
      n = np.array([-t[1], t[0]])  # normal

      midpoint = vor.points[[p1, p2]].mean(axis=0)
      direction = np.sign((midpoint - center).dot(n)) * n
      far_point = vor.vertices[v2] + direction * radius

      new_region.append(len(vertices))
      vertices.append(far_point.tolist())

    # sort region counterclockwise
    vs = np.asarray([vertices[v] for v in new_region])
    vs -= vs.mean(axis=0)
    angle_order = np.argsort(np.arctan2(vs[:,1], vs[:,0]))
    new_region = np.array(new_region)[angle_order]

    # finish
    regions.append(new_region)
  vertices = np.asarray(vertices)

  # Plot colored polygons
  if ax is None:
    ax = plt.gca()
  polys = PatchCollection([Polygon(vertices[region]) for region in regions],
                          cmap=cmap, alpha=alpha, edgecolor=edgecolor)
  polys.set_array(np.asanyarray(colors))
  ax.add_collection(polys)

  if show_points:
    ax.plot(vor.points[:,0], vor.points[:,1], 'ko')

  # Zoom to a reasonable scale.
  pad = padding_fraction * (vor.max_bound - vor.min_bound)
  mins = vor.min_bound - pad
  maxes = vor.max_bound + pad
  ax.set_xlim(mins[0], maxes[0])
  ax.set_ylim(mins[1], maxes[1])
  return polys
1352614
public static List<double[]> generatekMeansPlusPlusCentroids(int k,
			List<double[]> input, Random random) {
		int n = input.size();
		assert (n > 0);
		int d = input.get(0).length - 1;
		assert (k <= n);

		List<double[]> centerValue = new ArrayList<double[]>(k);
		// Selects and copies the first centroid
		double[] lastCenter = new double[d];
		System.arraycopy(input.get(random.nextInt(n)), 1, lastCenter, 0, d);
		centerValue.add(lastCenter);

		double[] distance = new double[n];
		for (int j = 0; j < n; j++) {
			distance[j] = Double.POSITIVE_INFINITY;
		}
		for (int i = 1; i < k; i++) {
			// Selects the next centroid
			double sum = 0.0;
			Iterator<double[]> jIter = input.iterator();
			for (int j = 0; j < n; j++) {
				double[] point = jIter.next();
				distance[j] = Math
						.min(distance[j],
								point[0]
										* Metric.distanceSquared(lastCenter,
												point, 1));
				sum += distance[j];

			}
			int candidate = 0;
			if (sum > 0) {
				double nextCenterValue = sum * random.nextDouble();
				double currentValue = distance[0];
				while (!(nextCenterValue < currentValue)) {
					currentValue += distance[++candidate];
				}
			}
			// Copies the selected centroid
			lastCenter = new double[d];
			System.arraycopy(input.get(candidate), 1, lastCenter, 0, d);
			centerValue.add(lastCenter);
		}

		return centerValue;
	}