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
