<p>I am solving the task that is as follows:</p>

<p><strong>Input:</strong> a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside.</p>

<p><strong>Goal:</strong> to cover it with 2 (at least) or more parallelograms that together are equal to or contain the whole polygon. The following criteria should be met:</p>

<ul>
<li>There is no point of the polygon that lies beyond parallelograms.</li>
<li>The number of the parallelograms should be the least possible. I.e. we want to find largest parallelograms that cover the polygon.</li>
<li>These parallelograms must not intersect within the polygon.</li>
</ul>

<p><strong>Question:</strong> Is this task solved and if it is solved - how? I am looking for a direction where to start with and what related algorithms/theory to learn.</p>

CC BY-SA 4.0
2019-04-29T10:52:36.907Z
When you say *"cover it with 2 (at least)"* and *"The amount of the parallelograms should be the least possible and the square of the parallelograms should be the least possible"* which takes priority? If the former, then surely it must always be 2 parallelograms?

Further, do any of the sides have to be aligned with a major axis or can they be entirely arbitrary?
Simon F
CC BY-SA 4.0
2019-04-30T07:52:06.417Z
@SimonF thanks! Edited question. what is "major axis"? Can you expand?
nickolay
CC BY-SA 4.0
2019-04-30T11:06:48.310Z
By "major axis" I just meant do you want to constrain all the parallelograms so that 2 sides are always horizontal (or vertical)? I was just wondering if you were trying to do, say, some kind of conservative rasterisation. (Also quite a few polygon triangulation algorithms first divide the data into trapeziums (*for those in USA, "trapezoids"* :-/ ) with horizontal  top and bottom edges. I was just thinking maybe you wanted something similar)
Simon F
CC BY-SA 4.0
2019-04-30T13:37:23.893Z
@SimonF I understood that I myself need to know more about the task so I could specify it better. I am going to understand the thing deeper, draw some images of input polygon and desired output and will come back.
nickolay
<computational-geometry><polygon>
Cover a polygon with least amount of parallelograms
nickolay
# Cover a polygon with least amount of parallelograms

(Asked by: username_0 on 2019-04-28)

I am solving the task that is as follows:

**Input:** a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside.

**Goal:** to cover it with 2 (at least) or more parallelograms that together are equal to or contain the whole polygon. The following criteria should be met:

* There is no point of the polygon that lies beyond parallelograms.
* The number of the parallelograms should be the least possible. I.e. we want to find largest parallelograms that cover the polygon.
* These parallelograms must not intersect within the polygon.

**Question:** Is this task solved and if it is solved - how? I am looking for a direction where to start with and what related algorithms/theory to learn.

**Tags:** computational-geometry, polygon

> **Comments:**
> **username_1**: When you say *"cover it with 2 (at least)"* and *"The amount of the parallelograms should be the least possible and the square of the parallelograms should be the least possible"* which takes priority? If the former, then surely it must always be 2 parallelograms?  Further, do any of the sides have to be aligned with a major axis or can they be entirely arbitrary?  
> **username_0**: @username_1 thanks! Edited question. what is "major axis"? Can you expand?  
> **username_1**: By "major axis" I just meant do you want to constrain all the parallelograms so that 2 sides are always horizontal (or vertical)? I was just wondering if you were trying to do, say, some kind of conservative rasterisation. (Also quite a few polygon triangulation algorithms first divide the data into trapeziums (*for those in USA, "trapezoids"* :-/ ) with horizontal  top and bottom edges. I was just thinking maybe you wanted something similar)  
> **username_0**: @username_1 I understood that I myself need to know more about the task so I could specify it better. I am going to understand the thing deeper, draw some images of input polygon and desired output and will come back.  

---

## 0 answers

