I have a 2d shape(boundary) and generated the convex hull. Now, I want to create a minimum bounding quadrilateral, minimum bounding triangle, and minimum bounding ellipse for that boundary. I have generated these minimum bounding shapes using a predefined function in matlab. But I want to do the same in Processing or C. Any ideas on how to proceed after creating a convex hull for a given 2d shape in C or processing.
How to create Minimum bounding shapes such as ellipse, triangle, quadrilateral from a given 2d shape
You have a convex hull?
Check the vertixes in a for loop
For your rect: the smallest x and y = upper left corner, the biggest = lower right corner
Bounding rectangle and ellipse are implemented here (in a geometry library I’m close to releasing):
@Chrisir Your suggestion would compute the envelope of the shape, not necessarily the minimum bounding rectangle.
@Chrisir Thanks for the suggestion. But, this just creates a bounding box. I want to know how to generate these minimum bounding shapes.
@micycle Great work! I’m able to generate a minbounding rect and circle. But I want to know how to generate minbounding quadrilateral triangle and ellipse
Hi @Goodman,
Searching for “minimum enclosing triangle” on Google yields interesting results:

OpenCV has a
minEnclosingTriangle()
function that you could try to access via its Java interface.
Considering the OBR (Oriented Bounding Rectangle) mentioned by @micycle is a quadrilateral already my guess is that you are looking either for a bounding irregular quadrilateral or for the minimum enclosing parallelogram.
Considering the apparent lack of readymade function for both, I would suggest to implement your own solution based on the few papers available on the subject (ex: Smallest Enclosing Parallelogram of a Convex Polygon)
Funny you’ve linked to OpenCV – I tried porting their C++ implementation to Java the other day.
Sometimes it works:
Occasionally it doesn’t:
Other times there’s no output at all:
There might be just one bug in there somewhere… Anyway, I didn’t realise it had a Java interface so I’ll try that and compare…
I just ported the algorithm in Python mode based on an implementation I found on GitHub and it seems I’m running into the same kind of issue: it works in most cases but sometimes fails to return a triangle (at all).
Not sure what could be the cause of this but I found out that a slight change in the floating numbers (be it a distance or a vector) usually solves the problem. For instance, calling sqrt
from Python ‘math’ module sometimes makes possible to return a valid triangle when Processing builtin sqrt
function fails to do so. Same thing for PVectors and Python tuples, sometimes one makes the whole thing work when the other doesn’t.
For now I’m adding a simple rule at the end of the procedure and it works great so far:
 if no valid triangle is found → flip the the order of the input vertices and compute again
 if still no valid triangle → add a slight change in the input vertices (± 1x10^3)
Here are some polygons (coordinates of convex hulls) that were problematic (without the procedure), if you want to test out:
hull = [PVector(155.12383, 248.58586, 0.0), PVector(161.0123, 179.3106, 0.0), PVector(168.83984, 130.08127, 0.0), PVector(248.66309, 119.282684, 0.0), PVector(461.89334, 137.37393, 0.0), PVector(475.26022, 199.19283, 0.0), PVector(245.58762, 380.92023, 0.0)]
hull = [PVector(110.02104, 279.57806, 0.0), PVector(123.71097, 101.68562, 0.0), PVector(334.75125, 123.85287, 0.0), PVector(357.30774, 305.98468, 0.0), PVector(333.9188, 368.8738, 0.0), PVector(303.62317, 390.05, 0.0), PVector(210.75824, 340.84155, 0.0)]
hull = [PVector(192.95053, 342.0016, 0.0), PVector(218.2282, 214.57556, 0.0), PVector(356.4301, 116.1142, 0.0), PVector(458.212, 231.65149, 0.0), PVector(429.22546, 332.95416, 0.0), PVector(390.15195, 342.7939, 0.0), PVector(263.15396, 347.68643, 0.0)]
hull = [PVector(129.48656, 388.42194, 0.0), PVector(181.31583, 230.62254, 0.0), PVector(212.38477, 167.97357, 0.0), PVector(469.0845, 162.51602, 0.0 ), PVector(486.59265, 234.31108, 0.0), PVector(477.97174, 363.26276, 0.0), PVector(431.43225, 382.64935, 0.0)]
hull = [PVector(202.1734, 128.25597, 0.0), PVector(425.54095, 139.74759, 0.0), PVector(428.87698, 295.7047, 0.0), PVector(255.63092, 373.27747, 0.0)]
hull = [PVector(128.32523, 105.98023, 0.0), PVector(393.61334, 184.44684, 0.0), PVector(493.83255, 221.63284, 0.0), PVector(411.80234, 359.64954, 0.0), PVector(231.17766, 248.42395, 0.0)]
hull = [PVector(110.02104, 279.57806, 0.0), PVector(123.71097, 101.68562, 0.0), PVector(334.75125, 123.85287, 0.0), PVector(357.30774, 305.98468, 0.0), PVector(333.9188, 368.8738, 0.0), PVector(303.62317, 390.05, 0.0), PVector(210.75824, 340.84155, 0.0)]
hull = [PVector(117.05237, 112.30546, 0.0), PVector(393.43924, 145.73712, 0.0), PVector(404.43298, 160.94029, 0.0), PVector(443.2803, 341.7787, 0.0), PVector(129.86247, 331.0315, 0.0), PVector(117.686295, 218.09064, 0.0)]
hull = [PVector(179.54169, 370.20096), PVector(184.75476, 138.93231), PVector(206.79596, 130.36479), PVector(350.9182, 143.59122), PVector(497.7497, 301.03436), PVector(253.6199, 396.03775)]
Processing Geometry Suite now has a robust Minimum Bounding Triangle method (first Java implementation as far as I can tell).