aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndrew Harvey <andrew@alantgeo.com.au>2021-05-04 14:50:52 +1000
committerAndrew Harvey <andrew@alantgeo.com.au>2021-05-04 14:50:52 +1000
commit5039b0dbf3af3b93466069927d794f5b1c8ccf81 (patch)
tree82f675877771b06da8cd4b82778c68b65d11cb91
parent0e9a1861bac8b310c757a2c3fd92d67b50ebba12 (diff)
add cluster library
-rw-r--r--.gitlab-ci.yml2
-rw-r--r--cluster.js64
-rw-r--r--package.json9
-rw-r--r--test/cluster.js83
-rw-r--r--yarn.lock130
5 files changed, 286 insertions, 2 deletions
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index a165d48..fe420c2 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -39,7 +39,7 @@ build:
- echo "deb https://dl.yarnpkg.com/debian/ stable main" | tee /etc/apt/sources.list.d/yarn.list
- apt-get update && apt-get install -y yarn nodejs
- yarn install
- - node test/index.js
+ - yarn run test
- mkdir -p dist data
- mkdir -p data/vicmap/ll_gda94/sde_shape/whole/VIC/VMADD/layer
- touch data/VICMAP_ADDRESS.zip
diff --git a/cluster.js b/cluster.js
new file mode 100644
index 0000000..c716063
--- /dev/null
+++ b/cluster.js
@@ -0,0 +1,64 @@
+const CheapRuler = require('cheap-ruler')
+const ruler = new CheapRuler(-37, 'meters')
+
+/**
+ * Cluster points together where within threshold distance.
+ *
+ * @param {Array} features - GeoJSON Point Features
+ * @param {number} thresholdDistance - Maximum distance between points to cluster together
+ *
+ * @returns {Array} clusters, where unclustered features are returned as single feature clusters
+ */
+module.exports = (features, thresholdDistance) => {
+ // Array of clusters where each cluster is a Set of feature index's
+ const clusters = []
+
+ features.map((a, ai) => {
+ features.map((b, bi) => {
+ // skip comparing with self
+ if (ai === bi) return
+
+ const distance = ruler.distance(a.geometry.coordinates, b.geometry.coordinates)
+ if (distance < thresholdDistance) {
+ // link into a cluster
+ let addedToExistingCluster = false
+ clusters.forEach((cluster, i) => {
+ if (cluster.has(ai) || cluster.has(bi)) {
+ // insert into this cluster
+ clusters[i].add(ai)
+ clusters[i].add(bi)
+
+ addedToExistingCluster = true
+ }
+ })
+
+ if (!addedToExistingCluster) {
+ // create a new cluster
+ const newCluster = new Set()
+ newCluster.add(ai)
+ newCluster.add(bi)
+ clusters.push(newCluster)
+ }
+ } // else don't cluster together
+ })
+ })
+
+ // result is array of clusters, including non-clustered features as single item clusters
+ const result = clusters.map(cluster => {
+ return Array.from(cluster).map(index => {
+ return features[index]
+ })
+ })
+
+ // find features not clustered
+ features.map((feature, index) => {
+ // if feature not a cluster, return as an single item cluster
+ const featureInACluster = clusters.map(cluster => cluster.has(index)).reduce((acc, cur) => acc || !!cur, false)
+ if (!featureInACluster) {
+ result.push([feature])
+ }
+ })
+
+ return result
+
+}
diff --git a/package.json b/package.json
index 3aa7820..ff27c53 100644
--- a/package.json
+++ b/package.json
@@ -5,12 +5,19 @@
"main": "index.js",
"author": "Andrew Harvey <andrew@alantgeo.com.au>",
"license": "MIT",
+ "scripts": {
+ "test": "./node_modules/.bin/tape test/index.js test/cluster.js"
+ },
"dependencies": {
"capital-case": "^1.0.4",
+ "cheap-ruler": "^3.0.1",
+ "flatbush": "^3.3.0",
+ "geoflatbush": "^1.0.0",
"ndjson": "^2.0.0",
"readable-stream": "^3.6.0",
"tape": "^5.2.2",
- "title-case": "^3.0.3"
+ "title-case": "^3.0.3",
+ "yargs": "^17.0.0"
},
"engines": {
"node": ">=12.3"
diff --git a/test/cluster.js b/test/cluster.js
new file mode 100644
index 0000000..ddec552
--- /dev/null
+++ b/test/cluster.js
@@ -0,0 +1,83 @@
+const test = require('tape')
+
+const cluster = require('../cluster.js')
+
+const A = {
+ type: 'Feature',
+ id: 'A',
+ properties: {},
+ geometry: {
+ type: 'Point',
+ coordinates: [0, 0]
+ }
+}
+
+const B = {
+ type: 'Feature',
+ id: 'B',
+ properties: {},
+ geometry: {
+ type: 'Point',
+ coordinates: [0, 0]
+ }
+}
+
+const C = {
+ type: 'Feature',
+ id: 'C',
+ properties: {},
+ geometry: {
+ type: 'Point',
+ coordinates: [0.000001, 0.000001]
+ }
+}
+
+const D = {
+ type: 'Feature',
+ id: 'D',
+ properties: {},
+ geometry: {
+ type: 'Point',
+ coordinates: [1, 1]
+ }
+}
+
+test('cluster', t => {
+ t.same(
+ cluster([], 100),
+ [],
+ 'empty input returns empty output'
+ )
+
+ t.same(
+ cluster([A], 100),
+ [[A]],
+ 'single feature input returns single feature output cluster'
+ )
+
+ t.same(
+ cluster([A, B], 100),
+ [[A, B]],
+ 'overlapping points clustered'
+ )
+
+ t.same(
+ cluster([A, C], 100),
+ [[A, C]],
+ 'nearby points clustered'
+ )
+
+ t.same(
+ cluster([A, D], 100),
+ [[A], [D]],
+ 'far away points not clustered'
+ )
+
+ t.same(
+ cluster([A, B, C, D], 100),
+ [[A, B, C], [D]],
+ 'some clustered others not'
+ )
+
+ t.end()
+})
diff --git a/yarn.lock b/yarn.lock
index 658af96..a402885 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -2,6 +2,18 @@
# yarn lockfile v1
+ansi-regex@^5.0.0:
+ version "5.0.0"
+ resolved "https://registry.yarnpkg.com/ansi-regex/-/ansi-regex-5.0.0.tgz#388539f55179bf39339c81af30a654d69f87cb75"
+ integrity sha512-bY6fj56OUQ0hU1KjFNDQuJFezqKdrAyFdIevADiqrWHwSlbmBNMHp5ak2f40Pm8JTFyM2mqxkG6ngkHO11f/lg==
+
+ansi-styles@^4.0.0:
+ version "4.3.0"
+ resolved "https://registry.yarnpkg.com/ansi-styles/-/ansi-styles-4.3.0.tgz#edd803628ae71c04c85ae7a0906edad34b648937"
+ integrity sha512-zbB9rCJAT1rbjiVDb2hqKFHNYLxgtk8NURxZ3IZwD3F6NtxbXZQCnnSi1Lkx+IDohdPlFp222wVALIheZJQSEg==
+ dependencies:
+ color-convert "^2.0.1"
+
array-filter@^1.0.0:
version "1.0.0"
resolved "https://registry.yarnpkg.com/array-filter/-/array-filter-1.0.0.tgz#baf79e62e6ef4c2a4c0b831232daffec251f9d83"
@@ -44,6 +56,32 @@ capital-case@^1.0.4:
tslib "^2.0.3"
upper-case-first "^2.0.2"
+cheap-ruler@^3.0.1:
+ version "3.0.1"
+ resolved "https://registry.yarnpkg.com/cheap-ruler/-/cheap-ruler-3.0.1.tgz#3df3bd6fe664d8cab9e9e826bba24d7271e7645a"
+ integrity sha512-bmBKGkNKcwCpltGzfMXZMrFE06SG8dgSv96W39Mk+um7zbNTQNumKl5LBwFC0gbffy8Jnf0+SDHsOqpDYJxYow==
+
+cliui@^7.0.2:
+ version "7.0.4"
+ resolved "https://registry.yarnpkg.com/cliui/-/cliui-7.0.4.tgz#a0265ee655476fc807aea9df3df8df7783808b4f"
+ integrity sha512-OcRE68cOsVMXp1Yvonl/fzkQOyjLSu/8bhPDfQt0e0/Eb283TKP20Fs2MqoPsr9SwA595rRCA+QMzYc9nBP+JQ==
+ dependencies:
+ string-width "^4.2.0"
+ strip-ansi "^6.0.0"
+ wrap-ansi "^7.0.0"
+
+color-convert@^2.0.1:
+ version "2.0.1"
+ resolved "https://registry.yarnpkg.com/color-convert/-/color-convert-2.0.1.tgz#72d3a68d598c9bdb3af2ad1e84f21d896abd4de3"
+ integrity sha512-RRECPsj7iu/xb5oKYcsFHSppFNnsj/52OVTRKb4zP5onXwVF3zVmmToNcOfGC+CRDpfK/U584fMg38ZHCaElKQ==
+ dependencies:
+ color-name "~1.1.4"
+
+color-name@~1.1.4:
+ version "1.1.4"
+ resolved "https://registry.yarnpkg.com/color-name/-/color-name-1.1.4.tgz#c2a09a87acbde69543de6f63fa3995c826c536a2"
+ integrity sha512-dOy+3AuW3a2wNbZHIuMZpTcgjGuLU/uBL/ubcZF9OXbDo8ff4O8yVp5Bf0efS8uEoYo5q4Fx7dY9OgQGXgAsQA==
+
concat-map@0.0.1:
version "0.0.1"
resolved "https://registry.yarnpkg.com/concat-map/-/concat-map-0.0.1.tgz#d8a96bd77fd68df7793a73036a3ba0d5405d477b"
@@ -89,6 +127,11 @@ dotignore@^0.1.2:
dependencies:
minimatch "^3.0.4"
+emoji-regex@^8.0.0:
+ version "8.0.0"
+ resolved "https://registry.yarnpkg.com/emoji-regex/-/emoji-regex-8.0.0.tgz#e818fd69ce5ccfcb404594f842963bf53164cc37"
+ integrity sha512-MSjYzcWNOA0ewAHpz0MxpYFvwg6yjy1NG3xteoqz644VCo/RPgnr1/GGt+ic3iJTzQ8Eu3TdM14SawnVUmGE6A==
+
es-abstract@^1.18.0-next.1, es-abstract@^1.18.0-next.2:
version "1.18.0"
resolved "https://registry.yarnpkg.com/es-abstract/-/es-abstract-1.18.0.tgz#ab80b359eecb7ede4c298000390bc5ac3ec7b5a4"
@@ -134,6 +177,23 @@ es-to-primitive@^1.2.1:
is-date-object "^1.0.1"
is-symbol "^1.0.2"
+escalade@^3.1.1:
+ version "3.1.1"
+ resolved "https://registry.yarnpkg.com/escalade/-/escalade-3.1.1.tgz#d8cfdc7000965c5a0174b4a82eaa5c0552742e40"
+ integrity sha512-k0er2gUkLf8O0zKJiAhmkTnJlTvINGv7ygDNPbeIsX/TJjGJZHuh9B2UxbsaEkmlEo9MfhrSzmhIlhRlI2GXnw==
+
+flatbush@^3.3.0:
+ version "3.3.0"
+ resolved "https://registry.yarnpkg.com/flatbush/-/flatbush-3.3.0.tgz#b68c9149107ae86d2bce6373491f404ba4f4534e"
+ integrity sha512-F3EzQvKpdmXUbFwWxLKBpytOFEGYQMCTBLuqZ4GEajFOEAvnOIBiyxW3OFSZXIOtpCS8teN6bFEpNZtnVXuDQA==
+ dependencies:
+ flatqueue "^1.2.0"
+
+flatqueue@^1.1.0, flatqueue@^1.2.0:
+ version "1.2.1"
+ resolved "https://registry.yarnpkg.com/flatqueue/-/flatqueue-1.2.1.tgz#82f501758fc5925742fbeb478637230456157ef2"
+ integrity sha512-X86TpWS1rGuY7m382HuA9vngLeDuWA9lJvhEG+GfgKMV5onSvx5a71cl7GMbXzhWtlN9dGfqOBrpfqeOtUfGYQ==
+
for-each@^0.3.3:
version "0.3.3"
resolved "https://registry.yarnpkg.com/for-each/-/for-each-0.3.3.tgz#69b447e88a0a5d32c3e7084f3f1710034b21376e"
@@ -156,6 +216,18 @@ function-bind@^1.1.1:
resolved "https://registry.yarnpkg.com/function-bind/-/function-bind-1.1.1.tgz#a56899d3ea3c9bab874bb9773b7c5ede92f4895d"
integrity sha512-yIovAzMX49sF8Yl58fSCWJ5svSLuaibPxXQJFLmBObTuCr0Mf1KiPopGM9NiFjiYBCbfaa2Fh6breQ6ANVTI0A==
+geoflatbush@^1.0.0:
+ version "1.0.0"
+ resolved "https://registry.yarnpkg.com/geoflatbush/-/geoflatbush-1.0.0.tgz#5e3041e9dd529774ea17f4d81fbd21465c108ef1"
+ integrity sha512-epTkkL1KUbbJDRJW2AcN2yKkj4GHTivXWgssZZtYtLRh8VowckqBjxUCIJq8ZAcUXkJz31+Tu1d9F2sTq5klvg==
+ dependencies:
+ flatqueue "^1.1.0"
+
+get-caller-file@^2.0.5:
+ version "2.0.5"
+ resolved "https://registry.yarnpkg.com/get-caller-file/-/get-caller-file-2.0.5.tgz#4f94412a82db32f36e3b0b9741f8a97feb031f7e"
+ integrity sha512-DyFP3BM/3YHTQOCUL/w0OZHR0lpKeGrxotcHWcqNEdnltqFwXVfhEBQ94eIo34AfQpo0rGki4cyIiftY06h2Fg==
+
get-intrinsic@^1.0.1, get-intrinsic@^1.0.2, get-intrinsic@^1.1.0, get-intrinsic@^1.1.1:
version "1.1.1"
resolved "https://registry.yarnpkg.com/get-intrinsic/-/get-intrinsic-1.1.1.tgz#15f59f376f855c446963948f0d24cd3637b4abc6"
@@ -243,6 +315,11 @@ is-date-object@^1.0.1, is-date-object@^1.0.2:
resolved "https://registry.yarnpkg.com/is-date-object/-/is-date-object-1.0.2.tgz#bda736f2cd8fd06d32844e7743bfa7494c3bfd7e"
integrity sha512-USlDT524woQ08aoZFzh3/Z6ch9Y/EWXEHQ/AaRN0SkKq4t2Jw2R2339tSXmwuVoY7LLlBCbOIlx2myP/L5zk0g==
+is-fullwidth-code-point@^3.0.0:
+ version "3.0.0"
+ resolved "https://registry.yarnpkg.com/is-fullwidth-code-point/-/is-fullwidth-code-point-3.0.0.tgz#f116f8064fe90b3f7844a38997c0b75051269f1d"
+ integrity sha512-zymm5+u+sCsSWyD9qNaejV3DFvhCKclKdizYaJUuHA83RLjb7nSuGnddCHGv0hk+KY7BMAlsWeK4Ueg6EV6XQg==
+
is-map@^2.0.1, is-map@^2.0.2:
version "2.0.2"
resolved "https://registry.yarnpkg.com/is-map/-/is-map-2.0.2.tgz#00922db8c9bf73e81b7a335827bc2a43f2b91127"
@@ -414,6 +491,11 @@ regexp.prototype.flags@^1.3.0:
call-bind "^1.0.2"
define-properties "^1.1.3"
+require-directory@^2.1.1:
+ version "2.1.1"
+ resolved "https://registry.yarnpkg.com/require-directory/-/require-directory-2.1.1.tgz#8c64ad5fd30dab1c976e2344ffe7f792a6a6df42"
+ integrity sha1-jGStX9MNqxyXbiNE/+f3kqam30I=
+
resolve@^2.0.0-next.3:
version "2.0.0-next.3"
resolved "https://registry.yarnpkg.com/resolve/-/resolve-2.0.0-next.3.tgz#d41016293d4a8586a39ca5d9b5f15cbea1f55e46"
@@ -450,6 +532,15 @@ split2@^3.0.0:
dependencies:
readable-stream "^3.0.0"
+string-width@^4.1.0, string-width@^4.2.0:
+ version "4.2.2"
+ resolved "https://registry.yarnpkg.com/string-width/-/string-width-4.2.2.tgz#dafd4f9559a7585cfba529c6a0a4f73488ebd4c5"
+ integrity sha512-XBJbT3N4JhVumXE0eoLU9DCjcaF92KLNqTmFCnG1pf8duUxFGwtP6AD6nkjw9a3IdiRtL3E2w3JDiE/xi3vOeA==
+ dependencies:
+ emoji-regex "^8.0.0"
+ is-fullwidth-code-point "^3.0.0"
+ strip-ansi "^6.0.0"
+
string.prototype.trim@^1.2.4:
version "1.2.4"
resolved "https://registry.yarnpkg.com/string.prototype.trim/-/string.prototype.trim-1.2.4.tgz#6014689baf5efaf106ad031a5fa45157666ed1bd"
@@ -482,6 +573,13 @@ string_decoder@^1.1.1:
dependencies:
safe-buffer "~5.2.0"
+strip-ansi@^6.0.0:
+ version "6.0.0"
+ resolved "https://registry.yarnpkg.com/strip-ansi/-/strip-ansi-6.0.0.tgz#0b1571dd7669ccd4f3e06e14ef1eed26225ae532"
+ integrity sha512-AuvKTrTfQNYNIctbR1K/YGTR1756GycPsg7b9bdV9Duqur4gv6aKqHXah67Z8ImS7WEz5QVcOtlfW2rZEugt6w==
+ dependencies:
+ ansi-regex "^5.0.0"
+
tape@^5.2.2:
version "5.2.2"
resolved "https://registry.yarnpkg.com/tape/-/tape-5.2.2.tgz#a98475ecf30aa0ed2a89c36439bb9438d24d2184"
@@ -585,7 +683,39 @@ which-typed-array@^1.1.2:
has-symbols "^1.0.1"
is-typed-array "^1.1.3"
+wrap-ansi@^7.0.0:
+ version "7.0.0"
+ resolved "https://registry.yarnpkg.com/wrap-ansi/-/wrap-ansi-7.0.0.tgz#67e145cff510a6a6984bdf1152911d69d2eb9e43"
+ integrity sha512-YVGIj2kamLSTxw6NsZjoBxfSwsn0ycdesmc4p+Q21c5zPuZ1pl+NfxVdxPtdHvmNVOQ6XSYG4AUtyt/Fi7D16Q==
+ dependencies:
+ ansi-styles "^4.0.0"
+ string-width "^4.1.0"
+ strip-ansi "^6.0.0"
+
wrappy@1:
version "1.0.2"
resolved "https://registry.yarnpkg.com/wrappy/-/wrappy-1.0.2.tgz#b5243d8f3ec1aa35f1364605bc0d1036e30ab69f"
integrity sha1-tSQ9jz7BqjXxNkYFvA0QNuMKtp8=
+
+y18n@^5.0.5:
+ version "5.0.8"
+ resolved "https://registry.yarnpkg.com/y18n/-/y18n-5.0.8.tgz#7f4934d0f7ca8c56f95314939ddcd2dd91ce1d55"
+ integrity sha512-0pfFzegeDWJHJIAmTLRP2DwHjdF5s7jo9tuztdQxAhINCdvS+3nGINqPd00AphqJR/0LhANUS6/+7SCb98YOfA==
+
+yargs-parser@^20.2.2:
+ version "20.2.7"
+ resolved "https://registry.yarnpkg.com/yargs-parser/-/yargs-parser-20.2.7.tgz#61df85c113edfb5a7a4e36eb8aa60ef423cbc90a"
+ integrity sha512-FiNkvbeHzB/syOjIUxFDCnhSfzAL8R5vs40MgLFBorXACCOAEaWu0gRZl14vG8MR9AOJIZbmkjhusqBYZ3HTHw==
+
+yargs@^17.0.0:
+ version "17.0.0"
+ resolved "https://registry.yarnpkg.com/yargs/-/yargs-17.0.0.tgz#147db33e222e8e6a7829df5f2ae696b58d1c82bf"
+ integrity sha512-gbtedDPfBgG40iLbaRXhqYJycUYqFVZQLIxl1cG5Ez/xZL/47TetSYzPSIixkWa36GKHr9D/o/oSG1vHXF4zTw==
+ dependencies:
+ cliui "^7.0.2"
+ escalade "^3.1.1"
+ get-caller-file "^2.0.5"
+ require-directory "^2.1.1"
+ string-width "^4.2.0"
+ y18n "^5.0.5"
+ yargs-parser "^20.2.2"