Description edited after comments:
Let's say I have a 3d cuboid that I projected onto a 2d plane. Now I want to find the minimum-area parallelogram that contains all those projected vertices. How do I go about doing that?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ I'm new around here, so I'm not sure why people are downvoting my question. Perhaps you can write a comment saying what I did wrong to warrant those downvotes? $\endgroup$– MoodyCommented Sep 14, 2017 at 21:26
-
$\begingroup$ Your question is not entirely clear. I tried to answer one interpretation, but I may be reading more into it than is there. $\endgroup$– Joseph O'RourkeCommented Sep 14, 2017 at 22:17
-
$\begingroup$ @JosephO'Rourke I project a cuboid onto a 2D plane, then I want to find the minimum-area parallelogram (on that plane) that encompasses all the projected points. Is that what you understood from my question? $\endgroup$– MoodyCommented Sep 14, 2017 at 22:27
-
1$\begingroup$ The body asks for a "minimum-area plane", which makes no sense, as all planes have infinite area. Then you ask for a "4-point convex hull", but it's not at all clear what this means, since there's no reason to expect a 2-dimensional shape to have a convex hull with four vertices. Then in your comment it seems you're not projecting any old 3-dimensional shape, but a cuboid, and you don't want any old 4-cornered set, but a parallelogram. Please think through your question, and edit the body so it asks what you actually want to ask. $\endgroup$– Gerry MyersonCommented Sep 14, 2017 at 22:55
-
1$\begingroup$ @GerryMyerson I edited the question. I hope that makes it clearer. $\endgroup$– MoodyCommented Sep 14, 2017 at 23:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
(I deleted my first answer, which misinterpreted the original question. Here I address the question in the comments, which is now incorporated in the revised question.)
The minimum area parallelogram enclosing a convex polygon can be found in linear time, linear in the number of vertices (for your case, a small constant). This result depends on proving that two adjacent edges of an optimal parallelogram must be flush with edges of the convex polygon. Once you have that lemma, it is easy to walk through the few possibilities.
Christian Schwarz, Jürgen Teich, Alek Vainshtein, Emo Welzl, and Brian L. Evans. Minimal enclosing parallelogram with application. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages C34–C35, 1995. ACM link.
Fig.2. Illustration of proof of one lemma.
Finding the minimum perimeter enclosing parallelogram (not what was asked) is a bit more involved, but can also be found in linear time.
answered Sep 14, 2017 at 22:02