Thursday, June 29, 2006

Right! Got the voronoi working up to 300 cells (blocks) without crashing, and then some very subtle bug creeps in... watch this space.

Here it is working on a tricky case - the blue is the output lines (roads), the red shows line ownership (which block a road is adjacent too) and the green line show cells (which roads make a block). Its in perspective so some of the lines dont meet up. You can appreciate how each cell is cut out of the existing mesh. This mean that its O(n^2) in time complexity (there are some O(n log(n)) algorithms):

This Voronoi implementation overran by a week . My maths and abstract thinking haven't seen daylight since my A levels - the only maths Ive done at bristol is to repeat a prescribed algorithm in graphics. The problem is that to teach computer science Bristol would need to fire most of its lecturers(not really, they're all researchers) and hire teachers and assistants like they do in UCSC. There's no way you can teach the kind of computer science you need to build the next silicon valley with class sizes of 100+ and no tutorials. Bristol labs don't count (the people wearing yellow t shirts are branded lab-monkeys for a reason).

Ranting aside, I have a plan! If I:
  • change the Voronoi to allow points to be weighted (mesh should still be valid) - 10 minute change
  • allow the input shape to be concave - just have to locate one of several bisector inside a shape
Then the voronoi may become a really good tool for laying out floorplans because of its ability to assign all the input space. Watch this space.....

No comments:

Post a Comment