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 <[email protected]>: > 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 < > [email protected]> 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 <[email protected] >>> <mailto:[email protected]>>: >>> >>> 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 <[email protected] >>> <mailto:[email protected]>> 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 >>> <[email protected] <mailto:[email protected] >>> >>: >>> >>> 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: [email protected] >>> <mailto:[email protected]> >>> <[email protected] >>> <mailto:[email protected]>> on behalf of >>> Sandro Santilli <[email protected] <mailto:[email protected]>> >>> 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 >>> [email protected] >>> <mailto:[email protected]> >>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis- >>> users >>> _______________________________________________ >>> postgis-users mailing list >>> [email protected] >>> <mailto:[email protected]> >>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis- >>> users >>> >>> >>> >>> _______________________________________________ >>> postgis-users mailing list >>> [email protected] <mailto:postgis-users@lists. >>> osgeo.org> >>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >>> >>> >>> >>> _______________________________________________ >>> postgis-users mailing list >>> [email protected] <mailto:[email protected]> >>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >>> >>> >>> >>> >>> _______________________________________________ >>> postgis-users mailing list >>> [email protected] >>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >>> >>> >> _______________________________________________ >> postgis-users mailing list >> [email protected] >> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >> > > > _______________________________________________ > postgis-users mailing list > [email protected] > http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users >
_______________________________________________ postgis-users mailing list [email protected] http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
