Saddle roof algorithm

I have map (openstreetmap project) with many buildings. Each building is a polygon. How can I make saddle roof parts polygons for every building outline?

Algorithm sho开发者_如何学Gould transform one polygon in 2D to set of polygons in 2D (or 3D).

Reason for this transformation is visualization - better rendering isometric view.

For example (shading isn't important):

alt text http://www.freeimagehosting.net/uploads/0168cec03a.png

Thanks

Main part (like 90%) of what you are looking for is called "skeleton". Take a look here, at the figure called "Other examples". This page is from a manual of a computer graphics library, so you'll find there a general description, and links to the (free) code.

Isn't this just what you get with a 4-neighbor watershed algorithm, plus marking all edges that are local extrema along the line perpendicular to the direction of fastest ascent? (The shading would need to be added somehow, of course, but wouldn't this give you the position of the roof peaks and angles?)

Your examples seem to assume that all roof slopes are the same. The additional lines (when seen directly from above) are then the lines of equal distance from the edges. These can be constructed by taking the angle bisector between two edges.

The algorithm would look like this:

• Start with any two neighbouring edges.
• Add a line along their angle bisector.
• Take the next neighbouring edge.
• Add a line along this angle bisector.
• Where two new lines meet, mark a new vertex, and clip the lines.
• From this vertex, add a line along the angle bisector of the two outer edges where the two lines originated.
• Take the next edge, etc..
• Take care to correctly clip the new lines and manage the new vertices.