{"version":3,"sources":["../../index.ts","../../lib/rbush-export.ts"],"sourcesContent":["import { GeoJsonProperties, FeatureCollection, Point } from \"geojson\";\nimport { clone } from \"@turf/clone\";\nimport { distance } from \"@turf/distance\";\nimport { degreesToRadians, lengthToDegrees, Units } from \"@turf/helpers\";\nimport { rbush as RBush } from \"./lib/rbush-export.js\";\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} 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 {string} [options.units=\"kilometers\"] in which `maxDistance` is expressed, can be degrees, radians, miles, or kilometers\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} 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,\n maxDistance: number,\n options: {\n units?: Units;\n minPoints?: number;\n mutate?: boolean;\n } = {}\n): FeatureCollection {\n // Input validation being handled by Typescript\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 // Calculate the distance in degrees for region queries\n const latDistanceInDegrees = lengthToDegrees(maxDistance, options.units);\n\n // Create a spatial index\n var tree = new RBush(points.features.length);\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 // Index each point for spatial queries\n tree.load(\n points.features.map((point, index) => {\n var [x, y] = point.geometry.coordinates;\n return {\n minX: x,\n minY: y,\n maxX: x,\n maxY: y,\n index: index,\n } as IndexedPoint;\n })\n );\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 const minY = Math.max(y - latDistanceInDegrees, -90.0);\n const maxY = Math.min(y + latDistanceInDegrees, 90.0);\n\n const lonDistanceInDegrees = (function () {\n // Handle the case where the bounding box crosses the poles\n if (minY < 0 && maxY > 0) {\n return latDistanceInDegrees;\n }\n if (Math.abs(minY) < Math.abs(maxY)) {\n return latDistanceInDegrees / Math.cos(degreesToRadians(maxY));\n } else {\n return latDistanceInDegrees / Math.cos(degreesToRadians(minY));\n }\n })();\n\n const minX = Math.max(x - lonDistanceInDegrees, -360.0);\n const maxX = Math.min(x + lonDistanceInDegrees, 360.0);\n\n // Calculate the bounding box for the region query\n const bbox = { minX, minY, maxX, maxY };\n return (tree.search(bbox) as ReadonlyArray).filter(\n (neighbor) => {\n const neighborIndex = neighbor.index;\n const neighborPoint = points.features[neighborIndex];\n const distanceInKm = distance(point, neighborPoint, {\n units: \"kilometers\",\n });\n return distanceInKm <= maxDistance;\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;\n}\n\nexport { Dbscan, DbscanProps, clustersDbscan };\nexport default clustersDbscan;\n","// Get around problems with moduleResolution node16 and some older libraries.\n// Manifests as \"This expression is not callable ... has no call signatures\"\n// https://stackoverflow.com/a/74709714\n\nimport lib from \"rbush\";\n\nexport const rbush = lib as unknown as typeof lib.default;\n"],"mappings":";AACA,SAAS,aAAa;AACtB,SAAS,gBAAgB;AACzB,SAAS,kBAAkB,uBAA8B;;;ACCzD,OAAO,SAAS;AAET,IAAM,QAAQ;;;ADoDrB,SAAS,eACP,QACA,aACA,UAII,CAAC,GACkC;AAQvC,MAAI,QAAQ,WAAW,KAAM,UAAS,MAAM,MAAM;AAGlD,QAAM,YAAY,QAAQ,aAAa;AAGvC,QAAM,uBAAuB,gBAAgB,aAAa,QAAQ,KAAK;AAGvE,MAAI,OAAO,IAAI,MAAM,OAAO,SAAS,MAAM;AAG3C,MAAI,UAAU,OAAO,SAAS,IAAI,CAAC,MAAM,KAAK;AAG9C,MAAI,WAAW,OAAO,SAAS,IAAI,CAAC,MAAM,KAAK;AAG/C,MAAI,UAAU,OAAO,SAAS,IAAI,CAAC,MAAM,KAAK;AAG9C,MAAI,aAAuB,OAAO,SAAS,IAAI,CAAC,MAAM,EAAE;AAGxD,OAAK;AAAA,IACH,OAAO,SAAS,IAAI,CAAC,OAAO,UAAU;AACpC,UAAI,CAAC,GAAG,CAAC,IAAI,MAAM,SAAS;AAC5B,aAAO;AAAA,QACL,MAAM;AAAA,QACN,MAAM;AAAA,QACN,MAAM;AAAA,QACN,MAAM;AAAA,QACN;AAAA,MACF;AAAA,IACF,CAAC;AAAA,EACH;AAGA,QAAM,cAAc,CAAC,UAAkC;AACrD,UAAM,QAAQ,OAAO,SAAS,KAAK;AACnC,UAAM,CAAC,GAAG,CAAC,IAAI,MAAM,SAAS;AAE9B,UAAM,OAAO,KAAK,IAAI,IAAI,sBAAsB,GAAK;AACrD,UAAM,OAAO,KAAK,IAAI,IAAI,sBAAsB,EAAI;AAEpD,UAAM,uBAAwB,WAAY;AAExC,UAAI,OAAO,KAAK,OAAO,GAAG;AACxB,eAAO;AAAA,MACT;AACA,UAAI,KAAK,IAAI,IAAI,IAAI,KAAK,IAAI,IAAI,GAAG;AACnC,eAAO,uBAAuB,KAAK,IAAI,iBAAiB,IAAI,CAAC;AAAA,MAC/D,OAAO;AACL,eAAO,uBAAuB,KAAK,IAAI,iBAAiB,IAAI,CAAC;AAAA,MAC/D;AAAA,IACF,EAAG;AAEH,UAAM,OAAO,KAAK,IAAI,IAAI,sBAAsB,IAAM;AACtD,UAAM,OAAO,KAAK,IAAI,IAAI,sBAAsB,GAAK;AAGrD,UAAM,OAAO,EAAE,MAAM,MAAM,MAAM,KAAK;AACtC,WAAQ,KAAK,OAAO,IAAI,EAAkC;AAAA,MACxD,CAAC,aAAa;AACZ,cAAM,gBAAgB,SAAS;AAC/B,cAAM,gBAAgB,OAAO,SAAS,aAAa;AACnD,cAAM,eAAe,SAAS,OAAO,eAAe;AAAA,UAClD,OAAO;AAAA,QACT,CAAC;AACD,eAAO,gBAAgB;AAAA,MACzB;AAAA,IACF;AAAA,EACF;AAGA,QAAM,gBAAgB,CAAC,aAAqB,cAA8B;AACxE,aAAS,IAAI,GAAG,IAAI,UAAU,QAAQ,KAAK;AACzC,UAAI,WAAW,UAAU,CAAC;AAC1B,YAAM,gBAAgB,SAAS;AAC/B,UAAI,CAAC,QAAQ,aAAa,GAAG;AAC3B,gBAAQ,aAAa,IAAI;AACzB,cAAM,gBAAgB,YAAY,aAAa;AAC/C,YAAI,cAAc,UAAU,WAAW;AACrC,oBAAU,KAAK,GAAG,aAAa;AAAA,QACjC;AAAA,MACF;AACA,UAAI,CAAC,SAAS,aAAa,GAAG;AAC5B,iBAAS,aAAa,IAAI;AAC1B,mBAAW,aAAa,IAAI;AAAA,MAC9B;AAAA,IACF;AAAA,EACF;AAGA,MAAI,kBAAkB;AACtB,SAAO,SAAS,QAAQ,CAAC,GAAG,UAAU;AACpC,QAAI,QAAQ,KAAK,EAAG;AACpB,UAAM,YAAY,YAAY,KAAK;AACnC,QAAI,UAAU,UAAU,WAAW;AACjC,YAAM,cAAc;AACpB;AACA,cAAQ,KAAK,IAAI;AACjB,oBAAc,aAAa,SAAS;AAAA,IACtC,OAAO;AACL,cAAQ,KAAK,IAAI;AAAA,IACnB;AAAA,EACF,CAAC;AAGD,SAAO,SAAS,QAAQ,CAAC,GAAG,UAAU;AACpC,QAAI,eAAe,OAAO,SAAS,KAAK;AACxC,QAAI,CAAC,aAAa,YAAY;AAC5B,mBAAa,aAAa,CAAC;AAAA,IAC7B;AAEA,QAAI,WAAW,KAAK,KAAK,GAAG;AAC1B,mBAAa,WAAW,SAAS,QAAQ,KAAK,IAAI,SAAS;AAC3D,mBAAa,WAAW,UAAU,WAAW,KAAK;AAAA,IACpD,OAAO;AACL,mBAAa,WAAW,SAAS;AAAA,IACnC;AAAA,EACF,CAAC;AAED,SAAO;AACT;AAGA,IAAO,+BAAQ;","names":[]}