3

I have found this problem in a book and am trying desperately to solve it. The Question itself is: Create a rooftop (non-flat roofs) with the maximum height. The Walls are either in an angle of 90 degrees or parallel.

My approach:
I have all the edge points. So I can use a scanline approach. I will sort all my points on the x-Axis and then y-Axis. I will then go through my whole list of points and draw a line in 45° to the walls. I will check if any line intersects with my current line I've already drawn. If there's no match I will go to the next point and draw another line 45° to the walls. Now the chance is high that the last 2 lines intersect and so I will make a new point at the point of intersection.
The problem I have is that there would be a lot of special cases. Is there an easier method which I did not think about? Are there other algorithms which are more suited for this kind of problem? What would be your idea to this kind of problem?

Example:
This is what imagine the roof to look like. rooftop

Fabio Oesch
  • 143
  • 2
  • 11
  • There are obviously some constraints missing in your problem as stated: constant circumference? Area of roof tiles? I don't think that putting a bend in your house changes anything - what you save one one side is exactly what you add on the other, so you can keep the house "straight line". (you can see this is true by taking the "lower branch", detaching it, and flipping it - it will now fit exactly with the other piece and make a linear roof). – Floris Nov 04 '13 at 14:41
  • I am not entirely sure what you mean with "linear roof" but what I wanted to create was only "pitched roof". I do not think it is of any matter how many areas I have. I want to create the highest possible roof. – Fabio Oesch Nov 04 '13 at 14:48
  • 1
    What constraints must be met by your design. I imagine "maximize height for given size (area of house covered), and given area of roof (> area of house). Otherwise your solution space is not bounded. So - can you clarify? – Floris Nov 04 '13 at 15:11
  • Maybe add some sample input/output for this algorithm because it really is not clear what the problem is. – littleimp Nov 04 '13 at 15:20
  • 1
    If you want a higher roof, don't put your roof panels at 45 degrees... Make them 89 degrees or something - as long as you stay under 90 degrees, they'll still intersect somewhere up there, and the closer you get to 90 the higher (and sharper) the peak. – twalberg Nov 04 '13 at 15:44
  • @twalberg if that were allowed, there would be no maximum height. – Dave Nov 04 '13 at 20:51
  • 1
    @DaveGalvin Agreed... It's just one of the missing constraints pointed out by Floris. There's obviously more to the question than what is stated... – twalberg Nov 04 '13 at 21:01

2 Answers2

1

I'm not sure if that's what you meant, but my answer is aimed to achieve the roof with the maximal peek height, and not the maximal average height.

The maximal peek height in this problem is determined by the maximal square that can fit into your structure.

So to find it, you just need to look for the maximal square that can fit in and perform a simple pyramid height calculation. For example, if your found a square with an edge of a, and you are constructing the roof with a 45 degrees angle from the base as you mentioned, then: Peek = sqrt(3)*a.

Finding the maximal square shouldn't be a complicated task: for each corner in the structure, go in every direction (up, down, left, right) on a straight line until you go out of the structure (assume we obtained these values up, down, left, right), the maximal square that can be constructed from a corner is the maximum value between min{up, left}, min{up, right}, min{down, left}, min{down, right}. and the maximal square is the maximum value obtained from any corner.

Now construct a pyramid where from the corner with the maximal value. in the rest of the structure you can do whatever you want, as it won't surpass the height of this pyramid.

Ron Teller
  • 1,880
  • 1
  • 12
  • 23
  • I know my question has a lot of things that are missing but I have found out the answer and it is very similar to your answer. I have also found out what my input was. I will clarify what the exact answer is. – Fabio Oesch Nov 12 '13 at 13:02
0

Many people criticized how I asked my question that something is missing and indeed it was missing an input. So as an input I have a set of points example:
(0, 0) (6, 0) (6, -2) (8, -2) (8, 8) (-2, 8) (-2, 3) (0, 3)
in the correct order.

Picture 1

The next thing I have to do is place the points like I have in Picture 1. In my case I have put them a bit to the lower right. Now there is a need to see which points are in the shape and which point are not in the shape. This can be easily found out by intersecting the horizontal and vertical lines which you make of the point with the building. If you find an uneven number you know the point is in the form. Otherwise we delete it.

Picture 2

After all this we're trying to find the biggest rectangle we can create from each point we have found (red line). The only thing we're missing now is that we create a new point on the lower right rectangle and make an other rectangle to the top left (yellow line). As seen in my example we find in this example the biggest square by using the smaller side of the rectangle. This divided by 2 will give us the largest height of the form.

Picture 3

If there are any more clarification you need do not hesitate to ask me.

Fabio Oesch
  • 143
  • 2
  • 11