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

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded