A first raw plpgsql implementation : "Loop" on all angle from convex hull edge.
https://github.com/Remi-C/PPPP_utilities/blob/master/postgis/rc_oriented_bbox_deom_axis.sql Cheers, Rémi-C 2014-10-25 17:06 GMT+02:00 Rémi Cura <remi.c...@gmail.com>: > Of course I plan to use convex hull, > > I didn't put it because I can call it at plpgsql level so I consider it to > be "free". > > Cheers, > Rémi-C > > 2014-10-25 16:15 GMT+02:00 Åsmund Tokheim <asmun...@gmail.com>: > >> Convex hulls are not only needed as a performance boost. You would need >> some complicated "find next extreme point"-code in order for the algorithm >> to behave correctly as well. >> >> Åsmund >> >> >> On Sat, Oct 25, 2014 at 3:41 PM, Stephen Woodbridge < >> wood...@swoodbridge.com> wrote: >> >>> 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 <asmun...@gmail.com >>>> <mailto:asmun...@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.c...@gmail.com >>>> <mailto:remi.c...@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 >>>> <s...@clevelandmetroparks.com <mailto:svm@ >>>> 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-boun...@lists.osgeo.org >>>> <mailto:postgis-users-boun...@lists.osgeo.org> >>>> <postgis-users-boun...@lists.osgeo.org >>>> <mailto:postgis-users-boun...@lists.osgeo.org>> on behalf >>>> of >>>> Sandro Santilli <s...@keybit.net <mailto:s...@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@lists.osgeo.org >>>> <mailto:postgis-users@lists.osgeo.org> >>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis- >>>> users >>>> _______________________________________________ >>>> postgis-users mailing list >>>> postgis-users@lists.osgeo.org >>>> <mailto:postgis-users@lists.osgeo.org> >>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis- >>>> users >>>> >>>> >>>> >>>> _______________________________________________ >>>> postgis-users mailing list >>>> postgis-users@lists.osgeo.org <mailto:postgis-users@lists. >>>> osgeo.org> >>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >>>> >>>> >>>> >>>> _______________________________________________ >>>> postgis-users mailing list >>>> postgis-users@lists.osgeo.org <mailto:postgis-users@lists.osgeo.org >>>> > >>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >>>> >>>> >>>> >>>> >>>> _______________________________________________ >>>> postgis-users mailing list >>>> postgis-users@lists.osgeo.org >>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >>>> >>>> >>> _______________________________________________ >>> postgis-users mailing list >>> postgis-users@lists.osgeo.org >>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >>> >> >> >> _______________________________________________ >> postgis-users mailing list >> postgis-users@lists.osgeo.org >> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >> > >
_______________________________________________ postgis-users mailing list postgis-users@lists.osgeo.org http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users