Ticket #3462 (closed defect: fixed)
[PATCH] Two Bugs in Contour Algorithm
|Reported by:||GregersP||Owned by:||chaitanya|
|Severity:||normal||Keywords:||contours, direction, duplicates|
I have found two bugs; one that was always in the contour algorithm, and one which was introduced by my patch from ticket #3129. A further explanation is given below.
Bug 1 - erroneous directions
The bug is in the contour algorithms way to ensure correct direction (my earlier patch from ticket #3129). In my eager to simplify the if statement, I seem to have oversimplified the situation, such that the checks for "left is high side" were not done diagonally - this meant that contour segments which were exactly horizontal or vertical would have arbitrary direction.
This can be solved by expanding the check for "left is high side" to be done using diagonally opposite points.
Basis: When we check the left side for intersection, we know that the top left point will never be the resulting intersection (due to the nature of the comparisons made in the "Intersect" function). The same is true for the starting point of the other sections due to symmetry - i.e. the bottom left point for the bottom section, the bottom right point for the right section, and the top right point for the right section.
So: In the special case of the contour following an edge exactly, we can not use the former checks of two point on the same side, e.g. the top left corner and bottom left corner both being 10.0 meters does not tell us if "left is high side". But if we check diagonally instead (as I did before I oversimplified my patch) the check of bottom left point vs. top right point will give us the correct answer, when check the property for a "left to bottom" contour.
When it comes to a contour from left to right (possibly horizontal), we can use that the top left point will never be on said line (due to symmetry neither will the bottom right point). So we in this case we can still check using two diagonal points.
Bug 2 - duplicate contour segments
During my work on the problem above, I stumbled upon the other bug: When creating contour segments, some are correctly left out due to symmetry conditions. Though, when the contour exactly follows the border of the rectangle (pixel) currently being processed, it is produced for all/any edges. The result is that one will see extra (duplicate) contour segments on top of the "real" contour. This is due to the fact, that only one of the two duals (the "up segment" or the "down segment") will be used when connecting the segments to a single contour.
In the patch attached, I have arbitrarily chosen to exclude those following the left side and the top side.