[postgis-devel] Could patch in #810 be applied?

Peter Hopfgartner peter.hopfgartner at r3-gis.com
Tue Feb 1 08:26:13 PST 2011


The algorithm used in PostGIS is basically the http://en.wikipedia.org/wiki/Shoelace_formula.

>From a pure math point of view, the result should not depend from the choice of the origin. Passing from pure math to floating point numerics, the idea is to keep the coordinates as low as possible.
Numerically, it would be even better to put the origin more central to the polygon, I would guess to put it to the center of mass, but this would require to loop twice through the verteces.
Another small improvement might be get from rearranging the terms in the sum, from:

for (j=0; j<ring->npoints-1; j++)
{
    getPoint2d_p(ring, j, &p1);
    getPoint2d_p(ring, j+1, &p2);
    ringarea += ( p1.x * p2.y ) - ( p1.y * p2.x );
}

to:

for (j=0; j<ring->npoints-1; j++)
{
    int prev, next;

    if (j = 0)
        prev = ring->npoints-1;
    else
        prev = j-1;

    if (j = ring->npoints-1)
        next = 0;
    else
        next = j+1;

    getPoint2d_p(ring, prev, &p0);
    getPoint2d_p(ring, j, &p1);
    getPoint2d_p(ring, next, &p2);
    ringarea += p1.x * (p2.y - p0.y);
}

I would expect this improvement from the fact, since, if (p0.y - p2.y) is in average smaller then p.x, then  numerically p.x * (p0.y - p2.y) would a better approximation then p.x*p0.y - p.x*p2.y.
Furthermore, this second variant would have only half the multiplications.
In case, I can try to perform some test on this wild theory.

Peter Hopfgartner
 
R3 GIS Srl - GmbH
http://www.r3-gis.com


--------Mark Cave-Ayland <mark.cave-ayland at siriusit.co.uk> wrote--------
Subject: Re: [postgis-devel] Could patch in #810 be applied?
Date: 01.02.2011 16:50

>On 01/02/11 10:17, Peter Hopfgartner wrote:
>
>> We use internally the patch in http://trac.osgeo.org/postgis/ticket/810
>and are quite happy with the improvement.
>> Could it be applied? I can provide a version for trunk, too.
>>
>> Peter Hopfgartner
>
>Hmmmm so it looks as if it is just shifting the origin from (0 0) to the 
>first vertex (and hence allows an increase in precision in these cases?).
>
>I think the comment needs to be expanded more, but I don't see an issue 
>with the overall approach. Perhaps more a candidate for trunk rather 
>than 1.5 though as it will potentially change the regression test output 
>and real calculation results.
>
>
>ATB,
>
>Mark.
>
>-- 
>Mark Cave-Ayland - Senior Technical Architect
>PostgreSQL - PostGIS
>Sirius Corporation plc - control through freedom
>http://www.siriusit.co.uk
>t: +44 870 608 0063
>
>Sirius Labs: http://www.siriusit.co.uk/labs
>




More information about the postgis-devel mailing list