[postgis-users] Oriented BBox Efficient computing?

[Rémi Cura]

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

> 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
>>
>
>
> _______________________________________________
> 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/52cd1bb1/attachment.html>