Now concave shapes...As Felkel explains when a roof is concave sometimes the bisector from a concave point runs into an opposing edge before colliding with either of its neightbours. This has the effect of splitting the remaining polygon into two seperate loops of points.
I look for these intersections as lines intersecting with quads(see adv comp graphics, jordan curve, yada yada....). Problem is there can be a lot of quads, have to test each point against all other lines, leaving this stage of the algorithmO(n*n). This method has to be really bullet proof to be useful as we may expect it to close holes in a surface that have negative edge weights.
The quads are formed by the bisectors and may well be infinite (for example a vertical face, or one with bisectors moving away from each other). But as long as the collision happens a very long way away we dont care about it, so we can just make the planes very, very big and not worry about the limiting case.
Getting this up and going is a real timewaster with picky border conditions. For example the bisectors must intersect with edges in all borderline cases, so that it cant escape between two edges. It'll probably take monday (at least) to finish this, a bit depressing really.