{"version":3,"sources":["/home/runner/work/turf/turf/packages/turf-clusters-dbscan/dist/cjs/index.cjs","../../index.ts"],"names":[],"mappings":"AAAA;ACCA,oCAAsB;AAEtB,gFAAmB;AACnB,2FAA2B;AAsD3B,SAAS,cAAA,CACP,MAAA,EACA,WAAA,EACA,QAAA,EAII,CAAC,CAAA,EACkC;AAWvC,EAAA,GAAA,CAAI,OAAA,CAAQ,OAAA,IAAW,IAAA,EAAM,OAAA,EAAS,0BAAA,MAAY,CAAA;AAGlD,EAAA,MAAM,UAAA,EAAY,OAAA,CAAQ,UAAA,GAAa,CAAA;AAGvC,EAAA,MAAM,QAAA,EAAU,IAAI,qBAAA,CAAO,MAAA,CAAO,QAAA,CAAS,MAAM,CAAA;AAEjD,EAAA,IAAA,CAAA,MAAW,MAAA,GAAS,MAAA,CAAO,QAAA,EAAU;AACnC,IAAA,OAAA,CAAQ,GAAA,CAAI,KAAA,CAAM,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,EAAG,KAAA,CAAM,QAAA,CAAS,WAAA,CAAY,CAAC,CAAC,CAAA;AAAA,EAC1E;AACA,EAAA,OAAA,CAAQ,MAAA,CAAO,CAAA;AAGf,EAAA,IAAI,QAAA,EAAU,MAAA,CAAO,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,KAAK,CAAA;AAG9C,EAAA,IAAI,SAAA,EAAW,MAAA,CAAO,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,KAAK,CAAA;AAG/C,EAAA,IAAI,QAAA,EAAU,MAAA,CAAO,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,KAAK,CAAA;AAG9C,EAAA,IAAI,WAAA,EAAuB,MAAA,CAAO,QAAA,CAAS,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAA;AAGxD,EAAA,MAAM,YAAA,EAAc,CAAC,KAAA,EAAA,GAAkC;AACrD,IAAA,MAAM,MAAA,EAAQ,MAAA,CAAO,QAAA,CAAS,KAAK,CAAA;AACnC,IAAA,MAAM,CAAC,CAAA,EAAG,CAAC,EAAA,EAAI,KAAA,CAAM,QAAA,CAAS,WAAA;AAE9B,IAAA,OAGK,SAAA,CAAA,MAAA,CAAe,OAAA,EAAS,CAAA,EAAG,CAAA,EAAG,KAAA,CAAA,EAAW,WAAW,CAAA,CACpD,GAAA,CAAI,CAAC,EAAA,EAAA,GAAA,CAAQ;AAAA,MACZ,IAAA,EAAM,MAAA,CAAO,QAAA,CAAS,EAAE,CAAA,CAAE,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA;AAAA,MAChD,IAAA,EAAM,MAAA,CAAO,QAAA,CAAS,EAAE,CAAA,CAAE,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA;AAAA,MAChD,IAAA,EAAM,MAAA,CAAO,QAAA,CAAS,EAAE,CAAA,CAAE,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA;AAAA,MAChD,IAAA,EAAM,MAAA,CAAO,QAAA,CAAS,EAAE,CAAA,CAAE,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA;AAAA,MAChD,KAAA,EAAO;AAAA,IACT,CAAA,CAAE,CAAA;AAAA,EAER,CAAA;AAGA,EAAA,MAAM,cAAA,EAAgB,CAAC,WAAA,EAAqB,SAAA,EAAA,GAA8B;AACxE,IAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,EAAA,EAAI,SAAA,CAAU,MAAA,EAAQ,CAAA,EAAA,EAAK;AACzC,MAAA,IAAI,SAAA,EAAW,SAAA,CAAU,CAAC,CAAA;AAC1B,MAAA,MAAM,cAAA,EAAgB,QAAA,CAAS,KAAA;AAC/B,MAAA,GAAA,CAAI,CAAC,OAAA,CAAQ,aAAa,CAAA,EAAG;AAC3B,QAAA,OAAA,CAAQ,aAAa,EAAA,EAAI,IAAA;AACzB,QAAA,MAAM,cAAA,EAAgB,WAAA,CAAY,aAAa,CAAA;AAC/C,QAAA,GAAA,CAAI,aAAA,CAAc,OAAA,GAAU,SAAA,EAAW;AACrC,UAAA,SAAA,CAAU,IAAA,CAAK,GAAG,aAAa,CAAA;AAAA,QACjC;AAAA,MACF;AACA,MAAA,GAAA,CAAI,CAAC,QAAA,CAAS,aAAa,CAAA,EAAG;AAC5B,QAAA,QAAA,CAAS,aAAa,EAAA,EAAI,IAAA;AAC1B,QAAA,UAAA,CAAW,aAAa,EAAA,EAAI,WAAA;AAAA,MAC9B;AAAA,IACF;AAAA,EACF,CAAA;AAGA,EAAA,IAAI,gBAAA,EAAkB,CAAA;AACtB,EAAA,MAAA,CAAO,QAAA,CAAS,OAAA,CAAQ,CAAC,CAAA,EAAG,KAAA,EAAA,GAAU;AACpC,IAAA,GAAA,CAAI,OAAA,CAAQ,KAAK,CAAA,EAAG,MAAA;AACpB,IAAA,MAAM,UAAA,EAAY,WAAA,CAAY,KAAK,CAAA;AACnC,IAAA,GAAA,CAAI,SAAA,CAAU,OAAA,GAAU,SAAA,EAAW;AACjC,MAAA,MAAM,YAAA,EAAc,eAAA;AACpB,MAAA,eAAA,EAAA;AACA,MAAA,OAAA,CAAQ,KAAK,EAAA,EAAI,IAAA;AACjB,MAAA,aAAA,CAAc,WAAA,EAAa,SAAS,CAAA;AAAA,IACtC,EAAA,KAAO;AACL,MAAA,OAAA,CAAQ,KAAK,EAAA,EAAI,IAAA;AAAA,IACnB;AAAA,EACF,CAAC,CAAA;AAGD,EAAA,MAAA,CAAO,QAAA,CAAS,OAAA,CAAQ,CAAC,CAAA,EAAG,KAAA,EAAA,GAAU;AACpC,IAAA,IAAI,aAAA,EAAe,MAAA,CAAO,QAAA,CAAS,KAAK,CAAA;AACxC,IAAA,GAAA,CAAI,CAAC,YAAA,CAAa,UAAA,EAAY;AAC5B,MAAA,YAAA,CAAa,WAAA,EAAa,CAAC,CAAA;AAAA,IAC7B;AAEA,IAAA,GAAA,CAAI,UAAA,CAAW,KAAK,EAAA,GAAK,CAAA,EAAG;AAC1B,MAAA,YAAA,CAAa,UAAA,CAAW,OAAA,EAAS,OAAA,CAAQ,KAAK,EAAA,EAAI,OAAA,EAAS,MAAA;AAC3D,MAAA,YAAA,CAAa,UAAA,CAAW,QAAA,EAAU,UAAA,CAAW,KAAK,CAAA;AAAA,IACpD,EAAA,KAAO;AACL,MAAA,YAAA,CAAa,UAAA,CAAW,OAAA,EAAS,OAAA;AAAA,IACnC;AAAA,EACF,CAAC,CAAA;AAED,EAAA,OAAO,MAAA;AACT;AAGA,IAAO,cAAA,EAAQ,cAAA;ADtGf;AACE;AACA;AACF,yEAAC","file":"/home/runner/work/turf/turf/packages/turf-clusters-dbscan/dist/cjs/index.cjs","sourcesContent":[null,"import { GeoJsonProperties, FeatureCollection, Point } from \"geojson\";\nimport { clone } from \"@turf/clone\";\nimport { Units } from \"@turf/helpers\";\nimport KDBush from \"kdbush\";\nimport * as geokdbush from \"geokdbush\";\n\n/**\n * Point classification within the cluster.\n *\n * @typedef {\"core\" | \"edge\" | \"noise\"} Dbscan\n */\ntype Dbscan = \"core\" | \"edge\" | \"noise\";\n\n/**\n * Properties assigned to each clustered point.\n *\n * @extends GeoJsonProperties\n * @typedef {object} DbscanProps\n * @property {Dbscan} [dbscan] type of point it has been classified as\n * @property {number} [cluster] associated clusterId\n */\ntype DbscanProps = GeoJsonProperties & {\n  dbscan?: Dbscan;\n  cluster?: number;\n};\n\n// Structure of a point in the spatial index\ntype IndexedPoint = {\n  minX: number;\n  minY: number;\n  maxX: number;\n  maxY: number;\n  index: number;\n};\n\n/**\n * Takes a set of {@link Point|points} and partition them into clusters according to {@link https://en.wikipedia.org/wiki/DBSCAN|DBSCAN's} data clustering algorithm.\n *\n * @function\n * @param {FeatureCollection<Point>} points to be clustered\n * @param {number} maxDistance Maximum Distance between any point of the cluster to generate the clusters (kilometers by default, see options)\n * @param {Object} [options={}] Optional parameters\n * @param {Units} [options.units=\"kilometers\"] in which `maxDistance` is expressed, Supports all valid Turf {@link https://turfjs.org/docs/api/types/Units Units}\n * @param {boolean} [options.mutate=false] Allows GeoJSON input to be mutated\n * @param {number} [options.minPoints=3] Minimum number of points to generate a single cluster,\n * points which do not meet this requirement will be classified as an 'edge' or 'noise'.\n * @returns {FeatureCollection<Point, DbscanProps>} Clustered Points with an additional two properties associated to each Feature:\n * - {number} cluster - the associated clusterId\n * - {string} dbscan - type of point it has been classified as ('core'|'edge'|'noise')\n * @example\n * // create random points with random z-values in their properties\n * var points = turf.randomPoint(100, {bbox: [0, 30, 20, 50]});\n * var maxDistance = 100;\n * var clustered = turf.clustersDbscan(points, maxDistance);\n *\n * //addToMap\n * var addToMap = [clustered];\n */\nfunction clustersDbscan(\n  points: FeatureCollection<Point>,\n  maxDistance: number,\n  options: {\n    units?: Units;\n    minPoints?: number;\n    mutate?: boolean;\n  } = {}\n): FeatureCollection<Point, DbscanProps> {\n  // Input validation being handled by Typescript\n  // TODO oops! No it isn't. Typescript doesn't do runtime checking. We should\n  // re-enable these checks, though will have to wait for a major version bump\n  // as more restrictive checks could break currently working code.\n  // collectionOf(points, 'Point', 'points must consist of a FeatureCollection of only Points');\n  // if (maxDistance === null || maxDistance === undefined) throw new Error('maxDistance is required');\n  // if (!(Math.sign(maxDistance) > 0)) throw new Error('maxDistance is invalid');\n  // if (!(minPoints === undefined || minPoints === null || Math.sign(minPoints) > 0)) throw new Error('options.minPoints is invalid');\n\n  // Clone points to prevent any mutations\n  if (options.mutate !== true) points = clone(points);\n\n  // Defaults\n  const minPoints = options.minPoints || 3;\n\n  // Create a spatial index\n  const kdIndex = new KDBush(points.features.length);\n  // Index each point for spatial queries\n  for (const point of points.features) {\n    kdIndex.add(point.geometry.coordinates[0], point.geometry.coordinates[1]);\n  }\n  kdIndex.finish();\n\n  // Keeps track of whether a point has been visited or not.\n  var visited = points.features.map((_) => false);\n\n  // Keeps track of whether a point is assigned to a cluster or not.\n  var assigned = points.features.map((_) => false);\n\n  // Keeps track of whether a point is noise|edge or not.\n  var isnoise = points.features.map((_) => false);\n\n  // Keeps track of the clusterId for each point\n  var clusterIds: number[] = points.features.map((_) => -1);\n\n  // Function to find neighbors of a point within a given distance\n  const regionQuery = (index: number): IndexedPoint[] => {\n    const point = points.features[index];\n    const [x, y] = point.geometry.coordinates;\n\n    return (\n      geokdbush\n        // @ts-expect-error 2345 until https://github.com/mourner/geokdbush/issues/20 is resolved\n        .around<number>(kdIndex, x, y, undefined, maxDistance)\n        .map((id) => ({\n          minX: points.features[id].geometry.coordinates[0],\n          minY: points.features[id].geometry.coordinates[1],\n          maxX: points.features[id].geometry.coordinates[0],\n          maxY: points.features[id].geometry.coordinates[1],\n          index: id,\n        }))\n    );\n  };\n\n  // Function to expand a cluster\n  const expandCluster = (clusteredId: number, neighbors: IndexedPoint[]) => {\n    for (var i = 0; i < neighbors.length; i++) {\n      var neighbor = neighbors[i];\n      const neighborIndex = neighbor.index;\n      if (!visited[neighborIndex]) {\n        visited[neighborIndex] = true;\n        const nextNeighbors = regionQuery(neighborIndex);\n        if (nextNeighbors.length >= minPoints) {\n          neighbors.push(...nextNeighbors);\n        }\n      }\n      if (!assigned[neighborIndex]) {\n        assigned[neighborIndex] = true;\n        clusterIds[neighborIndex] = clusteredId;\n      }\n    }\n  };\n\n  // Main DBSCAN clustering algorithm\n  var nextClusteredId = 0;\n  points.features.forEach((_, index) => {\n    if (visited[index]) return;\n    const neighbors = regionQuery(index);\n    if (neighbors.length >= minPoints) {\n      const clusteredId = nextClusteredId;\n      nextClusteredId++;\n      visited[index] = true;\n      expandCluster(clusteredId, neighbors);\n    } else {\n      isnoise[index] = true;\n    }\n  });\n\n  // Assign DBSCAN properties to each point\n  points.features.forEach((_, index) => {\n    var clusterPoint = points.features[index];\n    if (!clusterPoint.properties) {\n      clusterPoint.properties = {};\n    }\n\n    if (clusterIds[index] >= 0) {\n      clusterPoint.properties.dbscan = isnoise[index] ? \"edge\" : \"core\";\n      clusterPoint.properties.cluster = clusterIds[index];\n    } else {\n      clusterPoint.properties.dbscan = \"noise\";\n    }\n  });\n\n  return points as FeatureCollection<Point, DbscanProps>;\n}\n\nexport { Dbscan, DbscanProps, clustersDbscan };\nexport default clustersDbscan;\n"]}