Vladimir Agafonkin
5dedc6880c
simplify stack-based sorting
2025-12-08 00:58:36 +02:00
muendlein
34d7277eec
Switch to non recursive quicksort ( #70 )
...
* added test
* add Bentley-McIlroy 3-way partitioning
* switch to non recursive implementation
* fixed stack handling
* rename function
* escaped ts errors + enhanced performance
* remove escaped error
* additional performance enhancement
2025-12-08 00:56:17 +02:00
Volodymyr Agafonkin
6cef6f24df
pass item bbox to filterFn in search ( #68 )
2025-08-09 18:54:06 +03:00
Vladimir Agafonkin
511b50d050
upgrade dev deps
2025-08-09 14:33:50 +03:00
muendlein
1e87f4071d
Fix stack overflow for some degenerate data cases ( #65 )
...
* fix pivot selection
* add regression test
* fix linting
2025-05-18 23:37:55 +03:00
Vladimir Agafonkin
3a6f0f0cc5
upgrade dev deps, close #58
2025-03-10 13:56:25 +02:00
Vladimir Agafonkin
a737e6e151
upgrade deps, slightly simplify neighbors method
2025-02-04 11:09:37 +02:00
Vladimir Agafonkin
242845928e
upgrade dev deps, use ts-expect-error for now (ref #58 )
2025-01-10 20:33:39 +02:00
Vladimir Agafonkin
5729a98fac
switch to ESLint 9+, upgrade dev deps
2024-06-26 14:16:47 +03:00
Vladimir Agafonkin
2485486fd2
add maxX/maxY defaults to add for simpler point indexing, close #42
2024-01-29 13:21:15 +02:00
Kyle Barron
5d079a6b77
Accept byteOffset when creating an index from a buffer ( #55 )
...
* Support Uint8Array input
* extra space
* address comments
* commit test changes
* Update index.js
Co-authored-by: Volodymyr Agafonkin <agafonkin@gmail.com>
* Update index.js
Co-authored-by: Volodymyr Agafonkin <agafonkin@gmail.com>
* Update index.js
Co-authored-by: Volodymyr Agafonkin <agafonkin@gmail.com>
* Update index.js
Co-authored-by: Volodymyr Agafonkin <agafonkin@gmail.com>
* address comments
---------
Co-authored-by: Volodymyr Agafonkin <agafonkin@gmail.com>
2024-01-20 20:34:54 +02:00
Vladimir Agafonkin
370221743e
use label break to slightly simplify code
2023-04-21 11:58:59 +03:00
Vladimir Agafonkin
ce745eeafd
improve performance for small-radius knn queries
2023-04-21 11:58:24 +03:00
Volodymyr Agafonkin
eaca470fcc
Add JSDoc-based TypeScript checks + first-class types ( #47 )
...
* add JSDoc-based TypeScript checks + first-class types
* minot updates
* case conventions
* minor updates
* fixes
2023-04-21 11:55:12 +03:00
Vladimir Agafonkin
f3d24b3ba3
fix index.neighbors freezing with just x/y args
2023-04-19 19:11:15 +03:00
Jérôme Desboeufs
3e82ac6b91
Add SharedArrayBuffer support ( #46 )
...
* add SharedArrayBuffer support to Flatbush.from
* add an option to opt-in SharedArrayBuffer creation
* update README
* use global.SharedArrayBuffer to avoid exception and allow mocking
* ensure ArrayBufferType reflects data internal type
* add unit tests for SharedArrayBuffer support
* improve SharedArrayBuffer implementation
* update README
* remaining reference to useSharedArrayBuffer
* use duck-typing to check data is an ArrayBuffer-like
Co-authored-by: Volodymyr Agafonkin <agafonkin@gmail.com>
---------
Co-authored-by: Volodymyr Agafonkin <agafonkin@gmail.com>
2023-04-10 15:40:16 +03:00
Vladimir Agafonkin
4351cdec69
microoptimizations
2022-10-26 16:28:48 +03:00
Vladimir Agafonkin
a11b916c90
small cleanup
2022-03-30 10:18:54 +03:00
Vladimir Agafonkin
bcab4dd210
Switch to ESM-only entry point, drop transpiling and IE ( #40 )
...
* switch to ESM-only entry point
* readme updates
* clearer language
* try bigger API headings
* bring back smaller headings
* tiny cleanup
* replace broken bundlephobia badge with a static one
* adjust badge color
* readd rollup bundle for browser CDNs
* update cdn links
* cleanup
2022-03-29 23:11:48 +03:00
Vladimir Agafonkin
306fecfbef
avoid division by zero, close #34
2021-02-17 23:35:54 +02:00
Vladimir Agafonkin
6903d4b2c4
optimize knn search by using non-negative queue indices
2021-02-17 23:25:55 +02:00
Vladimir Agafonkin
7fd6d7b0c1
reintroduce upper bound routine in search
...
Possibly slightly faster (2–3%), and more consistent with kNN search.
2020-04-01 01:50:22 +03:00
Vladimir Agafonkin
d45c37837a
minor simplification
2020-04-01 01:40:10 +03:00
Jedidiah Buck McCready
755478c0d2
skip sorting when there is only one node ( #28 )
2020-03-31 11:17:28 +03:00
Vladimir Agafonkin
afc6213866
stop quicksort earlier for faster indexing ( #29 )
2020-03-31 01:13:26 +03:00
Lucio Paiva
8d5257f4f1
Explain what item indices are (and expose them) ( #26 )
...
* expose item index
* add unit test
2020-02-06 09:52:31 +02:00
Vladimir Agafonkin
f1c16d550d
slightly faster knn search
2018-11-08 14:58:25 +01:00
Vladimir Agafonkin
eb61250246
expand documentation
2018-10-10 13:35:28 +03:00
Vladimir Agafonkin
f87c6fbd1f
implement kNN queries
2018-10-10 11:30:40 +03:00
Vladimir Agafonkin
a5ffcdc445
clean up, modernize
2018-09-05 14:56:33 +03:00
Vladimir Agafonkin
40c08182b2
check ArrayType in constructor
2018-05-07 19:33:13 +03:00
Vladimir Agafonkin
b7b1eca826
add magic number + version to the header
2018-05-07 13:18:35 +03:00
Vladimir Agafonkin
45b00ece3b
simplify slightly
2018-05-07 11:34:47 +03:00
Vladimir Agafonkin
4267248414
add a header to the buffer; close #12
2018-05-07 11:34:34 +03:00
Vladimir Agafonkin
724fab44b8
simplify
2018-05-04 12:46:32 +03:00
Martin Raifer
0f7d35c366
we don't need an "alignment margin"; indices can't be larger than 32bit
...
as array indices can never be larger than 32 bit integers, the typed arrays always align correctly in the "data" array buffer (note that the boxes always come in multiples of four entries)
see https://github.com/mourner/flatbush/pull/11#discussion_r185742889
2018-05-04 10:35:37 +02:00
Martin Raifer
7ef566ef7e
fix alignment margin calculation
...
see https://github.com/mourner/flatbush/pull/11#discussion_r184096261
2018-04-25 17:08:22 +02:00
Martin Raifer
1075031900
decouple indices from coordinates
...
This allows to use an independent array type for indices (which are always unsigned integers for which the smallest fitting type is automatically chosen).
see https://github.com/mourner/flatbush/pull/4#issuecomment-383980084
2018-04-25 10:37:53 +02:00
Vladimir Agafonkin
ade1fdfbee
safeguard against infinite loop
2018-03-21 17:31:46 +02:00
Vladimir Agafonkin
6fabe76fcd
fix error reporting on search
2018-03-21 16:46:55 +02:00
Vladimir Agafonkin
8720096e89
remove binary search for level bound
...
slightly improves search performance, closes #6
2018-03-21 15:11:30 +02:00
Vladimir Agafonkin
5edf164ba2
optimize search queue
2018-03-21 14:19:37 +02:00
Vladimir Agafonkin
b90298988f
minor code cleanup
2018-03-21 14:18:15 +02:00
Vladimir Agafonkin
8492c77481
use rectangle centers instead of corners for packing
2018-03-21 13:43:13 +02:00
Vladimir Agafonkin
682036eb6a
accept array views for deserialization
2018-03-21 12:33:31 +02:00
Vladimir Agafonkin
a056d5567f
use let/const instead of var everywhere
2018-03-21 12:12:47 +02:00
Vladimir Agafonkin
6d283bdfaa
use class syntax
2018-03-21 12:02:35 +02:00
Vladimir Agafonkin
3bb64a7257
(breaking!) export class instead of factory
2018-03-21 12:01:00 +02:00
Vladimir Agafonkin
bf24351a75
expose minX, minY, maxX, maxY
2018-03-21 11:53:18 +02:00
Vladimir Agafonkin
ae2967afd9
expose numItems, nodeSize, ArrayType publicly
2018-03-21 11:47:13 +02:00
