# [QGIS-Developer] MinimumRectangle implementation

L.Bartoletti lbartoletti at tuxfamily.org
Thu Jun 8 13:28:01 PDT 2017

```Hello,

Yes, I have implemented this algorithm in python (processing). In my
memories, my other template was a R source code
<http://dwoll.de/rexrepos/posts/diagBounding.html>.

Regards.

Le 08.06.2017 à 09:21, Havard Tveite a écrit :
> The QgsGeometry::orientedMinimumBoundingBox seems to implement
> the rotating calipers method.  If it does, it should produce
> the correct minimum bounding rectangle.
> (http://en.wikipedia.org/wiki/Minimum_bounding_box_algorithms)
>
> Håvard
>
> On 08. juni 2017 01:18, Nyall Dawson wrote:
>> On 6 June 2017 at 18:43, Paul Jobling <paul.jobling at gmail.com> wrote:
>>
>>> I am implementing geo in the Kognitio WX2 database using GEOS as a
>>> backend,
>>> though I am using my own code for many things. One of those things is
>>> ST_MinimumRectangle, which I have implemented as the rectangle with the
>>> smallest area that encloses the geometry. This is different to the
>>> implementation that I see you have recently added, which
>>> extrapolates from
>>> the MinimumDiameter property.
>>>
>>>
>>>
>>> For example, ST_MinimumRectangle ('POLYGON((1 2, 3 0, 5 2, 3 2, 2 3,
>>> 1 2))')
>>> has an area of 9.6 (and a perimeter of 12.65) using the MinimumDiameter
>>> implementation, whereas my implementation finds the actual minimum –
>>> with an
>>> area of 8 (and perimeter of 11.31) - it is POLYGON ((5 2, 3 0, 1 2,
>>> 3 4, 5
>>> 2)) rather than POLYGON((1.4 3.2, 0.6 0.8, 4.2 -0.4,5 2, 1.4 3.2)).
>>>
>>>
>>>
>>> My question is why has this implementation been decided on – is it
>>> just that
>>> MimimumDiameter is already present? Or is there some other reason
>>> due to
>>> some standard?
>>
>> Did you mean to post this to the GEOS mailing lists instead?
>>
>> Anyway, some background from QGIS' perspective. A while ago I was
>> looking for a minimum rect implementation, so ported JTS'
>> implementation over to GEOS. I then exposed this to the QgsGeometry
>> API, but to my suprise found that the results were not ideal. At the
>> time there was some python code in processing which performed a MBR
>> calculation, and I found that the area of rectangles calculated by
>> this python code was smaller then JTS' algorithm. Additionally, I
>> thought it created subjectively 'more aesthetically pleasing'
>> rectangles (when used as atlas feature extents, and also output the
>> angle/width/height of these rectangles (the GEOS implementation
>> doesn't expose this). So I ported the Python code over to c++ as
>> QgsGeometry::orientedMinimumBoundingBox and updated the processing alg
>> to use this c++ method instead. The guts of this algorithm sits in
>> https://github.com/qgis/QGIS/blob/master/src/core/geometry/qgsgeometry.cpp#L890
>>
>> .
>>
>> Does that clarify?
>>
>> Nyall
>> _______________________________________________
>> QGIS-Developer mailing list
>> QGIS-Developer at lists.osgeo.org
>> List info: https://lists.osgeo.org/mailman/listinfo/qgis-developer
>> Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-developer
>>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/qgis-developer/attachments/20170608/6c37af3b/attachment.html>
```