Skip to main content
6 of 16
Added another potential solution
Thirlan
  • 157
  • 5

Polygon within polygon problem

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:

  1. all points in A are contained within B
  2. 20 <= m < n
  3. B is the polygon in the set of all Bs with the smallest area
  4. 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:

  1. B is a square.
  2. B is a circle with m points.
  3. Construct B from A by removing concave points. Doesn't work with non-concave polygons however : /
  4. 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).
  5. 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.

Thirlan
  • 157
  • 5