Given:
Construct the "roof" geometry of the polygon by generating a new polygonal mesh that extends into the 3rd dimension (perpendicular to the plane that the polygon lies in) such that the slope of the roof at each edge is equal to the slope defined in (B) (with the slope going “up” toward the inside of the polygon).
Specifically, I am trying to create the algorithm that would reliably generate this geometry. It is for software that I am writing. The output would be a list of simple polygons.
My initial instinct was to use half spaces combined with Boolean operations. I think this would work for convex polygons, but not for concave polygons. Additionally, it raises the question: even if I get a working algorithm for determining the proper combination of half-spaces, how do I convert that representation into a polygonal mesh?
I also tried generating a height map by combining gradients, but this suffers from the same weaknesses of the half space method (works well for convex but not concave, and given a solution, how to convert that into a polygonal mesh).
I tried a voronoi-esque method that was somewhat promising, but it results in some undesired curves (see purple + green/red) and suffers from the same “still-need-the-polygonal-mesh” problem.
Examples of correct solutions (not to scale)
(Dashes represent a slope of infinity)
Final example:
Top: 2 has same slope as 1 and 3
Middle: 2 has shallower slope than 1 and 3
Bottom: 2 has steeper slope than 1 and 3
I saw that this had been voted as "off topic" initially and thought that it wouldn't be posted. However, since it is posted publicly now, I thought that I would share the solution I found over at the math stack exchange:
https://math.stackexchange.com/questions/16400/generate-roof-from-a-2d-polygon
The answer is to compute the straight skeleton. More specifically, to compute the extrusion of a weighted straight skeleton.
CGAL provides such a function: https://doc.cgal.org/latest/Straight_skeleton_2/index.html#Straight_skeleton_2Extrusion