{"_id":"@delusional/midpoint-proximity","_rev":"9-ce38f1378e70ab43117d3df2e0f03be2","name":"@delusional/midpoint-proximity","dist-tags":{"latest":"0.1.8"},"versions":{"0.1.0":{"name":"@delusional/midpoint-proximity","version":"0.1.0","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.0","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"0cbc8be6cf6410e190f9dbc70a1c0dbaa1a402a8","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.0.tgz","fileCount":5,"integrity":"sha512-/8snrY4i+y+5DcTrtkWP0M1Izn+HRJ4cu03oyLXIp4qjCTC5DQxnrhl4VkmjG7Tv0uXF59xBBKBmPXYp2bUHJA==","signatures":[{"sig":"MEUCIEpOUBcIij4HLowYKCKwV0TOTwMaueVMyFd0tlPVaRhtAiEAsP0LYSl7iHbPt1ZiNv01BbRLsDXo40hfnYd24yt9xP0=","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":179689},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.0_1773709172849_0.455031461333403","host":"s3://npm-registry-packages-npm-production"}},"0.1.1":{"name":"@delusional/midpoint-proximity","version":"0.1.1","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.1","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"5fb423ae3ef87347b32f4fa984f67b0c2cbf112a","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.1.tgz","fileCount":6,"integrity":"sha512-Yz3pjSgyePnvxWU/oDP/MhcCS5OX+vf3qQbcAFhORPsiXuDKB9DZ/qR7Y7n9XqQddUjUkGvYtcxrGGVkbPFgfw==","signatures":[{"sig":"MEQCIFRopcTj7dKftPns+NYAaXIKl55KHIzKISA0OW81xMZRAiBHYeX5oyYrVn2pKUw/pvlRcQJP/J6M4wVOdOcVtcI4BQ==","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":184253},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.1_1773709847843_0.22702329130121868","host":"s3://npm-registry-packages-npm-production"}},"0.1.2":{"name":"@delusional/midpoint-proximity","version":"0.1.2","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.2","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"19f843b4de718dd2a4abb48054f3ffb0f8962fe1","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.2.tgz","fileCount":6,"integrity":"sha512-F4IH3sKleEQ8jEnjX+QIfwjKTEpHC0vdLR58xzJTod2RvFjpiUolp/qC+ZM7Jw1bfukU3wNCO3RCvn4ALIHTcw==","signatures":[{"sig":"MEUCIDjtto985p/Hvi4PEQnwteHb32jlErCfBO6wdnJL5ElVAiEAt43ubabtKm32mmdTUskrMv2s5FaKZubDk+b51x/vbBI=","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":175621},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.2_1776343242724_0.4315353287521726","host":"s3://npm-registry-packages-npm-production"}},"0.1.3":{"name":"@delusional/midpoint-proximity","version":"0.1.3","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.3","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"b6e8e8957f47df4c797cb381d6cb2783e90cc19b","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.3.tgz","fileCount":6,"integrity":"sha512-VU3vu3wEOw+Q8O1Fd9sHHPaRGrLCFeCWJe3pDkNKwR/U+1r4x/UJI6JUuuTr+ICK9kI1XUkvODD1iDiue3Mm4A==","signatures":[{"sig":"MEYCIQC3x/YvmEbqviEcAhn8qE8pIxoXwZRdUCq4fCV1pbKDjQIhAJGUp+It0ArGzdH+ZS9WTNR7VrNkZVwGkMRBhn7Aps7q","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":175637},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.3_1776351106996_0.4535769150547819","host":"s3://npm-registry-packages-npm-production"}},"0.1.4":{"name":"@delusional/midpoint-proximity","version":"0.1.4","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.4","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"1712373d857b448c34a94386004a8edefe1f1fa3","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.4.tgz","fileCount":6,"integrity":"sha512-fZ0lKFQWCh8MauCO6EAIWDOLctEISZC9mkLPOeyTXEXYptRas+WfaqK/KUE0Tz9cd+nDK50sl98lFUaaiyyrGg==","signatures":[{"sig":"MEUCIQD0EcALYA7qDtLvDGhVN7bhYWO1GibGRT9+O8QpTkSKHAIgLtIerv/mLveuz1OD5B+1I9gtCvdxeZD2lUvJ2o0x5os=","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":179043},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.4_1776352312695_0.15892349590311383","host":"s3://npm-registry-packages-npm-production"}},"0.1.5":{"name":"@delusional/midpoint-proximity","version":"0.1.5","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.5","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"29955848b683aae7a81c22b22ab1c3557b1d389f","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.5.tgz","fileCount":6,"integrity":"sha512-TnsETDoxPGthp45Iue1CKVYE1fL+N2JcKXUxCkSGKUt7SzUOislswsnucFsfmarJ/mIm8dziK51YX21QKl7y3Q==","signatures":[{"sig":"MEUCIQCRKfFAbPCHxgcxDuilN6d4XdE8WIL48L5pPz0PEnT0XQIgWu7oMLEloTPeUtXeAAiYJ/Dj5WLpuwtn+fDUH93Tc0w=","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":179066},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.5_1776353636296_0.3203307465755796","host":"s3://npm-registry-packages-npm-production"}},"0.1.6":{"name":"@delusional/midpoint-proximity","version":"0.1.6","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.6","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"e0bed42f8b112726f7f21285eca4991df09a4532","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.6.tgz","fileCount":6,"integrity":"sha512-YyDjDSz4pBGJK5l/xHZ2Etzb1jtSERDN22HKygnIhJHXoYWd9RScYkkOXWrcZ7BUn62oyJO/QRt66bjzTa84mA==","signatures":[{"sig":"MEQCIEre5rXkYrI0Ff+2XNeNpXw1pKsLXsjXS67N0UlHuAr2AiBmnztnUtT6kbOCv/6C7Ln3LekFFJSq9MW74ReSz/RByw==","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":179054},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.6_1776354247129_0.28996280323556345","host":"s3://npm-registry-packages-npm-production"}},"0.1.7":{"name":"@delusional/midpoint-proximity","version":"0.1.7","license":"MIT","_id":"@delusional/midpoint-proximity@0.1.7","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"dist":{"shasum":"aecfe6be72ebd04cdde58f7138ec51b26b510fc3","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.7.tgz","fileCount":6,"integrity":"sha512-0HELW18ntvi5jPwSTUwOs5s9xmId72w5aDFRR8XJAOdsb0kZrbsN5OvDuO3oAxkQHLzuqBTZyjmHRjLh6Pg7qA==","signatures":[{"sig":"MEUCIQDImLg6zmg0oqryx3e9zbuRaZ+aQFptrjCUzDwqcKRiGwIgbOMmEupe88nrpMnC2YFyFfsZcVq28DB31NXR+mwcuw0=","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":179111},"main":"delusional_geo_midpoint_proximity.js","type":"module","types":"delusional_geo_midpoint_proximity.d.ts","gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"_npmVersion":"11.9.0","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","directories":{},"sideEffects":["./snippets/*"],"_nodeVersion":"24.13.0","_hasShrinkwrap":false,"_npmOperationalInternal":{"tmp":"tmp/midpoint-proximity_0.1.7_1776355568891_0.40609930351293966","host":"s3://npm-registry-packages-npm-production"}},"0.1.8":{"name":"@delusional/midpoint-proximity","type":"module","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","version":"0.1.8","license":"MIT","main":"delusional_geo_midpoint_proximity.js","types":"delusional_geo_midpoint_proximity.d.ts","sideEffects":["./snippets/*"],"gitHead":"a1c9365ca7ea09cd9306d0208a4285323a0f2a3d","_id":"@delusional/midpoint-proximity@0.1.8","_nodeVersion":"24.13.0","_npmVersion":"11.9.0","dist":{"integrity":"sha512-otLRHE01f3yQXdFI7lxlBd9LdNDGUDKPpHGSHkVBBlMGvAjVFj9H6sP3lesJO5dZwDWjYb17MCZa6wNwZr/BeQ==","shasum":"222884ed622e7da073d85c9b74a93545f4f877a1","tarball":"https://registry.npmjs.org/@delusional/midpoint-proximity/-/midpoint-proximity-0.1.8.tgz","fileCount":6,"unpackedSize":179014,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEYCIQD+60M0UZYhnLTXWHJXhwY+au9cTOj89Q77u0TpBuEroAIhAPAP47MnRmMQ7Y9RGGSnITyvAHxVy9UT++E3tPZHrzCf"}]},"_npmUser":{"name":"odder","email":"oscarrothandersen@gmail.com"},"directories":{},"maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/midpoint-proximity_0.1.8_1778436415687_0.5058529933805138"},"_hasShrinkwrap":false}},"time":{"created":"2026-03-17T00:59:32.710Z","modified":"2026-05-10T18:06:55.995Z","0.1.0":"2026-03-17T00:59:33.010Z","0.1.1":"2026-03-17T01:10:47.999Z","0.1.2":"2026-04-16T12:40:42.861Z","0.1.3":"2026-04-16T14:51:47.160Z","0.1.4":"2026-04-16T15:11:52.836Z","0.1.5":"2026-04-16T15:33:56.435Z","0.1.6":"2026-04-16T15:44:07.292Z","0.1.7":"2026-04-16T16:06:09.060Z","0.1.8":"2026-05-10T18:06:55.851Z"},"license":"MIT","description":"Hyper-optimised midpoint proximity ranking for point pairs on a spherical surface","maintainers":[{"name":"odder","email":"oscarrothandersen@gmail.com"}],"readme":"# @delusional/midpoint-proximity\n\nGiven two lists of geographic points (A and B) and a target, find the (A, B) pairs whose\ngeographic midpoint is closest to the target. The brute-force approach checks all `|A| x |B|`\npairs — this crate uses a spatial index to avoid that quadratic blowup.\n\n## Installation\n\n```bash\nnpm install @delusional/midpoint-proximity\n```\n\n## Usage\n\n```ts\nimport init, {\n  initThreadPool,\n  find_top_midpoints,\n  find_best_pair,\n  compute_all_midpoints,\n} from \"@delusional/midpoint-proximity\";\n\nawait init();\nawait initThreadPool(navigator.hardwareConcurrency);\n\n// Flat [lat, lng, lat, lng, ...] in degrees\nconst pointsA = new Float64Array([51.5074, -0.1278, 48.8566, 2.3522]);\nconst pointsB = new Float64Array([40.7128, -74.0060, 35.6762, 139.6503]);\n\n// Top 5 pairs whose midpoint is closest to (50°N, 0°E), no minimum endpoint distance\nconst results = find_top_midpoints(pointsA, pointsB, 50.0, 0.0, 5, 0.0);\n// Float64Array: [mid_lat, mid_lng, dist_to_target_km, idx_a, idx_b, dist_ab_km, ...]\n//               (6 values per result, sorted closest-first)\n\n// Single best pair\nconst best = find_best_pair(pointsA, pointsB, 50.0, 0.0, 0.0);\n// Float64Array: [mid_lat, mid_lng, dist_to_target_km, idx_a, idx_b, dist_ab_km]\n\n// All midpoints (no target, no ranking)\nconst all = compute_all_midpoints(pointsA, pointsB);\n// Float64Array: [mid_lat, mid_lng, idx_a, idx_b, dist_ab_km, ...]\n//               (5 values per pair)\n```\n\n**Note:** `initThreadPool` requires `SharedArrayBuffer`, which needs these response headers:\n```\nCross-Origin-Opener-Policy: same-origin\nCross-Origin-Embedder-Policy: require-corp\n```\n\n**A should be the smaller set** — see Quick overview below for why.\n\n## Quick overview\n\nThe algorithm builds a spatial index on B, then loops over every A point. For each A, it\ncomputes where the ideal B partner would be (the \"reflection point\"), searches the index\nnear that location, and scores a small candidate set instead of all of B.\n\n**A should be the smaller set.** The outer loop iterates over A, and the index absorbs\nthe size of B. Building the index is O(|B|) — done once. Each A point queries it in O(C)\nwhere C is a small constant (256-4096 candidates). So total work is O(|B| + |A| x C).\nPutting the smaller list as A minimises the number of loop iterations, which is where\nthe per-point work (reflection, grid lookup, flood-fill, scoring) happens.\n\n![architectural diagram](img.png)\n\nThree public functions:\n- **`find_top_midpoints`** — the sub-quadratic indexed search (main entry point)\n- **`find_best_pair`** — optimised wrapper for N=1\n- **`compute_all_midpoints`** — brute-force all pairs (no target, no ranking)\n\n## Key insights\n\n### The reflection trick\n\nFor a given A point, which B point would produce a midpoint exactly on the target? The\ngeographic midpoint of two unit vectors a and b is `normalize(a + b)`. For this to equal\nthe target t, we need `a + b` parallel to t, which gives us `b* = 2(a . t)t - a`.\n\nThis b\\* is the **reflection** of a about the target axis. Instead of checking all B\npoints, we search the grid in a small neighbourhood around b\\*. This turns the search\nfrom O(|B|) per A to O(C) where C is typically 256-4096 candidates.\n\n### The octahedral grid\n\nB points are projected onto the unit sphere and then onto a 2D square using the\n**octahedral equal-area projection**. This projection unfolds the sphere onto the faces\nof an octahedron, giving roughly uniform cell sizes (unlike equirectangular, which\nbunches cells at the poles).\n\nThe 2D square is divided into a `res x res` grid (256, 512, or 1024 depending on |B|).\nEach B point lands in one cell. The grid uses a **dense offset array** (CSR format —\nCompressed Sparse Row) so looking up which B points are in cell (u, v) is a direct\narray index — O(1), no binary search.\n\nThree grids are built with different axis permutations (XYZ, YZX, ZXY). Each permutation\nputs a different axis as the \"primary\" axis, so cells near that axis have the best\nresolution. For any query direction, we **pick the single best table** — the one where\nthe query direction is closest to the primary axis — giving the tightest candidate set\nwithout redundant work.\n\n### The flood-fill\n\nOnce we know which cell b\\* lands in, we need to find all nearby cells that could contain\npromising B points. The algorithm:\n\n1. **Center cell**: always included.\n2. **Four axis spines**: walk north/south/east/west from the center. For each cell,\n   check if a midpoint formed from that cell's center could beat the current threshold.\n   Stop when it can't. Uses **SIMD f32x4** to test 4 consecutive cells per instruction.\n3. **Four quadrant sweeps**: fill in the diagonal regions bounded by the spines. Each\n   quadrant sweeps column-by-column, and the column height monotonically decreases\n   (convexity of the threshold boundary). Every cell is visited exactly once — no visited\n   bitset needed.\n\nThe threshold check is: \"if I placed A's partner at this cell's center, would the\nresulting midpoint be closer to the target than my current N-th best result?\" This is\ncomputed as `dot^2 > threshold * len_sq` — multiplications only, no division.\n\n### The ranking metric\n\nThe true geodesic distance requires `asin` and `sqrt`, which are expensive. Instead, we\nrank by `-(dot * |dot|) / |mid|^2` where `dot = midpoint . target` and `|mid|^2` is the\nsquared length of the unnormalised midpoint. This is **monotonic** with geodesic distance —\nit gives the exact same ranking but uses only multiplies and one division (and the division\nonly happens for candidates that pass the threshold check).\n\n### Why single-table selection works\n\nThe octahedral projection stretches cells near the \"equator\" of each permutation's primary\naxis. Three tables (XYZ, YZX, ZXY) guarantee that for any direction, at least one table\nhas tight cells. But querying all three tables triples the work for little benefit — the\nbest table already gives a tight candidate set. Selecting the best table per query reduces\ngather time significantly.\n\nThe selection is trivial: compare which component of b\\* is largest in absolute value, and\npick the table whose primary axis matches. Three comparisons, O(1).\n\n## Implementation details\n\n### Memory layout\n\nB point coordinates are stored in **Structure of Arrays** (SoA) format: separate `Vec<f32>`\nfor x, y, and z. This means consecutive cells along the v-axis have their x-coordinates\ncontiguous in memory, then y-coordinates contiguous, etc. The SIMD flood-fill exploits\nthis — `f32x4::from_slice` loads 4 consecutive cell centers with a single instruction,\nno gather needed.\n\nCell offsets are a dense `Vec<u32>` of size `res*res + 1`. Cell `(u, v)` contains B\nindices `indices[cell_offsets[u*res+v] .. cell_offsets[u*res+v+1]]`. Empty cells have\nequal consecutive offsets. This is the standard CSR (Compressed Sparse Row) format used\nin sparse matrices.\n\nMemory cost at res=512: ~1 MB for cell offsets + ~3 MB for cell centers = ~4 MB per table.\n\n### Parallelism\n\nThe outer loop over A points is parallelised with Rayon. Each thread maintains:\n- A local results buffer (top-N candidates found so far)\n- A local pruning threshold (tightens as better results are found)\n- A reusable scratch buffer for candidates\n\nWhen a thread's buffer exceeds a size limit, it runs `select_nth_unstable` to compact\ndown to the top-N and updates its threshold. This batched compaction amortises the O(n)\nselection cost across many insertions.\n\nAfter all threads finish, results are merged with a reduce step that keeps the global\ntop-N.\n\n### Target-neighbor safety net\n\nWhen `a . t <= 0` (A is on the opposite hemisphere from the target), the reflection b\\*\npoints away from the target. The flood-fill near b\\* might miss B points that are\nactually near the target. To handle this, we pre-gather a set of B points near the target\ndirection and merge them into each A's candidate set.\n\nThis merge is **conditionally skipped** per A point when the pruning threshold is tight\nenough. The best possible metric from a target neighbor is approximately `-(a.t + 1) / 2`.\nWhen this can't beat the current threshold, the merge is skipped entirely — saving work\nfor the majority of A points once early iterations have established good results.\n\n### SIMD details\n\nThe crate uses Rust's `portable_simd` (`#![feature(portable_simd)]`) which compiles to\nWASM SIMD128 instructions when targeting `wasm32-unknown-unknown` with\n`-C target-feature=+simd128`.\n\nThe threshold check on a cell center is:\n```\nmx = ax + cell_center_x\nmy = ay + cell_center_y\nmz = az + cell_center_z\ndot = mx*tx + my*ty + mz*tz\nlen_sq = mx*mx + my*my + mz*mz\npasses = dot*dot > threshold * len_sq\n```\n\nWith f32x4, this tests 4 cells in ~12 SIMD instructions. North/south spines use\ncontiguous `f32x4::from_slice` loads (cells along v are contiguous). East/west spines\nuse `f32x4::from_array` with manual gather (stride = res).\n\n### Index construction\n\nBuilding the grid is O(|B|) per table:\n1. Compute each B point's cell index via octahedral projection — O(|B|)\n2. Count points per cell — O(|B|)\n3. Prefix sum to build the dense offset array — O(res^2)\n4. Scatter B indices into position — O(|B|)\n5. Precompute cell-center unit vectors — O(res^2)\n\nNo sorting is needed. The prefix-sum + scatter pattern is the standard CSR construction\nused in sparse matrix libraries.\n\n### Grid resolution\n\n| B size | Resolution | Cells | Cell offsets | Cell centers |\n|--------|-----------|-------|-------------|-------------|\n| < 50K | 256 | 65K | 256 KB | 768 KB |\n| 50K-500K | 512 | 262K | 1 MB | 3 MB |\n| > 500K | 1024 | 1M | 4 MB | 12 MB |\n\n## Complexity\n\n| Function | Time | Space |\n|----------|------|-------|\n| `find_top_midpoints` | O(\\|B\\| + \\|A\\| · C + k log k) | O(\\|B\\|) index + O(k) per thread |\n| `find_best_pair` | O(\\|B\\| + \\|A\\| · C) | O(\\|B\\|) index |\n| `compute_all_midpoints` | O(\\|A\\| · \\|B\\|) | O(\\|A\\| · \\|B\\|) |\n\nWhere C is the per-A candidate count (typically 256–4096, controlled by grid resolution\nand pruning threshold), and k = top_n. Candidate selection uses `select_nth_unstable`\n(introselect, O(n)) with batched compaction. The final k winners are sorted in O(k log k).\nIndex construction is O(|B|) per table (3 tables). The outer loop over A is parallelised\nwith Rayon. `compute_all_midpoints` is the brute-force baseline with no indexing —\nquadratic in both time and space.\n","readmeFilename":"README.md"}