[postgis-users] Oriented BBox Efficient computing?

[Åsmund Tokheim]

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 <woodbri at swoodbridge.com
> 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 <asmundto at gmail.com
>> <mailto:asmundto at gmail.com>>:
>>
>>     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 <remi.cura at gmail.com
>>     <mailto:remi.cura at gmail.com>> 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
>>         <svm at clevelandmetroparks.com <mailto:svm at clevelandmetroparks.com
>> >>:
>>
>>             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: postgis-users-bounces at lists.osgeo.org
>>             <mailto:postgis-users-bounces at lists.osgeo.org>
>>             <postgis-users-bounces at lists.osgeo.org
>>             <mailto:postgis-users-bounces at lists.osgeo.org>> on behalf of
>>             Sandro Santilli <strk at keybit.net <mailto:strk at keybit.net>>
>>             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
>>             postgis-users at lists.osgeo.org
>>             <mailto:postgis-users at lists.osgeo.org>
>>             http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>             _______________________________________________
>>             postgis-users mailing list
>>             postgis-users at lists.osgeo.org
>>             <mailto:postgis-users at lists.osgeo.org>
>>             http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>
>>
>>
>>         _______________________________________________
>>         postgis-users mailing list
>>         postgis-users at lists.osgeo.org <mailto:postgis-users at lists.
>> osgeo.org>
>>         http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>
>>
>>
>>     _______________________________________________
>>     postgis-users mailing list
>>     postgis-users at lists.osgeo.org <mailto:postgis-users at lists.osgeo.org>
>>     http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>
>>
>>
>>
>> _______________________________________________
>> postgis-users mailing list
>> postgis-users at lists.osgeo.org
>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>
>>
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20141025/256b46dd/attachment.html>