TITLE: How does the $x/y$ "combined error" variant of Bresenham's line algorithm work?
QUESTION [1 upvotes]: Wikipedia's Bresenham Line Algorithm page lists the following algorithm which works for all directions and slopes of lines:
plotLine(x0, y0, x1, y1)
    dx = abs(x1 - x0)
    sx = x0 < x1 ? 1 : -1
    dy = -abs(y1 - y0)
    sy = y0 < y1 ? 1 : -1
    error = dx + dy
    
    while true
        plot(x0, y0)
        if x0 == x1 && y0 == y1 break
        e2 = 2 * error
        if e2 >= dy
            if x0 == x1 break
            error = error + dy
            x0 = x0 + sx
        end if
        if e2 <= dx
            if y0 == y1 break
            error = error + dx
            y0 = y0 + sy
        end if
    end while

The key benefit of this algorithm over Bresenham's original algorithm is that it works for all slopes and all directions. Bresenham's algorithm worked only for slopes 0..1 and for incrementing X. Additional code is needed for all octants.
The algorithm comes from section 1.3 of this paper. The following seems to be the key insight about this algorithm which I don't understand:

Since a positive gradient is assumed and the error on one side of the
curve will be negative, the equation $e_x ≥ e_{xy} ≥ e_y$ will always be
true which makes it possible to avoid the calculation of the absolute
value for the comparison. The conditions for the increments are now:
if $e_x + e_{xy} > 0$ then increment $x$
if $e_y + e_{xy} < 0$ then increment $y$

Why does $e_x ≥ e_{xy} ≥ e_y $always hold true, and why must the conditions be the ones stated?

REPLY [0 votes]: We have $e_x \ge e_{xy}$ because $P_{xy}$ is right of $P_x$ and $f$ decreases going right. We have $e_{xy} \ge e_y$ because $P_{xy}$ is above $P_y$ and $f$ increases going up.
We check the correctness of the conditions in four cases:

$0 \ge e_x \ge e_{xy} \ge e_y$. Here, we know that $P_x$ is the best point. And indeed, the first condition will fail, the second will pass, we will increment $y$ but not $x$ and end up at $P_x$.
$e_x \ge 0 \ge e_{xy} \ge e_y$. Here, we know $P_y$ is not the best point, so we should increment $y$ (as we do, because the second condition passes). We should increment $x$ as well iff $P_{xy}$ is a better point than $P_x$, which happens iff $e_x > -e_{xy}$, which is equivalent to the first condition.
$e_x \ge e_{xy} \ge 0 \ge e_y$. This is the mirror image of the second case.
$e_x \ge e_{xy} \ge e_y \ge 0$. This is the mirror image of the first case.
{"set_name": "stack_exchange", "score": 1, "question_id": 4432054}