[postgis-users] Oriented BBox Efficient computing?

[Stephen Woodbridge]

And if you do that on the convex hull rather than the original geometry, 
you will have less points to consider while doing the evaluation.

-Steve

On 10/25/2014 8:52 AM, Rémi Cura wrote:
> Found a python version here for minimal area enclosing rectangle
> http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html#minarearect
> It takes a numpy 2D array as point
> That means it is possible to use shapely to read postgis wkb geom, then
> convert it to numpy and use opencv afterward.
>
> There is also this implementation in python (iterate over all possible
> edge angle)
> https://github.com/dbworth/minimum-area-bounding-rectangle/blob/master/python/min_bounding_rect.py
>
> To implement rotating caliper,
> I would need some functions like :
>   - compute robust orientation of an edge (easy)
>   - loop on points (should be provided)
>   - area of a rectangle defined by 4 points and 1 angle (=2 caliper
> sets) (easy)
>
> I guess using only the geos_c.h api is not a good solution.
> Where should I look in the cpp geos jungle?
>
> Cheers,
> Rémi-C
>
> 2014-10-25 2:23 GMT+02:00 Åsmund Tokheim <asmundto at gmail.com
> <mailto:asmundto at gmail.com>>:
>
>     As far as I can tell, you shouldn't order and rotate, or you'll be
>     looking at a O(n^2) implementation. During an iteration of
>     http://cgm.cs.mcgill.ca/~orm/rotcal.html
>     <http://cgm.cs.mcgill.ca/%7Eorm/rotcal.html>, it seems like you can
>     make the following assumptions:
>
>     The next angle you should rotate to will be one of the four angles,
>     given by the current extreme points and their next clockwise
>     neighbour. So you should be able to find the next minimum clockwise
>     rotation in O(1) time
>
>     Also whenever you do a clockwise rotation to orient one of the
>     support lines along a new edge, the extreme points for the other
>     support lines stay the same. You only need to update the extreme
>     point that was on the edge we now use as a support line, to its next
>     clockwise point. Using the new extreme points and caliper's angle,
>     you can calculate the bbox area in O(1) time as well.
>
>     Regards
>     Åsmund
>
>
>     On Fri, Oct 24, 2014 at 7:09 PM, Rémi Cura <remi.cura at gmail.com
>     <mailto:remi.cura at gmail.com>> wrote:
>
>         Ok if I understand right,
>         implementing it at the sql level would be :
>
>           - compute convex envelop
>           - order edges by angle
>           - round angle to a given precision, keep distinct values
>           - for each angle, rotate and compute bbox and area
>
>         keep bbox and rotation giving the min area.
>
>         Cheers,
>         Rémi-C
>
>         2014-10-23 18:46 GMT+02:00 Stephen V. Mather
>         <svm at clevelandmetroparks.com <mailto:svm at clevelandmetroparks.com>>:
>
>             That would be really cool. Could be a set of functions. It
>             would be interesting to see if the triangulation
>             optimizations listed at
>             http://cgm.cs.mcgill.ca/~orm/rotcal.html
>             <http://cgm.cs.mcgill.ca/%7Eorm/rotcal.html> are faster than
>             the JTS/GEOS equivalents.
>
>                Stephen V. Mather
>             GIS Manager
>             (216) 635-3243 <tel:%28216%29%20635-3243> (Work)
>             clevelandmetroparks.com <http://clevelandmetroparks.com>
>
>
>
>
>             ________________________________________
>             From: postgis-users-bounces at lists.osgeo.org
>             <mailto:postgis-users-bounces at lists.osgeo.org>
>             <postgis-users-bounces at lists.osgeo.org
>             <mailto:postgis-users-bounces at lists.osgeo.org>> on behalf of
>             Sandro Santilli <strk at keybit.net <mailto:strk at keybit.net>>
>             Sent: Thursday, October 23, 2014 12:36 PM
>             To: PostGIS Users Discussion
>             Subject: Re: [postgis-users] Oriented BBox Efficient computing?
>
>             On Thu, Oct 23, 2014 at 06:17:56PM +0200, Rémi Cura wrote:
>              > Wov thanks everybody :
>              > Seems it possible to do it fully geometrically :
>              > http://cgm.cs.mcgill.ca/~orm/rotcal.html
>             <http://cgm.cs.mcgill.ca/%7Eorm/rotcal.html>
>
>             Nice, would be a good candidate for a new PostGIS function
>             (possibly via JTS/GEOS)
>
>             --strk;
>
>                ()   Free GIS & Flash consultant/developer
>                /\ http://strk.keybit.net/services.html
>             _______________________________________________
>             postgis-users mailing list
>             postgis-users at lists.osgeo.org
>             <mailto:postgis-users at lists.osgeo.org>
>             http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>             _______________________________________________
>             postgis-users mailing list
>             postgis-users at lists.osgeo.org
>             <mailto:postgis-users at lists.osgeo.org>
>             http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>
>
>
>         _______________________________________________
>         postgis-users mailing list
>         postgis-users at lists.osgeo.org <mailto:postgis-users at lists.osgeo.org>
>         http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>
>
>
>     _______________________________________________
>     postgis-users mailing list
>     postgis-users at lists.osgeo.org <mailto:postgis-users at lists.osgeo.org>
>     http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>
>
>
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>