Monday, June 26, 2006

Right, new week and fourth new start on the veronoi (curse that name) implementation and I'm a little fustrated to say the least, I have many cool ideas for this project, but little things keep eating up all my time. I have a feeling that this is how life is.

A tricky bulk of the voronoi code involves calling a routine that splits a cell (block) apart to make room for a new block. The routine has to return lots of thing about the state. It could be one monolithic lump of code, but I tried to split it up. The problem is the shared state (variables and return values) is huge. I ended up having a snapshot of the shared state (instanced return variables) as global values in the class, this works, but I'm not convinced there isn't a better way of doing it.

Another problem I stubled across was that because I only followed edges after a bisector, until an unkown cell was found I didn't create lines created in the unknown cell before the bisector was created.

The general algorithm (right) is then:
  • We add each point in turn. The first point owns the whole starting shape / "cell"
  • for each subsequent point we find the cell that it falls into, and that cells centre point.
  • We mark a start point at the start of the bisector of both points.
  • We remove everything on the new points side of the bisecors from the old points cell.
  • We then move onto the next cell (clockwise in my case) in which the bisector ends.
  • This is all well and good untill we meet an edge. Here we follow the painstakingly ( bug-ridden) list of edge pointers until we come across a cell we havn't already seen.
  • We traverse from the point we entered the new cell until we reach the cells bisector, then continue as above.
  • We repeat until we end up where we started.


  1. Hi Tom, well I have a very rough idea of what I think you're doing, and it looks...complex, to say the least. Good luck - I think you're being great about all this! - Christine

  2. This comment has been removed by a blog administrator.