[postgis-users] Oriented BBox Efficient computing?

Rémi Cura remi.cura at gmail.com
Thu Oct 30 12:13:21 PDT 2014 

A first raw plpgsql implementation :

"Loop" on all angle from convex hull edge.

https://github.com/Remi-C/PPPP_utilities/blob/master/postgis/rc_oriented_bbox_deom_axis.sql

Cheers,

Rémi-C

2014-10-25 17:06 GMT+02:00 Rémi Cura <remi.cura at gmail.com>:

> Of course I plan to use convex hull,
>
> I didn't put it because I can call it at plpgsql level so I consider it to
> be "free".
>
> Cheers,
> Rémi-C
>
> 2014-10-25 16:15 GMT+02:00 Åsmund Tokheim <asmundto at gmail.com>:
>
>> 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@
>>>> 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
>>>
>>
>>
>> _______________________________________________
>> 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/20141030/7eb49772/attachment.html>

More information about the postgis-users mailing list