ABSTRACT
DSLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.2 Iterative Refinement: An Algebraic Characterization . . . . . . . . . . . 98
3.2.1 Gradient and Intercept Estimation . . . . . . . . . . . . . . . . . . . . . . 98 3.2.2 Reconstruction of a DSLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.2.3 Computation of Precise Domain of a DSLS . . . . . . . . . . . . . 102 3.2.4 Speed and Convergence of Iterative Refinement . . . . . . . . 106 3.2.5 Length Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
3.2.5.1 (n)-characterization [76, 79] . . . . . . . . . . . . . . . 109 3.2.5.2 (ne, no)-characterization [76, 79] . . . . . . . . . . . 109 3.2.5.3 (n, q, p, s)-characterization [76, 79] . . . . . . . . . 109
3.3 Three-Dimensional Digital Straight Line Segments . . . . . . . . . . . . . 109 3.3.1 Geometric Preliminaries, Digitization, and
Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.3.1.1 Digitization of a 3-D Line Segment . . . . . . . . 112 3.3.1.2 Characterization of a 3-D DSLS . . . . . . . . . . . 113
3.3.2 Characterization of Chain Codes of 3-D DSLS . . . . . . . . . 113 3.3.2.1 n-characterization . . . . . . . . . . . . . . . . . . . . . . . . . . 114 3.3.2.2 (n, no1, no2)-characterization . . . . . . . . . . . . . . . 114 3.3.2.3 (n, no1, nc1, no2, nc2)-characterization . . . . . . 114 3.3.2.4 (n, q1, p1, s1, q2, p2, s2)-characterization . . . . 114
3.3.3 Length Estimators for Different Characterizations . . . . . 114 3.3.3.1 (n)-characterization [39] . . . . . . . . . . . . . . . . . . . 115 3.3.3.2 (n, no1, no2)-characterization [39] . . . . . . . . . . 116 3.3.3.3 (n, no1, nc1, no2, nc2)-characterization [39] . 116 3.3.3.4 (n, q1, p1, s1, q2, p2, s2)-characterization . . . . 116
3.4 Digital Plane Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 3.4.1 Digitization and Netcode Representation . . . . . . . . . . . . . . 117 3.4.2 Geometric Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 3.4.3 Characterization by Convex Hull Separability . . . . . . . . . . 120 3.4.4 Area Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.4.4.1 n2-characterization . . . . . . . . . . . . . . . . . . . . . . . . . 123 3.4.4.2 (n1, n2, n3) -characterization . . . . . . . . . . . . . . . 123
3.4.4.3 Non-linear Estimators . . . . . . . . . . . . . . . . . . . . . 124 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Line drawings represent a large class of pictorial data used in such diverse areas as cartography, computer graphics, alphanumeric text, engineering drawing, and so on. Straight lines are particularly important because of their simplicity and their ability to approximate any curve to any desired accuracy. More than two thousand years ago, Euclid introduced straight lines through an axiomatic approach and made them the basic elements in his geometry. It is no wonder that studies in discrete geometry concentrated on defining and characterizing discrete counterparts of this vital concept.
