# Polarized Raster Ling Algorithm Introduction

Original Publication Date: 1993-Sep-01

Included in the Prior Art Database: 2005-Mar-20

## Publishing Venue

IBM

## Related People

## Abstract

A raster line drawing algorithm involves the determination of the pixels to be turned on in a raster display system when drawing a line from (a0, b0) to (a1, b1). Fig. 1 shows a line and the discrete pixel approximation of the line by the [*] algorithm. The constraint used by this algorithm is that the raster line minimizes the mean squared distance error between the ideal line and the discrete line. While the above constraint is the best in many cases, sometimes it is necessary for the line to be polarized, i.e., represented in the discrete pixel space as shown in Fig. 2 or as shown in Fig. 3. For example while drawing a hollow polygon, the user might want all pixels for the edges to be inside the polygon, i.e.

**This text was extracted from an ASCII text file.**

**This is the abbreviated version, containing approximately 48% of the total text.**

Polarized Raster Ling Algorithm Introduction

A raster line
drawing algorithm involves the determination of

the pixels to be turned on in a raster display system when drawing a

line from (a0, b0) to (a1, b1). Fig. 1
shows a line and the discrete

pixel approximation of the line by the [*] algorithm. The constraint

used by this algorithm is that the raster line minimizes the mean

squared distance error between the ideal line and the discrete line.

While the above constraint is the best in many cases, sometimes it is

necessary for the line to be polarized, i.e., represented in the

discrete pixel space as shown in Fig. 2 or as shown in Fig. 3. For

example while drawing a hollow polygon, the user might want all

pixels for the edges to be inside the polygon, i.e., the pixels

should be to the left of each edge in the polygon when the vertices

of the polygon are specified in counterclockwise order. In Fig. 2

all pixels chosen to represent the line are to either on the line or

to its right, i.e., the line is "right polarized" as seen by a viewer

walking along the edge from the starting point to the ending point.

Similarly in Fig. 3 all pixels chosen to represent the line are

either on it or to its left, i.e., the line is "left polarized" as

seen by a viewer walking along the edge from the starting point to

the ending point. All arithmetic
operations and variables used in

this algorithm are in the integer domain.
The following definitions

will be used in the description of the algorithm.

(x0, y0) =
starting point of line

(x1, y1) = ending point of line

delta_x = x1 - x0

delta_y = y1 - y0

|x| = absolute value of x

|delta_x| >= |delta_y|
and delta_x * delta_y >= 0

other cases solved by symmetry

Fig. 1 shows a raster line through (x0, y0) = start point
and (x1,

y1) = end point. The equation of this
line is

(y - y0)/(x - x0) = delta_y/delta_x

=> x * delta_y - y * delta_x
+ x1 * y0 - x0 * y1 = 0

Let F(x, y) = 2(x delta_y - y delta_x + x1 y0 - x0
y1). F(x, y) = 0

represents the line. When delta_x >
0, F(x, y) < 0 for the region

above the line and F(x, y) > 0 for the region below the line (Fig.

4). An error term "e"
represents twice the signed distance between

the line and the midpoint between the two candidate pixels to be

chosen next. At the start of the
algorithm, the two pixels that may

be chosen next are (x0 + sign(delta_x), y0) and (x0 + sign(delta_x),

y0 + sign(delta_y)), where "sign" is the sign function:

sign (x) =
1 if x > 0

0 if x = 0

-1 if x < 0

The midpoint between the next two candidates is (x0 +
sign(delta_x),

y0 + sign(delta_y)/2). Therefore, the
starting value for "e" is

given by

e = F (x0 + sign(delta_x), y0 + sign(delta_y)/2)

=
2*(sign(delta_y)*delta_y...