I've been trying for a while to think of an algorithm as follows:
Input: List of line segments (x1,y1,x2,y2) forming a closed polygon. x/y points need not be integers, polygon need not be convex.
Output: Another list of line segments forming a closed polygon, with the property that:
a) Relative to the horizontal every line segment is exactly a multiple of k degrees - i.e. if k=60 then there are only 6 possible angles a line could take.
b) Intersection Over Union between the output polygon and the input polygon is maximized.
The greedy algorithm would be:
For each line segment, rotate it about its midpoint to align it to the nearest multiple of k degrees, changing the start/end point of neighboring lines to keep the polygon closed.
Choose the line segment not yet aligned for which making this alignment causes the highest IOU relative to previous iteration, and commit to that move.
Repeat until all lines adjusted.
However, I don't think this would produce the best possible result - when trying to change a line whose endpoints have already been changed by moving other lines, it might not produce an answer as good as an algorithm that considered all the lines together.
1) Does the greedy algorithm produce the optimal answer? (I expect not)
2) Can you help me devise an algorithm that does produce the optimal answer?