5

I have the following problem which seems related to the packing problem. I have a grid of same size rectangles and a polygon on which this grid of rectangles needs to be placed such that the number of rectangles completely withing the polygon boundaries are maximized. I have added a picture which shows a polygon and a grid of rectangles to illustrate the problem. The polygon can also contain holes.

polygon an rectangle grid

My current algorithmic approach is just to orientate the grid the same way as the longest edge in the polygon. The algorithm needs to be fast, the solution does not need to be optimal. Are there any similiar problems in literature I can read up on?

Also the grid can be rotated and translated arbitrarily.

Av0
  • 51
  • 2
  • 1
    You might get a better response by instead posting with the [computational-geometry] tag at https://math.stackexchange.com/ – RobPratt Apr 10 '22 at 14:53
  • If you cross-post, please indicate that both places. – prubin Apr 10 '22 at 15:38
  • When you say "orient the grid", does that mean you are free to rotate the grid? If so, can you only rotate it 90 degrees, or can you rotate it an arbitrary amount? – prubin Apr 10 '22 at 15:41
  • Also, just to be clear, you can shift the grid an arbitrary amount left/right and up/down? – prubin Apr 10 '22 at 18:39
  • Yes, the grid can be shifted and rotated arbitrarily. – Av0 Apr 11 '22 at 10:05
  • 2
    A bit of a long shot, but you might want to scan literature for nesting problems. A common nesting problem is to cut objects, defined by different polygons, out of a larger object in an attempt to minimize waste. For example, in the textile industry, there exists a problem on how to cut leather products (e.g. different components of a shoe) out of a leather hide. This requires positioning and orienting the different polygons onto the larger object without overlap. This paper might offer a starting point. – Joris Kinable Apr 11 '22 at 22:56
  • @Av0, is it possible to fit each polygon in a square/rectangle? – A.Omidi Apr 13 '22 at 10:48

0 Answers0