{"versions":{"1.2.0":{"name":"concaveman","version":"1.2.0","description":"Fast 2D concave hull algorithm in JavaScript (generates an outline of a point set)","main":"index.js","dependencies":{"point-in-polygon":"^1.0.1","rbush":"^3.0.0","robust-predicates":"^2.0.4","tinyqueue":"^2.0.3"},"devDependencies":{"eslint":"^7.0.0","eslint-config-mourner":"^2.0.1","tape":"^5.0.0"},"scripts":{"pretest":"eslint index.js test/*.js","test":"tape test/test.js"},"repository":{"type":"git","url":"git://github.com/mapbox/concaveman.git"},"keywords":["concave","hull","algorithm","geometry","shape","outline"],"eslintConfig":{"extends":"mourner"},"author":{"name":"Vladimir Agafonkin"},"license":"ISC","gitHead":"54838e1c9eb416f4393438df7e78ac2b0ca7faa5","bugs":{"url":"https://github.com/mapbox/concaveman/issues"},"homepage":"https://github.com/mapbox/concaveman#readme","_id":"concaveman@1.2.0","_nodeVersion":"10.20.1","_npmVersion":"6.14.4","dist":{"shasum":"4340f27c08a11bdc1d5fac13476862a2ab09b703","size":5548,"noattachment":false,"tarball":"http://123.232.10.234:8212/nexus/content/groups/npm-public/concaveman/-/concaveman-1.2.0.tgz"},"maintainers":[{"name":"anonymous","email":"accounts+npm-mapbox-machine-user@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-01@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-02@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-03@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-04@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-05@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-08@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-09@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-advanced-actions@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-npm-ci@mapbox.com"},{"name":"anonymous","email":"agafonkin@gmail.com"}],"_npmUser":{"name":"anonymous","email":"agafonkin@gmail.com"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/concaveman_1.2.0_1589794284325_0.6584958601906441"},"_hasShrinkwrap":false,"publish_time":1589794284463,"_cnpm_publish_time":1589794284463,"contributors":[]},"1.1.1":{"name":"concaveman","version":"1.1.1","description":"Fast 2D concave hull algorithm in JavaScript (generates an outline of a point set)","main":"index.js","dependencies":{"monotone-convex-hull-2d":"^1.0.1","point-in-polygon":"^1.0.1","rbush":"^2.0.1","robust-orientation":"^1.1.3","tinyqueue":"^1.1.0"},"devDependencies":{"eslint":"^3.6.0","eslint-config-mourner":"^2.0.1","tap":"^7.1.2"},"scripts":{"pretest":"eslint index.js test/*.js","test":"tap test/test.js"},"repository":{"type":"git","url":"git://github.com/mapbox/concaveman.git"},"keywords":["concave","hull","algorithm","geometry","shape","outline"],"eslintConfig":{"extends":"mourner"},"author":{"name":"Vladimir Agafonkin"},"license":"ISC","gitHead":"69a44b9b28aab0532e82c3a194a57a9a3b4fbfa0","bugs":{"url":"https://github.com/mapbox/concaveman/issues"},"homepage":"https://github.com/mapbox/concaveman#readme","_id":"concaveman@1.1.1","_shasum":"6c2482580b2523cef82fc2bec00a0415e6e68162","_from":".","_npmVersion":"3.10.7","_nodeVersion":"6.6.0","_npmUser":{"name":"anonymous","email":"agafonkin@gmail.com"},"dist":{"shasum":"6c2482580b2523cef82fc2bec00a0415e6e68162","size":5219,"noattachment":false,"tarball":"http://123.232.10.234:8212/nexus/content/groups/npm-public/concaveman/-/concaveman-1.1.1.tgz"},"maintainers":[{"name":"anonymous","email":"accounts+npm-mapbox-machine-user@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-01@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-02@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-03@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-04@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-05@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-08@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-09@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-advanced-actions@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-npm-ci@mapbox.com"},{"name":"anonymous","email":"agafonkin@gmail.com"}],"_npmOperationalInternal":{"host":"packages-16-east.internal.npmjs.com","tmp":"tmp/concaveman-1.1.1.tgz_1474896155750_0.11352050444111228"},"directories":{},"publish_time":1474896157133,"_cnpm_publish_time":1474896157133,"_hasShrinkwrap":false,"contributors":[]},"1.1.0":{"name":"concaveman","version":"1.1.0","description":"Fast 2D concave hull algorithm in JavaScript (generates an outline of a point set)","main":"index.js","dependencies":{"monotone-convex-hull-2d":"^1.0.1","point-in-polygon":"^1.0.0","rbush":"^1.4.2","robust-orientation":"^1.1.3","tinyqueue":"^1.0.1"},"devDependencies":{"eslint":"^1.10.3","eslint-config-mourner":"^1.0.1","tap":"^5.4.3"},"scripts":{"pretest":"eslint index.js test/*.js","test":"tap test/test.js"},"repository":{"type":"git","url":"git://github.com/mapbox/concaveman.git"},"keywords":["concave","hull","algorithm","geometry","shape","outline"],"eslintConfig":{"extends":"mourner"},"author":{"name":"Vladimir Agafonkin"},"license":"ISC","gitHead":"a539290022d8530b237e735a640801f9f07f9c8f","bugs":{"url":"https://github.com/mapbox/concaveman/issues"},"homepage":"https://github.com/mapbox/concaveman#readme","_id":"concaveman@1.1.0","_shasum":"3072395ec6facb0c64c2cecd4f30f26798be3dda","_from":".","_npmVersion":"3.6.0","_nodeVersion":"5.6.0","_npmUser":{"name":"anonymous","email":"agafonkin@gmail.com"},"dist":{"shasum":"3072395ec6facb0c64c2cecd4f30f26798be3dda","size":5138,"noattachment":false,"tarball":"http://123.232.10.234:8212/nexus/content/groups/npm-public/concaveman/-/concaveman-1.1.0.tgz"},"maintainers":[{"name":"anonymous","email":"accounts+npm-mapbox-machine-user@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-01@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-02@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-03@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-04@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-05@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-08@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-09@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-advanced-actions@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-npm-ci@mapbox.com"},{"name":"anonymous","email":"agafonkin@gmail.com"}],"_npmOperationalInternal":{"host":"packages-6-west.internal.npmjs.com","tmp":"tmp/concaveman-1.1.0.tgz_1455552644591_0.9769942772109061"},"directories":{},"publish_time":1455552648399,"_cnpm_publish_time":1455552648399,"_hasShrinkwrap":false,"contributors":[]},"1.0.0":{"name":"concaveman","version":"1.0.0","description":"Fast 2D concave hull algorithm in JavaScript (generates an outline of a point set)","main":"index.js","dependencies":{"monotone-convex-hull-2d":"^1.0.1","point-in-polygon":"^1.0.0","rbush":"^1.4.2","robust-orientation":"^1.1.3","tinyqueue":"^1.0.1"},"devDependencies":{"eslint":"^1.10.3","eslint-config-mourner":"^1.0.1","tap":"^5.4.3"},"scripts":{"pretest":"eslint index.js test/*.js","test":"tap test/test.js"},"keywords":["concave","hull","algorithm","geometry","shape","outline"],"eslintConfig":{"extends":"mourner"},"author":{"name":"Vladimir Agafonkin"},"license":"ISC","gitHead":"c49c7e191b6a86604010cd71ec89d78c8307a769","_id":"concaveman@1.0.0","_shasum":"f61f35bf0f50cf7964b6cfdd1523e8636f4aa7df","_from":".","_npmVersion":"2.14.17","_nodeVersion":"5.5.0","_npmUser":{"name":"anonymous","email":"agafonkin@gmail.com"},"dist":{"shasum":"f61f35bf0f50cf7964b6cfdd1523e8636f4aa7df","size":3465,"noattachment":false,"tarball":"http://123.232.10.234:8212/nexus/content/groups/npm-public/concaveman/-/concaveman-1.0.0.tgz"},"maintainers":[{"name":"anonymous","email":"accounts+npm-mapbox-machine-user@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-01@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-02@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-03@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-04@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-05@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-08@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-09@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-advanced-actions@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-npm-ci@mapbox.com"},{"name":"anonymous","email":"agafonkin@gmail.com"}],"_npmOperationalInternal":{"host":"packages-9-west.internal.npmjs.com","tmp":"tmp/concaveman-1.0.0.tgz_1455198471047_0.6993291596882045"},"directories":{},"publish_time":1455198474105,"_cnpm_publish_time":1455198474105,"_hasShrinkwrap":false,"contributors":[]},"1.2.1":{"name":"concaveman","version":"1.2.1","description":"","main":"index.js","dependencies":{"point-in-polygon":"^1.1.0","rbush":"^3.0.1","robust-predicates":"^2.0.4","tinyqueue":"^2.0.3"},"devDependencies":{"eslint":"^7.32.0","eslint-config-mourner":"^2.0.1","tape":"^5.3.1"},"scripts":{"pretest":"eslint index.js test/*.js","test":"tape test/test.js"},"repository":{"type":"git","url":"git://github.com/mapbox/concaveman.git"},"keywords":["concave","hull","algorithm","geometry","shape","outline"],"eslintConfig":{"extends":"mourner"},"author":{"name":"Vladimir Agafonkin"},"license":"ISC","gitHead":"f01d6e4b2c94e644a46e8113c6065aa0b4b79bc6","bugs":{"url":"https://github.com/mapbox/concaveman/issues"},"homepage":"https://github.com/mapbox/concaveman#readme","_id":"concaveman@1.2.1","_nodeVersion":"14.17.4","_npmVersion":"7.19.1","dist":{"shasum":"47d20b4521125c15fabf453653c2696d9ee41e0b","size":5591,"noattachment":false,"tarball":"http://123.232.10.234:8212/nexus/content/groups/npm-public/concaveman/-/concaveman-1.2.1.tgz"},"_npmUser":{"name":"anonymous","email":"agafonkin@gmail.com"},"directories":{},"maintainers":[{"name":"anonymous","email":"accounts+npm-mapbox-machine-user@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-01@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-02@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-03@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-04@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-08@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-09@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-npm-ci@mapbox.com"},{"name":"anonymous","email":"agafonkin@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/concaveman_1.2.1_1628502563120_0.8851149288155771"},"_hasShrinkwrap":false,"publish_time":1628502563353,"_cnpm_publish_time":1628502563353,"contributors":[]},"2.0.0":{"name":"concaveman","version":"2.0.0","description":"Fast 2D concave hull algorithm in JavaScript (generates an outline of a point set)","type":"module","main":"index.js","exports":"./index.js","dependencies":{"point-in-polygon":"^1.1.0","rbush":"^4.0.1","robust-predicates":"^3.0.2","tinyqueue":"^3.0.0"},"devDependencies":{"eslint":"^9.31.0","eslint-config-mourner":"^4.0.2"},"scripts":{"pretest":"eslint index.js test/*.js","test":"node test/test.js"},"repository":{"type":"git","url":"git://github.com/mapbox/concaveman.git"},"keywords":["concave","hull","algorithm","geometry","shape","outline"],"eslintConfig":{"extends":"mourner"},"author":{"name":"Vladimir Agafonkin"},"license":"ISC","_id":"concaveman@2.0.0","gitHead":"0b8e77d5b6ceb56f6f49446cb1cdd298cf54e38b","bugs":{"url":"https://github.com/mapbox/concaveman/issues"},"homepage":"https://github.com/mapbox/concaveman#readme","_nodeVersion":"20.15.1","_npmVersion":"11.3.0","dist":{"integrity":"sha512-3a9C//4G44/boNehBPZMRh8XxrwBvTXlhENUim+GMm207WoDie/Vq89U5lkhLn3kKA+vxwmwfdQPWIRwjQWoLA==","shasum":"5c4cea7e2329addf619ecae627cb721df05d1eac","tarball":"http://123.232.10.234:8212/nexus/content/groups/npm-public/concaveman/-/concaveman-2.0.0.tgz","fileCount":4,"unpackedSize":14832,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEUCIEaikNUVMv0RK7SuZX+eHZ291LW8XeA4PjvcT+boamCPAiEA3i/uZcfnoyWH8FgGIyJLyF5GAoTPDE1T3Yiz2NI7cy8="}],"size":5456},"_npmUser":{"name":"anonymous","email":"yannick.meeus+npm+prod+03@mapbox.com"},"directories":{},"maintainers":[{"name":"anonymous","email":"accounts+npmjs-01@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-02@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-07@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-03@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-04@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-09@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-05@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-06@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-08@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-advanced-actions@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs-npm-ci@mapbox.com"},{"name":"anonymous","email":"accounts+npmjs@mapbox.com"},{"name":"anonymous","email":"accounts@mapbox.com"},{"name":"anonymous","email":"accounts+npm-mapbox-machine-user@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+staging+ci@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+production+ci@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+01@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+02@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+03@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+04@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+05@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+06@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+07@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+08@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+09@mapbox.com"},{"name":"anonymous","email":"yannick.meeus@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+staging+advanced+actions@mapbox.com"},{"name":"anonymous","email":"yannick.meeus+npm+prod+advanced+actions@mapbox.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/concaveman_2.0.0_1752676149810_0.566982273905289"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-07-16T14:29:09.989Z","publish_time":1752676149989,"_source_registry_name":"default","contributors":[]}},"dist-tags":{"latest":"2.0.0"},"name":"concaveman","time":{"modified":"2025-07-16T14:29:25.597Z","created":"2022-01-27T15:11:16.338Z","1.2.0":"2020-05-18T09:31:24.463Z","1.1.1":"2016-09-26T13:22:37.133Z","1.1.0":"2016-02-15T16:10:48.399Z","1.0.0":"2016-02-11T13:47:54.105Z","1.2.1":"2021-08-09T09:49:23.353Z","2.0.0":"2025-07-16T14:29:09.989Z"},"readme":"## concaveman\n\nA very fast **2D concave hull** algorithm in JavaScript (generates a general outline of a point set).\n\n[![Build Status](https://travis-ci.org/mapbox/concaveman.svg?branch=master)](https://travis-ci.org/mapbox/concaveman)\n[![Coverage Status](https://coveralls.io/repos/github/mapbox/concaveman/badge.svg?branch=master)](https://coveralls.io/github/mapbox/concaveman?branch=master)\n[![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)\n\n<img width=\"570\" alt=\"sample concave hull\" src=\"https://cloud.githubusercontent.com/assets/25395/12975726/ada2ad10-d0c6-11e5-96c8-6e42c995e0e2.png\">\n\n### Usage\n\n```js\nimport concaveman from 'concaveman';\n\nconst points = [[10, 20], [30, 12.5], ...];\nconst polygon = concaveman(points);\n```\n\nSignature: `concaveman(points[, concavity = 2, lengthThreshold = 0])`\n\n- `points` is an array of `[x, y]` points.\n- `concavity` is a relative measure of concavity. `1` results in a relatively detailed shape, `Infinity` results in a convex hull.\nYou can use values lower than `1`, but they can produce pretty crazy shapes.\n- `lengthThreshold`: when a segment length is under this threshold, it stops being considered for further detalization.\nHigher values result in simpler shapes.\n\n### Algorithm\n\nThe algorithm is based on ideas from the paper [A New Concave Hull Algorithm and Concaveness Measure\nfor n-dimensional Datasets, 2012](https://jise.iis.sinica.edu.tw/JISESearch/fullText?pId=245&code=5A9B97538372AA1)\nby Jin-Seo Park and Se-Jong Oh.\n\nThis implementation dramatically improves performance over the one stated in the paper\n(`O(rn)`, where `r` is a number of output points, to `O(n log n)`)\nby introducing a fast _k nearest points to a segment_ algorithm,\na modification of a depth-first kNN R-tree search using a priority queue.\n\n### TypeScript\n\n[TypeScript type definitions](https://github.com/DefinitelyTyped/DefinitelyTyped/tree/master/types/concaveman)\nare available through `npm install --save @types/concaveman`.\n\n### Dependencies\n\n- [rbush](https://github.com/mourner/rbush) for point indexing\n- [tinyqueue](https://github.com/mourner/tinyqueue) as a priority queue\n- [point-in-polygon](https://github.com/substack/point-in-polygon) for point in polygon queries\n- [robust-predicates](https://github.com/mourner/robust-predicates) for 3-point orientation tests\n\n### C++ Port\n\nIn 2019, a [C++ port](https://github.com/sadaszewski/concaveman-cpp) has been created, allowing for efficient usage from C/C++, Python (via cffi) and other languages featuring an FFI and/or plug-in mechanism for C (e.g. a MATLAB MEX file should be easy to prepare).","users":{}}