[postgis-users] Oriented BBox Efficient computing?

[Åsmund Tokheim]

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, 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> 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>
> :
>
> 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 are faster than the JTS/GEOS
>> equivalents.
>>
>>   Stephen V. Mather
>> GIS Manager
>> (216) 635-3243 (Work)
>> clevelandmetroparks.com
>>
>>
>>
>>
>> ________________________________________
>> From: postgis-users-bounces at lists.osgeo.org <
>> postgis-users-bounces at lists.osgeo.org> on behalf of Sandro Santilli <
>> 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
>>
>> 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
>> 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/e30304c4/attachment.html>