Many curves and contours are definable by F(X,Y) = 0 with F changing sign on opposite sides of the curve. The following algorithm will draw most such curves more accurately than polygonal approximations and more easily than techniques which search for a "next" X and Y just one move away.
We observe that a good choice of lattice points is just those for which F, when evaluated on one of them, has opposite sign and smaller magnitude than on one or more of its four immediate neighbors. This tends to choose the nearer endpoint of each graph paper line segment which the curve crosses, if near the curve F is monotone with distance from the curve.
First, divide the curve into arcs within which the curve's tangent lies within one 45 degree semiquadrant. We can show that for reasonable F, only two different increments (say north and northwest) are needed to visit the desired points.
Thus, we will be changing one coordinate (incrementing Y) every step, and we have only to check whether changing the other (decrementing X) will reduce the magnitude of F. (If F increases with Y, F(X,Y+1) > -F(X-1,Y+1) means decrement X.) F can often be manipulated so that the inequality simplifies and so that F is easily computed incrementally from X and Y.
As an example, the following computes the first semiquadrant of the circle
2 2 2
F = X + Y - R = 0.
C0: F <- 0, Y <- 0, X <- R
C1: F <- F+2Y+1, Y <- Y+1
C2: if F >= X, F <- F-2X+1, X <- X-1
C3: if Y < X-1, go to C1
C4: (Link to next arc) if Y = X-1, Y <- Y+1, X <- X-1
This can be bummed by maintaining Z = 2Y+1 instead of Y. Symmetry may be used
to compute all eight semiquadrants at once, or the loop may be closed at C2 and
C3 with two PUSHJ's to provide the palindrome of decisions for the first
quadrant. There is an expression for the number of steps per quadrant, but it
has a three-way conditional dependent upon the midpoint geometry. Knowing this
value, however, we can replace C3 and C4 with a simple loop count and an
odd-even test for C4.The loop must be top-tested (C3 before C1) if the "circle" R = 1, with four diagonal segments, is possible.
All this suggests that displays might be designed with an increment mode which accepts bit strings along with declarations of the form: "0 means north, 1 means northwest". 1100 (or 0011) will not occur with a curve of limited curvature; thus, it could be used as an escape code, but this would be an annoying restriction.
See the following illustration of circles drawn this way.
[In case of a tie, i.e., F has equal magnitudes with opposite signs on adjacent points, do not choose both points but rather have some arbitrary yet consistent preference for, say, the outer one. The problem can't arise for C2 in the example because the inequality F >= X is really F > -(F-2X+1) or F > X-.5.]
P(X) Y(Nth derivative) + ..... + Q(X) = R(X)where P, ..... Q, and R are polynomials in X
2 2 2
(for example, Bessel's equation, X Y'' + X Y' + (X - N ) Y = 0)
and A is an algebraic number. Then Y(A) can be evaluated to N places
in time proportional to N(ln N)^3.Further, e^X and ln X or any elementary function can be evaluated to N places in N(ln N)^2 for X a real number. If F(X) can be evaluated in such time, so can the inverse of F(X) (by Newton's method), and the first derivative of F(X). Also, zeta(3) and gamma can be done in N(ln N)^3.
0 1 2 3 4 S A S S Y 0 1 0 2 2stand for the program
T0: ILDB C,A ;C gets next char from pointer in A
T1: CAIE C,"S ;skip if it's an S
JRST T0 ;loop back on failure
ILDB C,A ;next
T2: CAIE C,"A ;skip if A
JRST T1 ;could be an S
ILDB C,A
T3: CAIE C,"S
JRST T0 ;S, A, non S, so start over
ILDB C,A
T4: CAIE C,"S
JRST T2 ;could be SAS.ASSY
ILDB C,A
CAIE C,"Y
JRST T2 ;could be SASS.ASSY
;found SASSY
In other words, a number > 0 in the top row is a location in the program
where the corresponding letter of the middle row is compared with a character
of the input string. If it differs, the number in the bottom row indicates the
location where comparison is to resume. If it matches, the next character of
the middle row is compared with the next character of the input string.
Let J be a number in the to row and K be the number below J, so that TK is the
address field of the Jth JRST. For each J = 1, 2, ... we compute K(J) as
follows: K(1) = 0. Let P be a counter, initially 0. For each succeeding J,
increment P. If the Pth letter = the Jth, K(J) = K(P). Otherwise, K(J) = P,
and P is reset to 0. (P(J) is the largest number such that the first P
characters match the last P character in the first J characters of the sought
string.)
J= 0 1 0 1 2 3 4 5
M I S S I S S I P P I I S S I S S I P P I
K(J)= 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 5 1 0
0 1 2 3 0 1 2 3
C O C A C O L A S A S S A F R A S
0 1 0 2 0 1 3 1 0 1 0 2 1 3 1 1 0
To generalize this method to search for N strings at once, we produce a program
of ILDB-CAIE-JRST's for each of the sought strings, omitting the initial ILDB
from all but the first. We must compute the destination of the Jth JRST in the
Ith program, TKM(I,J), which is the location of the Kth compare in the Mth
program.
It might be reasonable to compile such an instruction sequence whenever a search is initiated, since alternative schemes usually require saving or backing up the character pointer.
The perpendicular distance which the vector C lies from the line connecting the
vectors A and B is just
(C - A) x (B - A)
----------------- ,
2 |A - B|
but maximizing this can lose on very pointy V's. The distance sum hack can
lose on very squashed Z's.