## Wednesday, June 14, 2006

First thing I started working on collisions between the straight skeleton bisectors (interior roof edges). Finding the place where two lines cross (in front of a pair of points) is easy, as is returning large values or null when the lines are , or almost are, parallel. The fun starts when the lines are coincident (on top of each other, so they are parallel as well). If the lines go in opposite directions they can't collide, but otherwise they might. If they are both going in the same direction one may catch up and overtake another, and if they are going towards each other then they meet somewhere in the middle. Where they meet is then just 'two trains leave moscow and prague at 12pm and 6pm...' type maths.

All this complication with speeds is because I'm trying for a weighted straight skeleton (which isn't documented anywhere except in Eppstein's paper). This means that the edges of the roof have different speeds. Does this mean I get to name it? If I do then it's a camp skeleton forevermore.

I implemented line-on-line collisions. Comming up with the following to simplify the problem of colliding co-incident lines and allowing the input shape to be non-planar(would be mega-cool):

Then I set up a queue to contain the collision events and had it return the event with the lowest height. Finally a bit of work on a graphical debugger finished it all off.