Following is the problem statement.
You have been given k number of equilateral triangles (There is a upper cap on
k, lets say k=<15). The triangles can be overlapping.
Now you have to find a parallelogram enclosing all the triangles and has the
minimum area. It is given that two opposite edges of the four edges are
parallel to either X axis or Y axis(That is your choice).
Let’s say two of them are parallel to Y axis.
Then the leftmost point and the rightmost point of the set of triangles
will lie in two opposite edges of the parallelogram. Now I will draw two straight lines which pass through these points and are parallel to the Y axis.
This way I have found two edges its not so difficult.
Now I am stuck and don’t know how to find other two.
I thought a lot but since I was unable to make it out I am posting it here.
Any help will be appreciated!!!!!!!
Build convex hull around all triangles vertices.
Then use rotating calipers to get a pair of parallel lines with the smallest vertical distance between them (parallelogram area is defined by height (here horizontal) – it is already fixed, and by vertical base length – choose minimum)