<div dir="ltr"><div><div>A first raw plpgsql implementation :<br><br>"Loop" on all angle from convex hull edge.<br><br><a href="https://github.com/Remi-C/PPPP_utilities/blob/master/postgis/rc_oriented_bbox_deom_axis.sql">https://github.com/Remi-C/PPPP_utilities/blob/master/postgis/rc_oriented_bbox_deom_axis.sql</a><br><br></div>Cheers,<br><br></div>Rémi-C<br></div><div class="gmail_extra"><br><div class="gmail_quote">2014-10-25 17:06 GMT+02:00 Rémi Cura <span dir="ltr"><<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@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"><div>Of course I plan to use convex hull,<br></div><br>I didn't put it because I can call it at plpgsql level so I consider it to be "free".<br><br>Cheers,<br>Rémi-C<br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">2014-10-25 16:15 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">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.<span><font color="#888888"><div><br></div></font></span><div><span><font color="#888888">Åsmund</font></span><div><div><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Oct 25, 2014 at 3:41 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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.<br>
<br>
-Steve<span><br>
<br>
On 10/25/2014 8:52 AM, Rémi Cura wrote:<br>
</span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>
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" target="_blank">http://docs.opencv.org/<u></u>modules/imgproc/doc/<u></u>structural_analysis_and_shape_<u></u>descriptors.html#minarearect</a><br>
It takes a numpy 2D array as point<br>
That means it is possible to use shapely to read postgis wkb geom, then<br>
convert it to numpy and use opencv afterward.<br>
<br>
There is also this implementation in python (iterate over all possible<br>
edge angle)<br>
<a href="https://github.com/dbworth/minimum-area-bounding-rectangle/blob/master/python/min_bounding_rect.py" target="_blank">https://github.com/dbworth/<u></u>minimum-area-bounding-<u></u>rectangle/blob/master/python/<u></u>min_bounding_rect.py</a><br>
<br>
To implement rotating caliper,<br>
I would need some functions like :<br>
- compute robust orientation of an edge (easy)<br>
- loop on points (should be provided)<br>
- area of a rectangle defined by 4 points and 1 angle (=2 caliper<br>
sets) (easy)<br>
<br>
I guess using only the geos_c.h api is not a good solution.<br>
Where should I look in the cpp geos jungle?<br>
<br>
Cheers,<br>
Rémi-C<br>
<br>
2014-10-25 2:23 GMT+02:00 Åsmund Tokheim <<a href="mailto:asmundto@gmail.com" target="_blank">asmundto@gmail.com</a><br></span>
<mailto:<a href="mailto:asmundto@gmail.com" target="_blank">asmundto@gmail.com</a>>>:<span><br>
<br>
As far as I can tell, you shouldn't order and rotate, or you'll be<br>
looking at a O(n^2) implementation. During an iteration of<br>
<a href="http://cgm.cs.mcgill.ca/~orm/rotcal.html" target="_blank">http://cgm.cs.mcgill.ca/~orm/<u></u>rotcal.html</a><br></span>
<<a href="http://cgm.cs.mcgill.ca/%7Eorm/rotcal.html" target="_blank">http://cgm.cs.mcgill.ca/%<u></u>7Eorm/rotcal.html</a>>, it seems like you can<span><br>
make the following assumptions:<br>
<br>
The next angle you should rotate to will be one of the four angles,<br>
given by the current extreme points and their next clockwise<br>
neighbour. So you should be able to find the next minimum clockwise<br>
rotation in O(1) time<br>
<br>
Also whenever you do a clockwise rotation to orient one of the<br>
support lines along a new edge, the extreme points for the other<br>
support lines stay the same. You only need to update the extreme<br>
point that was on the edge we now use as a support line, to its next<br>
clockwise point. Using the new extreme points and caliper's angle,<br>
you can calculate the bbox area in O(1) time as well.<br>
<br>
Regards<br>
Åsmund<br>
<br>
<br>
On Fri, Oct 24, 2014 at 7:09 PM, Rémi Cura <<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a><br></span><span>
<mailto:<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>>> wrote:<br>
<br>
Ok if I understand right,<br>
implementing it at the sql level would be :<br>
<br>
- compute convex envelop<br>
- order edges by angle<br>
- round angle to a given precision, keep distinct values<br>
- for each angle, rotate and compute bbox and area<br>
<br>
keep bbox and rotation giving the min area.<br>
<br>
Cheers,<br>
Rémi-C<br>
<br>
2014-10-23 18:46 GMT+02:00 Stephen V. Mather<br></span>
<<a href="mailto:svm@clevelandmetroparks.com" target="_blank">svm@clevelandmetroparks.com</a> <mailto:<a href="mailto:svm@clevelandmetroparks.com" target="_blank">svm@<u></u>clevelandmetroparks.com</a>>>:<span><br>
<br>
That would be really cool. Could be a set of functions. It<br>
would be interesting to see if the triangulation<br>
optimizations listed at<br>
<a href="http://cgm.cs.mcgill.ca/~orm/rotcal.html" target="_blank">http://cgm.cs.mcgill.ca/~orm/<u></u>rotcal.html</a><br></span>
<<a href="http://cgm.cs.mcgill.ca/%7Eorm/rotcal.html" target="_blank">http://cgm.cs.mcgill.ca/%<u></u>7Eorm/rotcal.html</a>> are faster than<span><br>
the JTS/GEOS equivalents.<br>
<br>
Stephen V. Mather<br>
GIS Manager<br></span>
<a href="tel:%28216%29%20635-3243" value="+12166353243" target="_blank">(216) 635-3243</a> <tel:%28216%29%20635-3243> (Work)<br>
<a href="http://clevelandmetroparks.com" target="_blank">clevelandmetroparks.com</a> <<a href="http://clevelandmetroparks.com" target="_blank">http://clevelandmetroparks.<u></u>com</a>><br>
<br>
<br>
<br>
<br>
______________________________<u></u>__________<br>
From: <a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">postgis-users-bounces@lists.<u></u>osgeo.org</a><br>
<mailto:<a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">postgis-users-bounces@<u></u>lists.osgeo.org</a>><br>
<<a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">postgis-users-bounces@lists.<u></u>osgeo.org</a><br>
<mailto:<a href="mailto:postgis-users-bounces@lists.osgeo.org" target="_blank">postgis-users-bounces@<u></u>lists.osgeo.org</a>>> on behalf of<br>
Sandro Santilli <<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a> <mailto:<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a>>><span><br>
Sent: Thursday, October 23, 2014 12:36 PM<br>
To: PostGIS Users Discussion<br>
Subject: Re: [postgis-users] Oriented BBox Efficient computing?<br>
<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/<u></u>rotcal.html</a><br></span>
<<a href="http://cgm.cs.mcgill.ca/%7Eorm/rotcal.html" target="_blank">http://cgm.cs.mcgill.ca/%<u></u>7Eorm/rotcal.html</a>><span><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/<u></u>services.html</a><br>
______________________________<u></u>_________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br></span>
<mailto:<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.<u></u>osgeo.org</a>><span><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
______________________________<u></u>_________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br></span>
<mailto:<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.<u></u>osgeo.org</a>><span><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
postgis-users mailing list<br></span>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a> <mailto:<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.<u></u>osgeo.org</a>><span><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
postgis-users mailing list<br></span>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a> <mailto:<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.<u></u>osgeo.org</a>><span><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<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-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
<br>
</span></blockquote><div><div>
<br>
______________________________<u></u>_________________<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-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
</div></div></blockquote></div><br></div></div></div></div></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></blockquote></div><br></div>