1
$\begingroup$

Let's say we have a 2D Polygon ( it can be concaved or convex), and on top of this polygon we are required to build a house roof. What is the algorithm that one can use for this?

The conditions:

  1. The roof cannot be $0^o$ or $90^o$.
  2. The created roof piece must be as smooth as possible ( smooth is defined as first order differentiable), meaning the slope of the roof must not change unnecessarily.

I'm sorry if the conditions sound vague. If you get lost, just think about this: you have a house, how do you generate the roof profile?

Note: The roof plan must be uniformly sloping, so no circle, or bump can be used.

  • 0
    Is the polygon the "floor plan" of the house?2011-01-05
  • 0
    @Day, you can say that2011-01-05
  • 2
    How about drawing a circle around the polygon, building a hemispherical dome over it, then slicing off the parts of the dome that extend beyond polygon?2011-01-05
  • 0
    @Day, no, that's not what I have in mind :)2011-01-05
  • 0
    @Ngu: What additional characteristics is the roof to have? Maybe that it's the same height along the perimeter of the polygon? Have you looked at "bump functions"? http://en.wikipedia.org/wiki/Bump_function2011-01-05
  • 0
    @Day, yes, one can assume that it is of the same height. No, bump function is not desired.2011-01-05
  • 0
    @Ngu: Is a pyramid an acceptable roof for a convex polygon? If so, then how about ... Pick a point in the interior and build a solid pyramid with apex over that point, covering all vertices the point can "see"; then pick a point in a part not yet covered and build another pyramid covering vertices *that* point can "see"; etc, until the polygon is covered; then take as the roof the surface of the union of these pyramidal solids? (It's possible that a resulting "trough" might be horizontal, but wiggling might help that. There may be other issues, as well.) The Art Gallery Theorem may be helpful.2011-01-05
  • 0
    @Day, from your description, I afraid that your house roof is highly unconventional. So, sorry, no.2011-01-05

3 Answers 3

2

Try computing the straight skeleton of the polygon. See also http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html and http://www.vterrain.org/Culture/BldCity/Roof/ for instance.

3

Here is an image I happen to have prepared for a book. It shows the medial-axis polyhedron over a convex polygon, which coincides with the straight skeleton as in lhf's answer, and also with the offset-procedure in alQpr's answer. Sides slope at $45^\circ$.
MedialAxis Polyhedron

  • 0
    That's the graph of the distance to the polygon's boundary.2011-01-06
  • 0
    yup!! This is what I want. You have an algorithm for this?2011-01-06
  • 0
    Sorry I never replied---Somehow I missed these comments. @whuber: Yes, precisely.2011-11-22
  • 1
    @Graviton: The algorithm is described in _[Discrete and Computational Geometry](http://cs.smith.edu/~orourke/DCG/)_, Chapter 5.2011-11-22
2

Start at the outside. Step inwards a small amount to generate a first level (polygonal) curve at a small height above the wall. Project "ridge" lines from outward corners of house (or crotch lines for inside corners) through corresponding corners of the new polygon (I guess they'll be bisecting the angles of the original polygon) and whenever two or more ridgelines, or two or more of the edges meet, repeat the process starting with the reduced polygon(s) which give the level curve through the point of intersection.