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)

    Didn't sleep well. Long day of work. Dinner with akiva at hanamichi.

  • (no subject)

    K was going to do a thing for her dad's birthday, but scheduling kept slipping and slipping so I guess we're going to try doing it tomorrow instead.

  • (no subject)

    Had a pleasant lunch with paul and gabe back from working-at-facebook times. Discussed the important issues of the day, by which I mean video games…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded