0
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ "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. $\endgroup$
    – lightxbulb
    Commented Feb 13, 2019 at 13:14
  • $\begingroup$ Yes if the number of rectangle is 1. I need one algorithm that does that but choosing the number of rectangles $\endgroup$
    – Randomize
    Commented Feb 13, 2019 at 13:17
  • $\begingroup$ 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. $\endgroup$
    – Randomize
    Commented Feb 13, 2019 at 13:19
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Commented Feb 13, 2019 at 13:20
  • $\begingroup$ In that way it won’t grant me minimum area coverage. If you take a triangle and apply that how it will work? $\endgroup$
    – Randomize
    Commented Feb 13, 2019 at 13:22

3 Answers 3

Reset to default
1
$\begingroup$

(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 :)

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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, by Suk et. al.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.