Problem with RingExtent::calculate in shape2ogr.cpp

[bpeschel]

I am using code from shape2ogr.cpp to determine outer/inner rings and their association. The method RingExtent::calculate() is used to find the max and min of the object. This is used later to check if the inner rings are contained by the inner.

However, the code has a bug in it:

void RingExtent::calculate( int ringParts, double *ringX, double *ringY )
{
    empty = ringParts <= 0;
    if ( !empty )
    {
        xMin = xMax = *ringX;
        yMin = yMax = *ringY;
        while( --ringParts > 0 )
        {
            if ( xMin > *ringX )
                xMin = *ringX;
            else if ( xMax < *ringX )
                xMax = *ringX;
            if ( yMin > *ringY )
               yMin = *ringY;
            else if ( yMax < *ringY )
                yMax = *ringY;
            ++ringX;
            ++ringY;
        }
    }
}

The problem is in the while loop. Because SHPReadOGRObject() calls this by:

 int start = 0;
 int end = 0;
 RingStartEnd ( psShape, iRing, &start, &end );
 extents[ iRing ].calculate( end-start, psShape->padfX + start, psShape->padfY + start );

So, if the ring has 4 points (causing 5 in the shape file because the first and last must be repeated), start would be 0 and end would be 4. So, the loop will evaluate points 0, 1, and 2 skipping the fourth point. If that point happens to be a max or min, the later calculations will not be correct.

It appears this can be fixed by changing

while( --ringParts > 0 )

to

while( ringParts-- > 0 )

at least in my limited testing.

If I can attach a file after submission, I will attach a shapefile set that proves this.

[bpeschel]

The problem manifests in the second ring of shape 3 and the ring in shape 4

[Even Rouault]

I share bpeschel's analysis. My suggestion for a fix would be to increment ringX and ringY before the loop. bpeschel's fix would work too, but would go on doing an extra first loop that does nothing.

void RingExtent::calculate( int ringParts, double *ringX, double *ringY )
{
    empty = ringParts <= 0;
    if ( !empty )
    {
        xMin = xMax = *ringX;
        yMin = yMax = *ringY;
        ++ringX; // FIX
        ++ringY; // FIX
        while( --ringParts > 0 )
        {
            if ( xMin > *ringX )
                xMin = *ringX;
            else if ( xMax < *ringX )
                xMax = *ringX;
            if ( yMin > *ringY )
               yMin = *ringY;
            else if ( yMax < *ringY )
                yMax = *ringY;
            ++ringX;
            ++ringY;
        }
    }
}

I also want to outline that since my fix for bug #1217, RingExtent::calculate is not called anymore in trunk (since r13551) and in branches/1.5 (since r13553). The old code that classified multipolygons is still there, but it's dead.

[Even Rouault]

In tunk, in r13599, I've removed in the SHAPE driver the unused old classification code for multipolygons. So the bug outlined by bpeschel is obsolete. It's also obsolete in branches/1.5 as the function is unused since r13553.