|
|
|
best route
Monday, September 7 2009
I worked on and off for most of the day on the "best route" system for my database mapper. The scope was straight forward: I had just two routes to pick between for drawing each relationship in a database. I just had to pick the best of these routes. But how? The best routes were the ones traversing across the fewest unrelated tables in the design, whatever it happened to be. So my "best route" algorithm had to add up the crossed unrelated tables and pick the route with the fewest of those to render visible. This problem is similar to a collision problem in an arcade game. Take an object with a known size and position, and then scan through other objects on the screen to see if it invades the space of any of those. My task was relatively easy since all my objects were rectangular in shape (or, as in the case of the relations, made up of extremely narrow rectangles).
I decided to call my object scanner (the code scanning through every table on the map looking to see if it was intercepted) from inside the routine drawing every leg of every relation. This meant that it would usually be called three or four times for each relation, since that is how many segments comprise most relations. I'd get a tally for crossed unrelated tables for each segment, add them together, compare for both routes, and then turn on the route with the least crossed unrelated tables. It was all very processor-intensive, but since it was all happening in Javascript, it didn't have any affect on the server. And it would only run slowly in maps with large numbers of tables. For those maps I included code to turn off the "best route" algorithm whenever the table number of a map crossed a certain threshold (though I found it worked fine even with 30 tables, at least on my Core-2 Duo machine).
For those who are curious (and I went through much grief figuring this out, particularly the offsetWidth/Height nonsense) the Javascript collision detector for two rectangular DIV objects ended up being this:
Later after thinking on the algorithm in the bathtub, I tweaked the object scanner code so that instead of passing back integer numbers of counts, it instead passed back arrays of the names of intercepted tables. This made it so I could concatenate the lists and eliminate duplicates to arrive at more accurate counts of crossed unmapped tables (particularly in cases where a bend in the relation happened over an unrelated table, where two legs of the relation had been each counting that table once). This change in accuracy didn't affect the actual behavior of the algorithm much, though it was more elegant and provided a more solid basis for future designs (such as those that select between more than two routes).
You can see the results of this effort in a map in the demo version of my visualizer. It's easier to experiment with in a more stripped-down map. There you can see the two relations going from the critter table over and up to the friendship_map table. If another table (say enemyship_map) were to be dragged into position over that bend in the relationship, the "best route" code would immediately select the alternative route. Of course, there are only two possible routes and if both are blocked the relation has to be drawn somewhere.
This evening Gretchen and I began re-watching season two of The Wire on DVD. I think my favorite character in season two is Ziggy (Jesus, he has his own Wikipedia entry!).
For linking purposes this article's URL is:
http://asecular.com/blog.php?090907 feedback
previous | next |
