The verifier can check the final geometric criterion directly, independently of the incremental decision variable. Set , , and define the scaled vertical residualThe exact line ordinate is , so . Nearest-integer selection with upward ties is preciselyThe strictness matters: at a half-integer ordinate the upper pixel has and passes, whereas the lower pixel has and fails. Each column has exactly one accepted integer ordinate.
With
reject() terminating verification unsuccessfully, suitable outline code is:void checkPoint(int x, int y)
{
Wide a = Wide(x) - x0;
if (a < 0) reject(); // inequality 1
Wide b = Wide(x1) - x;
if (b < 0) reject(); // inequality 2
Wide dx = Wide(x1) - x0;
Wide dy = Wide(y1) - y0;
Wide e = 2 * dy * a - 2 * dx * (Wide(y) - y0);
Wide lower = e + dx;
if (lower < 0) reject(); // inequality 3
Wide upper = dx - e;
if (upper <= 0) reject(); // inequality 4
counter[x]++;
}Wide denotes a signed integer type large enough for the products and differences, with conversion before subtraction. These are exactly four inequalities against zero, all applied to named integer variables. The arithmetic restriction on the drawing loop in part (c) does not restrict multiplication in this verifier. The screen endpoints are assumed valid, with and valid endpoint ordinates, so indexing is safe after the first two checks. These endpoint and screen preconditions belong in initialization if they are not guaranteed by the caller.No separate -range tests are needed: for between the endpoints, lies in , and its nearest integer lies in the same interval because both bounds are integers. The counters defer detection of omissions and repetitions to part (e). As for every finite counter, use adequate capacity or a sticky failure on overflow; saturating each counter at two also suffices because only zero, one, and “more than one” matter.
Articles by others on the same topic
There are currently no matching articles.