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.