I'm a bit confused, we don't have to update the distance inside the while loop?

Actually, the !(x0 >= 0 && x0 < width && y0 >= 0 && y0 < height) is also puzzling - doesn't that say we keep going as long as the coordinates are *outside* the image?

Oh wait, duh, that's the point: you keep trying as long as it's outside the image window

The (distance, nearest) map doesn't change when we do the walk. In some implementations you can compute both at the same time (ie compute the (distance, nearest) on each jump, but here I chose to compute the whole map as a raster in the dmap cell. As a consequence if the walk jumps outside the raster we are "lost"—so when that happens we just skip that jump.

Nice! As is tradition, I've tried optimizing it a bit ;) https://observablehq.com/d/b11a37073e21fa89

Thanks! I don't want to fix the data structure too soon, in particular I think taking averages is just one example of interpolation, and there could be more interesting stuff to make by accumulating the source information as a list of hits. (I was thinking a bitfield, or a map for each run, that could be returned by a worker.) https://blog.demofox.org/2020/07/11/interpolating-data-over-arbitrary-shapes-with-laplaces-equation-and-walk-on-spheres/ has a list of examples that I'd like this type of code to be able to reproduce. But I reckon that making it faster would help—wouldn't it be neat for example to color https://observablehq.com/@d3/draw-me with WoS at interactive speeds?

PS if you want to play here are two previous (unfinished/unpolished/unsatisfying) experiments: - delaunay edition https://observablehq.com/d/a00eda4879484d64 - polygon edition https://observablehq.com/d/5e18767f50cffceb

Yeah the inlining I did (which is pretty much the biggest perf difference) doesn't help with code readability. The thing is, all that small array allocation and destructuring was taking up so much time it was triggering the "frozen script?" pop-up in my Firefox so I think we better find *some* alternative to that. Maybe a class? JS engines are pretty good with prototypical objects, as long as you don't add fields dynamically after construction Thanks for the links!

Ah you mean it's… the way I wrote distanceToSegment([x, y], [[ax, ay], [bx, by]]) that slows things down on FF? (……a minute later……) there's a bug report for that! https://bugzilla.mozilla.org/show_bug.cgi?id=1165569 and a test! http://fischer-l.github.io/testes6.html

I think I have some ideas on how to do the draw-me notebook... in short: 1. whenever we finish drawing a line segment we update the distance map 2. assume the image is already pretty full, in which case most pixels will *not* shortest distances will *not* their shortest distance 3. in this case, we can use spatial binning (like a quad-tree) to quickly determine that we don't need updates for large areas (guess those are just your basic hit-detection optimization techniques, really, and someone better versed in those will probably come along and come up with something better :p) ... actually, now that I think about it, we should be able to do something like this with the line segments here as well: build a quad-tree of the line segments first, then test every pixel (which avoids brute-force testing each line segment *and* calculating the distance every time).

so, for FF I seem to get a large speed boost by switching to object assignement: function distanceToSegment({ 0: x, 1: y }, { 0: { 0: ax, 1: ay }, 1: { 0: bx, 1: by } }) but it's ugly and I'd rather go back to the usual function(x,y,ax,ay,bx,by).

Oof... at the same time, using a typed array as a poor man's struct is bug-prone as well (it took me ages to get the Linde-Buzo-Gray stippling notebook to work with that), not to mention a real pain to update later. Anyway, I'm searching google scholar for 2D hit detection papers (and weeding out the "line detection in images and point clouds" ones, which are admittedly really cool but kind of the opposite of our problem :p)

Something like https://www.redblobgames.com/articles/visibility/ ? You can also see it as the delaunay problem, with segments instead of points. Since we don't need infinitesimal precision (1 pixel is enough), we can sample the segments pixel by pixel (at most 300 pixels per segment), and Delaunator might still be fast enough. Intermediate solutions would sample less (eg every 4 px) and switch to the current function if the distance is < 4.

much faster innit? https://observablehq.com/d/6c34e1b506410991

@jobleonard - https://github.com/zandaqo/structurae might help with the handling of typed arrays. - Also, have you considered exploring spatial line indexing instead of drawing distance maps? - By the way, have you seen https://observablehq.com/@mourner/fast-distance-transform ? @fil Can you quantify the speed post, and do you have guesses about the underlying causes?

For the FF issue, I have no idea where it's coming from, but it's good to know especially when we're upgrading D3 to ES6 and might want to use this type of syntax. For the delaunay optimization I think it's a huge improvement both in theory and practice — about segments.length times faster, since the lookup is now essentially O(1) for almost all pixels.

@fil That optimization is 👌 @mootari I had missed that fast distance transform notebook! Thanks!

This is one of the most cubist sketches I've seen, Fil. Very cool!

WoS Draw me! https://observablehq.com/d/f2ea3d94e6a933be