Maximize coverage of a polygon with a circle of specified radius

Question

I have a set of various irregular polygons with between 3-5 sides. I need to fit a circular wafer of a specific radius inside each of these polygons, but I want to maximize the amount of usable area of my wafer (have the most possible area of the circular wafer inside the polygon). The polygons are all slightly larger than the wafers, and I am hoping to write some sort of matlab code to help me know how to position the wafers to maximize usable area.

Answer 1

You might be able to do a monte carlo method to get an approximate solution.

0. Define a rectangular window that contains both the circle and the polygon.

1. Generate a reasonable number of random points (will depend on error bounds you want) and for each point, test if it is inside the circle, inside the polygon, or both, or neither.

2. loop:

   Fix the circle radius and center point (3 variables). Check each point in the saved list to see if it's inside circle, both circle and polygon, only polygon, or neither (for each r,x,y, in the loop).

   Save result for each test into a dictionary (e.g. [{r,x,y}:{(num inside polygon, but outside circle)/(num inside circle and polygon)},...]

   end loop

3. Return the triple (r,x,y) where the above value is smallest.

You might be able to use Matlab fminsearch optimisation function to vary the r,x,y for you (these would be the input variables; the random points would stay fixed).

PS: For determining if a point lies inside the region, you might consider using matlabs polyshape library, which converts a set of points to a polyshape object, which actually has a method called isinterior. here

For checking if a point lies inside a circle ... that is easy. If $$(x_0-x)^2+(y_0-y)^2 < r^2,$$ then $(x_0,y_0)$ lies inside.