<p>(Not an answer but my comments are too large for a "comment") </p>

<p>This is more computational geometry than graphics. First of all, it would help if you could give an example (a drawing) which describes your input and your expected output. Are you working with low count polygons, or precise coastal maps? Do you want a real-time solution or is it off-line? It could be a big help if you would describe what you want to obtain with these rectangles covering your polygon. Also, what are your needs concerning the solution(s), for instance do you want the area of the rectangles to be as least as possible?</p>

<p>Intrinsically this is NP-hard, this means there is a vast amount of possible solutions when the size of input data rises. Think of a circle covered by a square divided in two not necessarily equally sized rectangles. There is an infinite set of solutions already there concerning where they are split. Then just think of the amount of possible solutions for optimally packing a star shape into five or so rectangles, it's simply "not possible" if you want it done on a computer, in finite time.</p>

<p>So, you will be looking for a heuristic, that gives you a solution but not necessarily an optimal one. This means that you need to figure out what you want to accept being a solution.</p>

<p>Edit: One variant of the problem at hand, that I didn't think of, could be that you already have N rectangles (size is given up front, they might be of the same size) that you wish to cover a polygon with. It's not simpler, also it could be impossible, for instance if the total area of the rectangles is less than the area of the polygon. So: Please describe your problem at bit more :)</p>

CC BY-SA 4.0
2019-02-15T10:08:56.557Z
2019-02-15T13:10:43.083Z
2019-02-15T13:10:43.083Z
beyond
<p>Some search terms that might benefit you: &quot;image decomposition&quot; and &quot;image segmentation.&quot;</p>
<p>For a good overview of some techniques, see <a href="http://library.utia.cas.cz/separaty/2012/ZOI/suk-0381722.pdf" rel="nofollow noreferrer">Decomposition of binary images — A survey and comparison</a>, by Suk et. al.</p>

CC BY-SA 4.0
2020-10-23T20:33:05.220Z
2020-10-23T20:33:05.220Z
jwd
<p>I can't comment as I don't have enough reputation but I would take a look at packing algorithms, specially the ones using No/Inner Fit Polygon through computation of Minkowsky differences.</p>

CC BY-SA 4.0
2019-02-19T18:42:46.317Z
2019-02-19T18:42:46.317Z
Felipe Gutierrez
<p>I am looking for an algorithm that is able to cover with non-overlapping rectangles in a pre-defined number and minimum area a generic 2d-polygon.</p>

<p>Polygons are usually free-hand draws, so they can be of really any shape and number of vertexes and having holes.</p>

<p>I found different articles like: <a href="https://en.wikipedia.org/wiki/Polygon_covering" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Polygon_covering</a></p>

<p>but I am not sure if it is what I am looking for. Can you point me to some source code or something readable for a non-graphic guy?</p>

CC BY-SA 4.0
2019-02-13T13:14:34.873Z
"but I am not sure if it is what I am looking for" - why do you expect that others would know what you're looking for? It's not obvious what you want from the way you formulated it. There's infinitely many ways to cover a polygon with rectangles. The simplest is to just take max and min $x,y$ vertices and create a rectangle based on that.
lightxbulb
CC BY-SA 4.0
2019-02-13T13:17:31.180Z
Yes if the number of rectangle is 1. I need one algorithm that does that but choosing the number of rectangles
Randomize
CC BY-SA 4.0
2019-02-13T13:19:53.680Z
For not sure what I am looking for is the high number of papers that I am not able to understand properly as non-graphic guy.
Randomize
CC BY-SA 4.0
2019-02-13T13:20:12.500Z
As I said, this has infinitely many solutions. If you want n rectangles, you could just partition that 1 rectangle into however many you want. The issue here is that as you formulated your problem it's underconstrained.
lightxbulb
CC BY-SA 4.0
2019-02-13T13:22:35.457Z
In that way it won’t grant me minimum area coverage. If you take a triangle and apply that how it will work?
Randomize
CC BY-SA 4.0
2019-02-13T13:24:55.617Z
You never mentioned anything about minimal area in your question. Edit your question to provide additional details.
lightxbulb
CC BY-SA 4.0
2019-02-13T13:53:59.887Z
You should also include the form of your polygon (rectilinear, convex, with holes,self intersecting, etc), as well as whether the covering rectangles need to be axis aligned or not.
lightxbulb
CC BY-SA 4.0
2019-02-13T14:06:56.237Z
As you have formulated your problem it is NP. (also do add whether the rectangles are axis-aligned). Considering that the problem is NP you might want to look at approximations to the actual solution. https://link.springer.com/article/10.1007%2Fs10589-009-9258-1
lightxbulb
CC BY-SA 4.0
2019-04-26T05:34:05.333Z
How about considering the answer from other SE such as this:
https://mathoverflow.net/questions/105164/covering-a-polygon-with-rectangles
Karsun
<algorithm><polygon>
An algorithms for covering a 2d polygon with a predetermined number of rectangles?
Randomize
# An algorithms for covering a 2d polygon with a predetermined number of rectangles?

(Asked by: username_0 on 2019-02-13)

I am looking for an algorithm that is able to cover with non-overlapping rectangles in a pre-defined number and minimum area a generic 2d-polygon.

Polygons are usually free-hand draws, so they can be of really any shape and number of vertexes and having holes.

I found different articles like: <https://en.wikipedia.org/wiki/Polygon_covering>

but I am not sure if it is what I am looking for. Can you point me to some source code or something readable for a non-graphic guy?

**Tags:** algorithm, polygon

> **Comments:**
> **username_1**: "but I am not sure if it is what I am looking for" - why do you expect that others would know what you're looking for? It's not obvious what you want from the way you formulated it. There's infinitely many ways to cover a polygon with rectangles. The simplest is to just take max and min $x,y$ vertices and create a rectangle based on that.  
> **username_0**: Yes if the number of rectangle is 1. I need one algorithm that does that but choosing the number of rectangles  
> **username_0**: For not sure what I am looking for is the high number of papers that I am not able to understand properly as non-graphic guy.  
> **username_1**: As I said, this has infinitely many solutions. If you want n rectangles, you could just partition that 1 rectangle into however many you want. The issue here is that as you formulated your problem it's underconstrained.  
> **username_0**: In that way it won’t grant me minimum area coverage. If you take a triangle and apply that how it will work?  
> **username_1**: You never mentioned anything about minimal area in your question. Edit your question to provide additional details.  
> **username_1**: You should also include the form of your polygon (rectilinear, convex, with holes,self intersecting, etc), as well as whether the covering rectangles need to be axis aligned or not.  
> **username_1**: As you have formulated your problem it is NP. (also do add whether the rectangles are axis-aligned). Considering that the problem is NP you might want to look at approximations to the actual solution. https://link.springer.com/article/10.1007%2Fs10589-009-9258-1  
> **username_2**: How about considering the answer from other SE such as this: https://mathoverflow.net/questions/105164/covering-a-polygon-with-rectangles  

---

## 3 answers

### Answer by username_3 on 2019-02-15. Score: 1

(Not an answer but my comments are too large for a "comment")

This is more computational geometry than graphics. First of all, it would help if you could give an example (a drawing) which describes your input and your expected output. Are you working with low count polygons, or precise coastal maps? Do you want a real-time solution or is it off-line? It could be a big help if you would describe what you want to obtain with these rectangles covering your polygon. Also, what are your needs concerning the solution(s), for instance do you want the area of the rectangles to be as least as possible?

Intrinsically this is NP-hard, this means there is a vast amount of possible solutions when the size of input data rises. Think of a circle covered by a square divided in two not necessarily equally sized rectangles. There is an infinite set of solutions already there concerning where they are split. Then just think of the amount of possible solutions for optimally packing a star shape into five or so rectangles, it's simply "not possible" if you want it done on a computer, in finite time.

So, you will be looking for a heuristic, that gives you a solution but not necessarily an optimal one. This means that you need to figure out what you want to accept being a solution.

Edit: One variant of the problem at hand, that I didn't think of, could be that you already have N rectangles (size is given up front, they might be of the same size) that you wish to cover a polygon with. It's not simpler, also it could be impossible, for instance if the total area of the rectangles is less than the area of the polygon. So: Please describe your problem at bit more :)


---

### Answer by username_4 on 2020-10-23. Score: 0

Some search terms that might benefit you: "image decomposition" and "image segmentation."

For a good overview of some techniques, see [Decomposition of binary images — A survey and comparison](http://library.utia.cas.cz/separaty/2012/ZOI/suk-0381722.pdf), by Suk et. al.


---

### Answer by username_5 on 2019-02-19. Score: 0

I can't comment as I don't have enough reputation but I would take a look at packing algorithms, specially the ones using No/Inner Fit Polygon through computation of Minkowsky differences.


---

