Title: [BUG]: findEmpties throws "iterated with no new neighbors" for large NaN regions in contour (double-precision underflow) · Issue #8108 · plotly/plotly.js · GitHub
Open Graph Title: [BUG]: findEmpties throws "iterated with no new neighbors" for large NaN regions in contour (double-precision underflow) · Issue #8108 · plotly/plotly.js
X Title: [BUG]: findEmpties throws "iterated with no new neighbors" for large NaN regions in contour (double-precision underflow) · Issue #8108 · plotly/plotly.js
Description: Description findEmpties() (used by contour, heatmap with connectgaps, surface with connectgaps, and contourcarpet) throws findEmpties iterated with no new neighbors for large empty (NaN) regions, even though every empty cell is connected...
Open Graph Description: Description findEmpties() (used by contour, heatmap with connectgaps, surface with connectgaps, and contourcarpet) throws findEmpties iterated with no new neighbors for large empty (NaN) regions, e...
X Description: Description findEmpties() (used by contour, heatmap with connectgaps, surface with connectgaps, and contourcarpet) throws findEmpties iterated with no new neighbors for large empty (NaN) regions, e...
Opengraph URL: https://github.com/plotly/plotly.js/issues/8108
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"[BUG]: findEmpties throws \"iterated with no new neighbors\" for large NaN regions in contour (double-precision underflow)","articleBody":"### Description\n\n`findEmpties()` (used by `contour`, `heatmap` with `connectgaps`, `surface` with `connectgaps`, and\n`contourcarpet`) throws\n\n```\nfindEmpties iterated with no new neighbors\n```\n\nfor large empty (NaN) regions, **even though every empty cell is connected to real data**. The cause\nis a double-precision underflow of the internal \"fractional neighbour count\" weight, which the code\nthen misreads as \"this cell has no neighbours\".\n\nInside the flood-fill loop the weight is recomputed once per layer as\n\n```js\nneighborCount = ((neighborHash[[i - 1, j]] || blank)[2] +\n (neighborHash[[i + 1, j]] || blank)[2] +\n (neighborHash[[i, j - 1]] || blank)[2] +\n (neighborHash[[i, j + 1]] || blank)[2]) / 20; // src/traces/heatmap/find_empties.js, L70-L73\n\nif(neighborCount) { // L75: 0 is treated as \"no neighbour\"\n newNeighborHash[thisPt] = [i, j, neighborCount];\n noNeighborList.splice(p, 1);\n foundNewNeighbors = true;\n}\n```\n\nso the weight decays geometrically. With `n` already-filled neighbours per layer, after `k` layers\n`w ≈ w0 * (n / 20)^k`. Once `w` falls below `Number.MIN_VALUE` (≈ 4.94e-324, the smallest positive\ndouble) it becomes **exactly 0**, the `if(neighborCount)` guard fails, no cell is marked as filled in\nthat round, `foundNewNeighbors` stays `false`, and the function throws.\n\nThe number of layers until underflow is `324 / log10(20 / n)`:\n\n| already-filled neighbours per layer | layers until the weight becomes 0 | typical geometry |\n| --- | --- | --- |\n| 1 | **249** | a 1-cell-wide propagation channel |\n| 2 | 324 | diagonal / corner of a 2-D front |\n| 4 | 463 | interior of a 2-D island |\n\nNumeric evidence: `20 ** -248 === 1.9763e-323` (still representable) but `20 ** -249 === 0`\n(exactly zero, verified in Node/Chrome).\n\nSo the real limit is **the depth of contiguous empty cells along the propagation direction\n(roughly 250-330)**, not the amount of missing data and not connectivity. Note also that a *lot* of\nmissing data is fine as long as it is shallow:\n\n* a `5 x 251` grid whose column 0 is data and columns 1-250 are NaN (only 1250 empty cells) **throws**;\n* a `200 x 200` grid of data with a `100 x 100` NaN hole (10000 empty cells) renders fine.\n\n### Screenshots/Video\n\nConsole output for the reproducer below (plotly.js 3.7.0, unminified):\n\n```\nUncaught findEmpties iterated with no new neighbors\n```\n\nNote that the exception is thrown **synchronously** out of `Plotly.newPlot()`, so it is *not*\ndelivered as a promise rejection and cannot be handled with `.catch()`.\n\n### Steps to reproduce\n\nMinimal, no browser required (the function body is copied verbatim from\n`src/traces/heatmap/find_empties.js`; run with `node repro.js`):\n\n```js\n// NOTE: plotly passes z through clean2dArray, whose cleanZvalue() maps any non-numeric\n// value to undefined (`if(!isNumeric(v)) return undefined;`), so NaN reaches findEmpties\n// as undefined - that is what \"empty\" means here.\nvar maxRowLength = function(z) { var m = 0; for (var k = 0; k \u003c z.length; k++) if (z[k].length > m) m = z[k].length; return m; };\n\nfunction findEmpties(z) { /* exact copy of src/traces/heatmap/find_empties.js, see file above */ }\n\n// 5 rows, column 0 is data, columns 1..250 are empty -> THROWS\nfunction strip(rows, nanCount) {\n var z = [], r, i, j;\n for(i = 0; i \u003c rows; i++) { r = [1]; for(j = 0; j \u003c nanCount; j++) r.push(undefined); z.push(r); }\n return z;\n}\n\nfindEmpties(strip(5, 250)); // Uncaught findEmpties iterated with no new neighbors\nfindEmpties(strip(5, 249)); // fine - one column less\n```\n\nEnd-to-end in the browser / CodePen (also verified through `Plotly.newPlot` with jsdom against the\nreal 3.7.0 bundle - the same exception is thrown synchronously):\n\n```html\n\u003cscript src=\"https://cdn.plot.ly/plotly-3.7.0.js\">\u003c/script>\n\u003cdiv id=\"plot\" style=\"width:900px;height:400px\">\u003c/div>\n\u003cscript>\nvar z = [], i, j, row;\nfor(i = 0; i \u003c 5; i++) { row = [1]; for(j = 0; j \u003c 250; j++) row.push(NaN); z.push(row); }\n\n// throws synchronously; try/catch is required, .catch() on the promise is not enough\ntry {\n Plotly.newPlot('plot', [{ z: z, type: 'contour' }], {});\n} catch(e) {\n console.log(e); // findEmpties iterated with no new neighbors\n}\n\u003c/script>\n```\n\nCodePen: \u003chttps://codepen.io/.../pen/...> (see the attached example; button \"Case 1\" fails in \u003c 1 s,\n\"Case 2\" - a 325 x 325 grid whose only data are the centre 2 x 2 cells - fails after ~1 minute).\n\n### Suggested fix\n\nThe weight is only an ordering heuristic (see the file's own comment: *\"this is to give us an order\nof points to evaluate for interpolation\"*), so it must not affect control flow. Testing the **sum**\ninstead of the quotient, and clamping the underflowed quotient to `Number.MIN_VALUE`, is enough:\n\n```diff\n--- a/src/traces/heatmap/find_empties.js\n+++ b/src/traces/heatmap/find_empties.js\n@@\n- var neighborCount;\n+ var neighborCount;\n+ var neighborSum;\n@@\n- neighborCount = ((neighborHash[[i - 1, j]] || blank)[2] +\n+ neighborSum = (neighborHash[[i - 1, j]] || blank)[2] +\n (neighborHash[[i + 1, j]] || blank)[2] +\n (neighborHash[[i, j - 1]] || blank)[2] +\n- (neighborHash[[i, j + 1]] || blank)[2]) / 20;\n+ (neighborHash[[i, j + 1]] || blank)[2];\n+\n+ neighborCount = neighborSum / 20;\n \n- if(neighborCount) {\n+ if(neighborSum) {\n+ // neighborSum / 20 can underflow to 0 (once neighborSum \u003c= ~1e-323),\n+ // but this cell does have neighbours: keep a strictly positive weight\n+ if(!neighborCount) neighborCount = Number.MIN_VALUE;\n newNeighborHash[thisPt] = [i, j, neighborCount];\n noNeighborList.splice(p, 1);\n foundNewNeighbors = true;\n```\n\nMeasured with this patch applied to the shipping implementation:\n\n| input | unpatched | patched |\n| --- | --- | --- |\n| `5 x 251` strip (1250 empty) | throws | fills all 1250, ~0.6 s |\n| `5 x 250` strip (1245 empty) | fills 1245 | fills 1245 (unchanged) |\n| `324 x 324` centre island | fills 104972 | fills 104972 (unchanged) |\n| `325 x 325` centre island | throws after ~60 s | fills all 105621 |\n| `512 x 512` centre island | throws after ~134 s | fills all 262140 |\n| `200 x 200` with a `60 x 60` hole | fills 3600 | fills 3600 (unchanged) |\n\nThe returned list is still sorted by descending weight (verified monotonic non-increasing), and in\nthe `325 x 325` case only a single cell ends up clamped to `Number.MIN_VALUE`, so the interpolation\norder is not distorted. A regression test could be added next to the existing heatmap tests in\n`test/jasmine/tests/heatmap_test.js`.\n\nTwo further suggestions, happy to open PRs for either:\n\n1. Replace the weighted flood fill with a plain BFS over layer indices (`w = 1 / (1 + layer)`).\n This removes the underflow at the source *and* fixes the complexity: the current loop rescans\n every remaining empty cell on every round and uses string-keyed hash lookups plus\n `Array#splice` in the middle of a large array, so an input that *fails* can take minutes of\n wasted work first (measured ~60 s for a 325 x 325 grid and ~134 s for 512 x 512 on a desktop CPU).\n2. `throw 'findEmpties iterated with no new neighbors'` throws a **bare string**, so it cannot be\n identified with `instanceof Error`. If a hard failure is really the intent (e.g. all-NaN `z`),\n please throw an `Error` with a message that points at the missing data instead.\n\n### Notes\n\n* Affected traces: `contour` (findEmpties is called unconditionally), `heatmap` with\n `connectgaps: true`, `surface` (3D) with `connectgaps: true`, and `contourcarpet`.\n* There is no configuration that avoids this; `zsmooth`, `connectgaps: false` etc. only change\n whether the code path is reached, not whether it can throw.\n* Every empty cell in all reproducers above is 4-connected to real data, so the error message\n (\"iterated with no new neighbors\") is misleading - it suggests disconnected data where there is none.\n* `findEmpties` only sees `undefined` cells because `clean2dArray` converts NaN to `undefined`\n first; this is why a repro that calls the function directly with a `Float64Array` filled with\n `NaN` silently returns `[]`.\n\n### Examples\n\nCodePen Link:\n```\nhttps://codepen.io/Czhaowu/pen/myWBYEW\n```\n\u003cimg width=\"784\" height=\"82\" alt=\"Image\" src=\"https://github.com/user-attachments/assets/9b150f93-3ae4-4f4c-b7e6-1a59138ddce6\" />","author":{"url":"https://github.com/Czhaowu","@type":"Person","name":"Czhaowu"},"datePublished":"2026-10-04T09:43:07Z","url":"https://github.com/plotly/plotly.js/issues/8108"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:bd5fa393-acdd-7a94-e247-0ef0f6e2e742 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | DB3C:3C21B:2D4238F:39D63BF:6B01AB81 |
| html-safe-nonce | db80da9c1e37c309100884036302a0ac65ba07f027759fd6c89b4b26a209aaec |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJEQjNDOjNDMjFCOjJENDIzOEY6MzlENjNCRjo2QjAxQUI4MSIsInZpc2l0b3JfaWQiOiI2NTM4NzA1Nzg4NTc4NDA5MzQ1IiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | 815978cef1788f8319889d1c60f2c8c2bda15a07b58c268767e80de70a82a300 |
| hovercard-subject-tag | issue:5698089292 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/plotly/plotly.js/8108/issue_layout |
| twitter:image | https://opengraph.githubassets.com/eab1cfe250580336247c3acff62d79b874cb2fafe833a56a2988f9de0fb9fea7/plotly/plotly.js/issues/8108 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/eab1cfe250580336247c3acff62d79b874cb2fafe833a56a2988f9de0fb9fea7/plotly/plotly.js/issues/8108 |
| og:image:alt | Description findEmpties() (used by contour, heatmap with connectgaps, surface with connectgaps, and contourcarpet) throws findEmpties iterated with no new neighbors for large empty (NaN) regions, e... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | Czhaowu |
| hostname | github.com |
| expected-hostname | github.com |
| None | cc5dfdd32f62ebd3223cab3af3aa2b268d3605218237326a48a99d1efd89495c |
| turbo-cache-control | no-preview |
| go-import | github.com/plotly/plotly.js git https://github.com/plotly/plotly.js.git |
| octolytics-dimension-user_id | 5997976 |
| octolytics-dimension-user_login | plotly |
| octolytics-dimension-repository_id | 45646037 |
| octolytics-dimension-repository_nwo | plotly/plotly.js |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 45646037 |
| octolytics-dimension-repository_network_root_nwo | plotly/plotly.js |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 8c77c9e8439031ad54c75a250694842892f693e1 |
| ui-target | canary-2 |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width