Algorithm: Create rooftop with maximum height

Question

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.

Answer 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.

Answer 2

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.

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.

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.

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