Algorithm: Create rooftop with maximum height
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.
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.
- How can I create all combinations of this object's keys/values in JavaScript?
- Why does the xorshift random number generator always seem to use these specific shifts?
- Checking if a word in string contains a palindrome
- Efficient algorithm for detecting cycles in a directed graph
- How does a 'diff' algorithm work, e.g. in VCDIFF and DiffMerge?
- Find minimum sum from given array
- algorithm using recursive function
- Javascript twoSum algorithm: Given an array of integers, return indices of the two numbers such that they add up to a specific target
- Split String into smaller Strings by length variable
- Bubble sort does not sort as expected
- Shortening list of numbers with hyphens between consecutive numbers
- Adjacent items in Quicksort's output: Does the algorithm guarantee they have been directly compared?
- The simplest way to write a unit conversion program
- Isn't there any more efficient solution for the CodeForces 919-B/Perfect Number question?
- What's the difference between O(n) and O(n+n^1/2) in algorithm?
- Understanding dynamic programming timeouts with 2 different solutions
- ColdFusion - What's an efficient way to search an array of structs?
- DirectoryInfo.EnumerateFiles(...) causes UnauthorizedAccessException (and other exceptions)
- How can I find the number of concordant/discordant pairs for a given cell in Google Sheets?
- Fastest algorithm for filling overlapping rectangles of pixels
- How to sort with incomplete ordering?
- Fast CRC algorithm?
- Extract the closest two numbers that multiply to create a given number
- Best algorithm for delete duplicates in array of strings
- Understanding the Time Complexity Difference of Two Ways to Generate Subsets
- Online algorithm for calculating standard deviation of counts
- Calculate Time Remaining
- Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
- Search Algorithm to find the k lowest values in a list (selection algorithm/problem)
- While finding count of points inside some shape using KD-Tree, do we need to check areas intersection, or just compare depth-appropriate properties?