Problem: You have a set of n ordered x,y points that form a contour of polygon A that may or may not be concave. You must create a new polygon B with m points such that:
- all points in A are contained within B
- 20 <= m < n
- B is the polygon in the set of all Bs with the smallest area
- the algorithm must be reasonably fast and not overly complicated (i.e. no fast-fourier transforms lol!)
I'd like (3) to be the optimal solution but it doesn't have to be since I think this would make the problem NP-hard. This solution is for practical purposes so I'm really looking for a practical solution. (1) Is critical so whatever the solution is it should be trivial to prove that (1) holds true.
Have four solutions so far:
- B is a square.
- B is a circle with m points.
- Construct B from A by removing concave points. Doesn't work with non-concave polygons however : /
- Construct B from A by looping through each point "a" and taking the next two points "b" and "c". Then create a ray "ab" through "a" and "b". Move point "c" the minimum distance such that it is on the ray "ab". Remove point "b". This method doesn't always work and I have found cases where it will fail to with rule (1).
- Draw a triangle around the polygon and use rays to iteratively slice away the sub-section with the largest area that contains no points from Polygan A.
Each solutions is terrible in its own way.