pack: fix 0-case in implementation of Brensenham’s algorithm
Graphics Gems I §II.8 gives the definition of the sgn
function as:
function sgn (x: int) : int;
begin return if x > 0 then 1 else –1; endfunc;
Its reference code appears to have incorrectly implemented this as:
/* take binary sign of a, either -1, or 1 if >= 0 */
#define SGN(a) (((a)<0) ? -1 : 0)
The errata following the first edition notes a bug with this:
Serious errors (ones your compiler cannot or may not catch):
p. 630: …
Change SGN macro to (i.e. change positive condition result to "1"):
#define SGN(a) (((a)<0) ? -1 : 1)
This corrected version seems to have been copied into Graphviz. However neither
Graphviz developers nor the Graphics Gems editors seemed to notice that the
corrected macro still does not correctly implement the pseudocode it corresponds
to. In the x == 0
case, the pseudocode returns -1 while the macro was
returning 1.
A comment in lib/dotgen/compound.c suggests that developers may have been seeing symptoms of this but did not identify the root cause:
/* The following functions are derived from pp. 411-415 (pp. 791-795)
* of Graphics Gems. In the code there, they use a SGN function to
* count crossings. This doesn't seem to handle certain special cases,
* as when the last point is on the line. It certainly didn't work
* for us when we used int values; see bug 145. We needed to use CMP instead.