On 16-11-2010 4:35, Darren New wrote:
> Darren New wrote:
>> I'm thinking you could probably triangulate all the areas between
>> verticies.
>
> FWIW, it looks like
> http://en.wikipedia.org/wiki/Delaunay_triangulation
> is getting me on the way.

I was thinking about that too,but you can not guarantee that existing 
walls are part of the triangles. You need an additional program to flip 
edges until all are in the correct order.

I think this may also work:
(first close the exit in order to get one graph)
create a list by a depth first search over the entire tree and note 
every node number going down and up.

make an emty list of triangles
repeat
- find three consecutive points that form a triangle with a positive area
- add that triangle to your list of triangles
- remove middle point from list
until list contains 2 elements (both sides of the entrance)

Post a reply to this message