[postgis-users] Oriented BBox Efficient computing?
Rémi Cura
remi.cura at gmail.com
Sat Oct 25 08:06:43 PDT 2014
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 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
>>
>
>
> _______________________________________________
> 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/5fedf71a/attachment.html>
More information about the postgis-users
mailing list