# How to create Minimum bounding shapes such as ellipse, triangle, quadrilateral from a given 2d shape

**URL:** <https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460>\
**Category:** Coding Questions\
**Created:** [April 17, 2021, 7:23pm UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460 "2021-04-17T19:23:18Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Goodman](https://avatars.discourse-cdn.com/v4/letter/g/838e76/32.png) [@Goodman](https://discourse.processing.org/u/Goodman)\
**Post date:** [April 17, 2021, 7:23pm UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/1 "2021-04-17T19:23:18Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [April 17, 2021, 7:56pm UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/2 "2021-04-17T19:56:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [April 17, 2021, 8:29pm UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/3 "2021-04-17T20:29:38Z")

</div>

Bounding rectangle and ellipse are implemented here (in a geometry library I’m close to releasing):

> **[micycle1/PGS - Geometric Optimization](https://github.com/micycle1/PGS#geometric-optimization)**
>
> Processing Geometry Suite. Contribute to micycle1/PGS development by creating an account on GitHub.

@Chrisir Your suggestion would compute the [_envelope_](https://github.com/micycle1/PGS#envelope) of the shape, not necessarily the **minimum** bounding rectangle.

---

<div class="post-metadata">

**Author:** ![Goodman](https://avatars.discourse-cdn.com/v4/letter/g/838e76/32.png) [@Goodman](https://discourse.processing.org/u/Goodman)\
**Post date:** [April 18, 2021, 4:46am UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/4 "2021-04-18T04:46:36Z")

</div>

@Chrisir Thanks for the suggestion. But, this just creates a bounding box. I want to know how to generate these minimum bounding shapes.

---

<div class="post-metadata">

**Author:** ![Goodman](https://avatars.discourse-cdn.com/v4/letter/g/838e76/32.png) [@Goodman](https://discourse.processing.org/u/Goodman)\
**Post date:** [April 18, 2021, 4:54am UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/5 "2021-04-18T04:54:46Z")

</div>

@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

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [April 19, 2021, 12:16pm UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/6 "2021-04-19T12:16:45Z")

</div>

Hi @Goodman,

Searching for “ **minimum enclosing triangle** ” on Google yields interesting results:

- [OpenCV](https://opencv.org/) has a `minEnclosingTriangle()` [function](https://docs.opencv.org/master/d3/dc0/group __imgproc__ shape.html#ga1513e72f6bbdfc370563664f71e0542f) that you could try to access via its [Java interface](https://opencv-java-tutorials.readthedocs.io/en/latest/01-installing-opencv-for-java.html).

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 ready-made 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](https://arxiv.org/pdf/1905.11203v2.pdf))

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [April 19, 2021, 2:21pm UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/7 "2021-04-19T14:21:49Z")

</div>

Funny you’ve linked to OpenCV – I tried porting their C++ [implementation](https://github.com/opencv/opencv/blob/master/modules/imgproc/src/min_enclosing_triangle.cpp) to Java the other day.

Sometimes it works:

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/3/35c4a3d7b157c3a9975922cbddd72e992adf611e.png) ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/7/740bf68ee388456863694e5732596c3b7758de3d.png) ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/d/dafec6df7542e20f5091b3c8a3689168201b5a23.png)

Occasionally it doesn’t:

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/7/7b43ee7993383fda2194376302acb6388543d94a.png)

Other times there’s no output at all:

![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/7/7f8261ffae257f5f7e07462085e803c536a6a60f.png)

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…

> <https://gist.github.com/micycle1/e6548e4e2cb66a52371499baac634683>

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [April 20, 2021, 9:24am UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/8 "2021-04-20T09:24:36Z")

</div>

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 built-in `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)

 ![MET](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/b/b569b8d0555e6909e60ab091b18fe82ee3a812b3.jpeg)

Here are some polygons (coordinates of convex hulls) that were problematic (without the procedure), if you want to test out:

```auto
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)]

```

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [January 6, 2022, 5:20pm UTC](https://discourse.processing.org/t/how-to-create-minimum-bounding-shapes-such-as-ellipse-triangle-quadrilateral-from-a-given-2d-shape/29460/9 "2022-01-06T17:20:00Z")

</div>

[Processing Geometry Suite](https://discourse.processing.org/t/processing-geometry-suite/29924) now has a robust _Minimum Bounding Triangle_ method (first Java implementation as far as I can tell).

![ezgif.com-gif-maker (2)](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/b/b27eb089c886e06f622def736c2d0b07e80f0ddd.gif)