diff options
author | Andrew Harvey <andrew@alantgeo.com.au> | 2021-05-04 14:50:52 +1000 |
---|---|---|
committer | Andrew Harvey <andrew@alantgeo.com.au> | 2021-05-04 14:50:52 +1000 |
commit | 5039b0dbf3af3b93466069927d794f5b1c8ccf81 (patch) | |
tree | 82f675877771b06da8cd4b82778c68b65d11cb91 | |
parent | 0e9a1861bac8b310c757a2c3fd92d67b50ebba12 (diff) |
add cluster library
-rw-r--r-- | .gitlab-ci.yml | 2 | ||||
-rw-r--r-- | cluster.js | 64 | ||||
-rw-r--r-- | package.json | 9 | ||||
-rw-r--r-- | test/cluster.js | 83 | ||||
-rw-r--r-- | yarn.lock | 130 |
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() +}) @@ -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" |