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:[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]
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
