<div dir="ltr"><div>Found a python version here for minimal area enclosing rectangle<br><a href="http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html#minarearect">http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html#minarearect</a><br></div><div>It takes a numpy 2D array as point <br></div><div>That means it is possible to use shapely to read postgis wkb geom, then convert it to numpy and use opencv afterward.<br></div><div><br></div><div>There is also this implementation in python (iterate over all possible edge angle)<br><a href="https://github.com/dbworth/minimum-area-bounding-rectangle/blob/master/python/min_bounding_rect.py">https://github.com/dbworth/minimum-area-bounding-rectangle/blob/master/python/min_bounding_rect.py</a><br><br></div><div>To implement rotating caliper,<br></div><div>I would need some functions like :<br></div><div> - compute robust orientation of an edge (easy)<br></div><div> - loop on points (should be provided)<br></div><div> - area of a rectangle defined by 4 points and 1 angle (=2 caliper sets) (easy)<br><br></div><div>I guess using only the geos_c.h api is not a good solution.<br></div><div>Where should I look in the cpp geos jungle?<br><br></div>Cheers,<br>Rémi-C<br></div><div class="gmail_extra"><br><div class="gmail_quote">2014-10-25 2:23 GMT+02:00 Åsmund Tokheim <span dir="ltr"><<a href="mailto:asmundto@gmail.com" target="_blank">asmundto@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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" target="_blank">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><span class="HOEnZb"><font color="#888888">Åsmund</font></span><div><div class="h5"><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><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" 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></blockquote></div><br></div></div></div></div></div></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>