gdal_contour generates incorrect oriented contour lines

[schmitzu]

In some very rare cases I get contour lines from gdal_contour which are reversed in respect of the rule 'right is high'. Since the input data is too large to post it here (and all efforts in reducing it ends in the absent of the problem) I've tried to find it myself.

The problem resides in the Method GDALContourItem::Merge (alg/contour.cpp). It tries to merge two contour polygons of same level into one. Checks are are done to find the right order of chaining the two coordinate list. Four consecutive if-clauses try to detect if start or end of the first matches start or end of the second polygon. The first match is taken and the polygons are merged. The match is calculated by having a difference of X and Y coordinates less than JOIN_LENGTH. And that's the crux: What happens if one segment is very small, say smaller than JOIN_LENGTH? All four cases (or to be precise: if-expressions) may match and thus always the first if-branch will be taken... and can be wrong by a chance of 50%. Since the bLeftIsHigh flag is not further taken into account, this may lead to an incorrect oriented contour line.

I've written a patch in which I determine the merge case in an extra method. The distance between all four variants (this.start-poOther.end, this.end-poOther.start ... etc.) is calculated an the minimum case if choosen if it is smaller than JOIN_LENGTH. Of course this takes more time than the actual method, but it eliminates the error. The aforementioned contour line now has the right direction. May be it's possible to optimize this further or someone finds a better approaches. Anyhow, I attach the patch to this report.

I can provide test data if required, but can't get it below 30MB.

[Even Rouault]

In 34471:

GDAL contour: fix incorrect oriented contour lines in some rare cases (patch by schmitzu, fixes #6563)

[Even Rouault]

In 34472:

GDAL contour: fix incorrect oriented contour lines in some rare cases (patch by schmitzu, fixes #6563)

[Even Rouault]

Although I'm not a specialist of this algorithm, your changes look good, so I've merged them with some minor formatting changes. Thanks