[postgis-users] Oriented BBox Efficient computing?
Åsmund Tokheim
asmundto at gmail.com
Sat Oct 25 07:15:35 PDT 2014
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>
More information about the postgis-users
mailing list