Jason (jcreed) wrote,

I had some weird semi-dreamy ideations last night about directed graphs. So, obviously, I started playing with javascript and the HTML canvas widget this morning. Here's what I managed after spending most of today fiddling with it. The little blue circle tries its best to follow the mouse. That's it; there's no "winning" yet. I developed it on firefox, and while it technically seems to work on my version of chromium on linux, there's some progressive crappification that happens to the background image as the blue circle passes over it. A bug (or at least unintended behavior) of chrome's drawImage, maybe?

The tricky bit was implementing Delaunay triangulation in what is, I think, the second-most horrifyingly naive way possible. bhudson, you probably want to avert your eyes. I'm not directly using the circumcircle definition of Delaunay-ness, but the thing I did is still definitely O(n3). I believe optimal (based on cursory Wikipedia reading) is O(n lg n), so that's pretty obscene indeed.

And then I filter out some nodes that are too near each other, and those that are too collinear with each other, and assign edge-orientations in a recursive way that guarantees the whole graph is strongly-connected, and there you go.
Tags: graphs, javascript, toys

  • (no subject)

    Some further progress cleaning up the https://xkcd.com/1360/ -esque augean stables that is my hard drive. Tomato chicken I made a couple days ago…

  • (no subject)

    Did some personal archaeology. Helped a little with laundry. Threw some chicken, onions, tomato, stock, peppers in the slow cooker and hopefully…

  • (no subject)

    Dinner with akiva and dannel at nuevo portal in carroll gardens. Ate a pile of chicken stew and rice and beans and maduros, good times. I do miss…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded