TAOCP 7.1.3 Exercise 185
Let the endpoints be rational numbers (\xi,\eta)=\left(\frac{a}{c},\frac{b}{c}\right), \qquad (\xi',\eta')=\left(\frac{a'}{c'},\frac{b'}{c'}\right), where $a,b,a',b' \in \mathbb{Z}$ and $c,c' \in \mat...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 185. ▶ [23] [23] Design an algorithm that properly digitizes a straight line from (ξ, η) to (ξ′, η′), when ξ, η, ξ′, and η′ are rational numbers, by simplifying Algorithm T.
Verified: yes
Solve time: 1m11s
Solution
Let the endpoints be rational numbers
$$ (\xi,\eta)=\left(\frac{a}{c},\frac{b}{c}\right), \qquad (\xi',\eta')=\left(\frac{a'}{c'},\frac{b'}{c'}\right), $$
where $a,b,a',b' \in \mathbb{Z}$ and $c,c' \in \mathbb{Z}_{>0}$.
Let $d=\operatorname{lcm}(c,c')$. Define integer coordinates
$$ x_0 = d\xi = \frac{da}{c}, \quad y_0 = d\eta = \frac{db}{c}, \quad x_1 = d\xi' = \frac{da'}{c'}, \quad y_1 = d\eta' = \frac{db'}{c'}. $$
These are integers since $c \mid d$ and $c' \mid d$.
Algorithm T constructs digitized points using only integer arithmetic and decisions determined by signs of expressions derived from the quadratic form $Q$. For the line segment case, all decision tests depend on evaluating $Q$ and its linear variants at integer combinations of the current lattice point and the endpoints.
Define a scaled quadratic form
$$ Q_d(x,y)=d^2,Q!\left(\frac{x}{d},\frac{y}{d}\right). $$
Since $Q$ is quadratic, every term in $Q(x/d,y/d)$ is a rational number with denominator dividing $d^2$, hence $Q_d$ is an integer-valued quadratic form on integer arguments. Moreover,
$$ Q(\xi,\eta)=0, \qquad Q(\xi',\eta')=0 $$
implies
$$ Q_d(x_0,y_0)=0, \qquad Q_d(x_1,y_1)=0. $$
Each decision step in Algorithm T depends only on the sign of expressions of the form
$$ Q(u,v), \quad Q(u+\delta_1,v+\delta_2), \quad Q(u+\delta_1',v+\delta_2'), $$
with integer increments $\delta_i \in {0,1}$. After scaling by $d$, these become evaluations of $Q_d$ at integer arguments, and multiplication by the positive constant $d^2$ preserves all sign comparisons.
Run Algorithm T with inputs $(x_0,y_0)$, $(x_1,y_1)$ and quadratic form $Q_d$. Every step produces an integer lattice point $(x,y)$. Mapping back by division by $d$ yields the rational points
$$ \left(\frac{x}{d},\frac{y}{d}\right). $$
Since the ordering of all sign tests is identical to that of the original rational formulation, the sequence of digitized decisions coincides exactly with what Algorithm T would produce on $(\xi,\eta)$ and $(\xi',\eta')$ if all arithmetic were carried out in rational form.
Thus a correct digitization for rational endpoints is obtained by clearing denominators once at the start, applying Algorithm T to the resulting integer data, and scaling the output back by the same factor $d$.
This completes the construction. ∎