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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Simon F Apr 29 at 10:52
  • $\begingroup$ @SimonF thanks! Edited question. what is "major axis"? Can you expand? $\endgroup$ – DaddyM Apr 30 at 7:52
  • $\begingroup$ 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) $\endgroup$ – Simon F Apr 30 at 11:06
  • 1
    $\begingroup$ @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. $\endgroup$ – DaddyM Apr 30 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.