<div dir="ltr">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 <a href="http://cgm.cs.mcgill.ca/~orm/rotcal.html">http://cgm.cs.mcgill.ca/~orm/rotcal.html</a>, it seems like you can make the following assumptions:<div><br></div><div>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<br><div><br></div><div>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.</div><div><br></div><div>Regards</div><div>Åsmund<br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Oct 24, 2014 at 7:09 PM, Rémi Cura <span dir="ltr"><<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div>Ok if I understand right, <br></div>implementing it at the sql level would be :<br></div><br> - compute convex envelop<br></div> - order edges by angle<br></div><div> - round angle to a given precision, keep distinct values<br></div> - for each angle, rotate and compute bbox and area<br></div><br>keep bbox and rotation giving the min area.<br><br>Cheers,<br>Rémi-C<br></div><div class="gmail_extra"><br><div class="gmail_quote">2014-10-23 18:46 GMT+02:00 Stephen V. Mather <span dir="ltr"><<a href="mailto:svm@clevelandmetroparks.com" target="_blank">svm@clevelandmetroparks.com</a>></span>:<div><div class="h5"><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">That would be really cool. Could be a set of functions. It would be interesting to see if the triangulation optimizations listed at <a href="http://cgm.cs.mcgill.ca/~orm/rotcal.html" target="_blank">http://cgm.cs.mcgill.ca/~orm/rotcal.html</a> are faster than the JTS/GEOS equivalents.<br>
<br>
  Stephen V. Mather<br>
GIS Manager<br>
<a href="tel:%28216%29%20635-3243" value="+12166353243" target="_blank">(216) 635-3243</a> (Work)<br>
<a href="http://clevelandmetroparks.com" target="_blank">clevelandmetroparks.com</a><br>
<br>
<br>
<br>
<br>
________________________________________<br>
From: <a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">postgis-users-bounces@lists.osgeo.org</a> <<a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">postgis-users-bounces@lists.osgeo.org</a>> on behalf of Sandro Santilli <<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a>><br>
Sent: Thursday, October 23, 2014 12:36 PM<br>
To: PostGIS Users Discussion<br>
Subject: Re: [postgis-users] Oriented BBox Efficient computing?<br>
<div><div><br>
On Thu, Oct 23, 2014 at 06:17:56PM +0200, Rémi Cura wrote:<br>
> Wov thanks everybody :<br>
> Seems it possible to do it fully geometrically :<br>
> <a href="http://cgm.cs.mcgill.ca/~orm/rotcal.html" target="_blank">http://cgm.cs.mcgill.ca/~orm/rotcal.html</a><br>
<br>
Nice, would be a good candidate for a new PostGIS function<br>
(possibly via JTS/GEOS)<br>
<br>
--strk;<br>
<br>
  ()   Free GIS & Flash consultant/developer<br>
  /\   <a href="http://strk.keybit.net/services.html" target="_blank">http://strk.keybit.net/services.html</a><br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><br>
</div></div></blockquote></div></div></div><br></div>
<br>_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><br></blockquote></div><br></div></div></div></div>