[QGIS-Developer] MinimumRectangle implementation

[Havard Tveite]

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
> 

-- 
Håvard Tveite
Faculty of Sciences and Technology, NMBU
Drøbakveien 31, POBox 5003, N-1432 Ås, NORWAY
Phone: +47 67231548   Web: http://www.nmbu.no