Lars Ericson.

Topologically correct graphical editing in the plane online

. (page 1 of 4)
Online LibraryLars EricsonTopologically correct graphical editing in the plane → online text (page 1 of 4)
Font size
QR-code for this ebook


Robotics Research
Technical Report







'^ina







Topologically Correct Graphical Editing in the Plane

by
Lars Ericson



Technical Report No. 275

Robotics Report No. 97

January, 1987




\



\



2: c cr>

o o to «J

r; >^ o D^ Cb
g U EH



New York University
I ^ Institute of Mathematical Sciences



Computer Science Division

25 1 Mercer Street New York, NX 1 00 1 2




L



Topologically Correct Graphical Editing in the Plane

by
Lars Ericson



Technical Report No. 275

Robotics Report No. 97

January, 1987



New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012



Work on this paper has been supported National Science Foundation Grants DCR-84-01898
and DCR-84-01633, and in part by U.S. Army Contract DAAB027-82-K-J196.



Topologically correct graphical editing in the plane

Lars Warren Ericson

Computer Science Department

Courant Institute of Mathematical Sciences

New York University

October 21, 1986

Revised January 17, 1987

Abstract

Computational geometers invent algorithms to represent and manipulate
geometrical objects. The applications of such algorithms range from the
creation of diagrams for documents to the visualization of steps in the proofs
of correctness of motion planning algorithms for robotics. An ideahzation
of the computational geometric component of each of these applications is
the problem of editing geometric objects composed of points and Hnes in
the plane. The editing algorithms employed must not lead to topologically
invalid conclusions, which could result from round-off error in munerical
approximations. We model the correct graphical editing problem as the
creation, and iterative modification and solution, of the set of equations
induced by a network whose nodes are relations constraining the values of
arcs which are labelled by portions of geometric objects. This survey focuses
on programming languages and systems which do constraint satisfaction,
and on numerical, algebraic and automated deduction methods which may
be applied to solve the systems of equations implied by constraint networks.



This work is partially supported by National Science Foundation grants DCR-84-
01898 and DCR-84-01633, and in part by U.S. Army Contract DAAB027-82-K-
J196.



Acknowledgement

I thank Professor Chee Yap for posing the problem of this paper and direct-
ing my reading in this area, Professors Bud Mishra and Edmond Schonberg
for critical reading of several versions of this paper, and Professor Jim Dem-
mel for informative conversation regtirding numerical methods. I would also
like to thank the Ada and Setl projects of Professors Edmond Schonberg
and Robert B.K. Deweir, for providing me with a congenial working environ-
ment and excellent criticaJ opinions in the area of programming language
design and implementation. Any remaining errors in this paper are my own
fault, of course.



2 CONTENTS

Contents

1 Topologically correct editing 5

1.1 The problem in general 5

1.2 The geometric relations considered 7

1.2.1 Numbers 8

1.2.2 Angles 9

1.2.3 Points 9

1.2.4 Lines 10

1.2.5 Frames 12

1.3 A canonical example 12

1.4 Implementing a correct graphical editor 16

2 Constraint network manipulations 19

2.1 Constraint networks are undirected graphs 19

2.2 Local graph techniques 20

2.2.1 Propagation of known states 21

2.2.2 Propagation of degrees of freedom 24

2.2.3 Redundant views 25

3 Numerical methods 26

3.1 Linearizing constraints 28

3.1.1 How to linearize constraints 28

3.1.2 Constraint linearization in SKETCHPAD 28

3.2 Minimizing least squares 30

3.3 Relaxation 32

3.3.1 Defining relaxation 32

3.3.2 Relaxation in SKETCHPAD and THINGLAB 33

3.4 Newton-Raphson iteration 33

3.4.1 Details of the method 33

3.4.2 A way of programming Newton iteration 35

3.4.3 Constraint systems which use Newton-Raphson iter-
ation 36



CONTENTS 3

4 Algebraic methods 37

4.1 Variations on Gaussian elimination 37

4.1.1 The LELAND Elimination Algorithm 37

4.1.2 Algebraic transformations in MaGRITTE 39

4.1.3 Leler's augmented term rewriting system 40

4.2 Advanced algebraic methods 41

4.2.1 van Wyk's observations on algebraic complexity . . 41

4.2.2 Grobner bases and ideal-theoretic methods 42

4.2.3 Algebraic nimabers 46

5 Finite-precision arithmetic and graphics 49

6 Constraint languages 50

6.1 The SKETCHPAD graphical editor 50

6.2 A proposal of Wilkes 52

6.3 Constraint languages and applications at MIT 53

6.4 The THINGLAB graphical simulation language 54

6.5 The MAGRITTE graphical editor 56

6.6 The Ideal typesetting language 56

6.7 The Juno graphical editor 57

6.7.1 Elements of the language 57

6.7.2 Juno code for an equilateral triangle 58

6.8 The BERTRAND production system language 58

6.8.1 Rules in BERTRAND 58

6.8.2 Types in BERTRAND 59

6.8.3 Evaluation order in BERTRAND 60

7 Conclusion 61
References 62



LIST OF TABLES



List of Figures



1 Topological error caused by approximation 6

2 Line types 11

3 The intersection of two lines 13

4 Addition and subtraction 14

5 A + B = C* D 14

6 The intersection of two lines, in detail 15

7 The constraint x + x — 4 23

8 Local propagation fails here 24

9 Local propagation succeeds here 26

List of Tables

1 Graphical editors and languages and their methods 17



1 Topologically correct editing
1.1 The problem in general

Current computer graphics systems use numerical approximations when
calculating the position of objects in relation to each other. These ap-
proximations may result in topologically invalid conclusions, when the \in-
certainty induced by round-off error is not accounted for. Suppose, for
example, that we define three lines

Lx-y = X
Lb'-V = -x + 2
Lc-.y = 1.1

and define a certain point px as the intersection of La and Lb- By algebraic
solution of the linear equation system we see that p^ lies below (1,1.1). But
iising numerical methods with fixed-precision arithmetic, we niay instead
conclude that px is above. Since the algebraic solution is niore accurate, we
see that simple numerical approximation results in an error in computing
the discrete relationship {below, above} between two objects. The situation
is illustrated in Figure 1.

The problem is to create a computer program to edit point and line
objects and groups of objects in the plane, in a correct fashion (to be defined
in a moment).

Objects are partially specified by a set of geometric relations between
objects. This set may be viewed as a network of constraints on the objects.
In a constraint network, the arcs are labels of portions of objects, and the
nodes are geometric relations.

An editing step is performed by modifying the constraint network, then
computing a satisfying assignment of values to variables in the system of
equations induced by the network. Depending on how much information is
"filled in", the result of an editing step is either a reduced set of equations,
with some unknowns remaining, or a complete set of satisfying assignments
to all va.riables occurring in the equations. As a refinement, we recursively
apply the process to isolatable subnetworks.



6



1 TOPOLOGICALLY CORRECT EDITING




a. The actual intersection point is at (1,1)




b. Shift due to approximation of intersection point



Figure 1: Topological error caused by approximation.



1.2 The geometric relations considered 7

By correct we mean that no network-satisfying assignment leads us to
conclude that a discrete relationship holds between two objects, when we
would conclude that the relationship did not hold if we performed an exact
algebraic solution of the system.

The problem above was suggested to me by Prof. Chee-Keng Yap, in the
course of an independent study on computer algebra (Spring, 1986). During
this time we worked on a language for describing constrained geometric
objects.

1.2 The geometric relations considered

The complexity of correct editing increases with the number of dimensions^,
and is unsolvable for unrestricted arithmetic relationships on the domain
of integers [8]. We restrict ourselves to the plane and, most importantly,
we restrict our investigation to methods which apply to a particular set of
geometric relationships, which we outline below.

The following objects and relational operators are those expressed in
Ericson and Yap's propK)sed LINEToOL language [ll].

Picture a plane on which a collection of Unes and points is displayed.
These lines and points are organized into movable figures, which we call
frames. Within a frame, lines and points are confi^red in relation to each
other by geometric assertions, such as the statement that point p is formed
by the intersection of lines Li and Lj. Frames are projected onto the plane,
where the projection is defined by a translation point and a rotation angle.
The translation point locates the origin of the virtual plane defined by
the frame on the absolute plane. The rotation angle gives the angle of
the frame plane i-aocis with respect to the absolute plane z-axis and the
absolute origin.

We may think of many different ways of describing a certain type of
object. For example, a line may be defined by a linear equation y = mx + b,
or it may be defined by two points through which it passes, or it may be
defined by a point and an angle; there are yet other descriptions. But for



^1 don't want to say much more than that, because it is basically a qualitative statement
which I can't give general support for, but is used to justify restricting the problem to
the plane.



8 1 TOPOLOGICALLY CORRECT EDITING

purposes of definition, we choose a canonical representation for each type
of object we will consider. Alternate representations may then be defined
by equations involving the canonical representaitons.

1.2.1 Numbers

The most primitive type of object required in the specification of geometric
objects is the number. There are various subtypes of number together with
their representations, such as real, complex, rational and algebraic numbers.
For the purpose of specifying objects by their relation to each other, it does
not concern us how a number is represented: for topological correctness
to hold, the statement of relationships between geometric objects such as
points and lines should be independent of the representation chosen for a
nimiber at a particular point in the computation. We also generally do not
care about which subtype of number is required; the "computing engine"
should choose the correct subtype in the course of computing relationships.
The following are some number representations that may be useful.

• Fixed- precision floating-point numbers, represented by a word or two
of computer memory, together with non-cissociative rounding or trun-
cating machine arithmetic.

• Rational numbers, represented by pairs of integers which form a quo-
tient, together with greatest common divisor nonnalizing rational
arithmetic.

• Algebraic numbers, represented by a defining polynomial with rational
or integer coefficients plus an isolating interval for a particular root
of the polynomial represented by a pair of rationals. The topic of
algebraic number arithmetic is quite complex and will be elaborated
in a section below.

We assimae the presence of the relations —, ^, and < on numbers,
as well SiS the relations of addition, multiplication and exponentiation. For
example, we view addition on (a, 6, c) as the relation a + 6 = c. The idea here
is that we are specifying geometric objects indirectly by their relationship
to each other. The arithmetic operations plus, times and exponent are



1.2 The geometric relations considered 9

viewed as relations rather than functions because it is more convenient. A
function is a one-directional operation which holds when we have values for
all of its arguments. Thus Add(i,y) = i + y is a function which takes on
a value when we know x and y. The relation of addition x+ y = z is much
more flexible: it tells us all when we know i and y, or i and z, or y and
2, and it tells us something even when we know only one of z, y or z, or if
we have only partial information about some subexpression of x, y or z, in
the case that these are expressions rather than simple variables.

1.2.2 Angles

ATigles 'are simply numbers, together with arithmetic modulo the period
of the chosen units {2n in the case of radians, 360 in the case of degrees).
Again, for the purpose of surveying the literature, we do not care about
the exact representation.

Between numbers and angles we define a coercion relation

RNxi^iO,) = »■ = number(a) = a = angle(r)

where r is a real number and a is an angle.

Between numbers and angles we have the cosine relation

Rcot{r, b. These methods are fast (but slower than network-
manipulation methods, when they work). Lazard notes that numerical
methods do not give the number of roots of a system of equations, nor do
they work on extensions of finite fields [19]. An example of the fallibility of



1.4 Implementing a correct graphical editor



17



System


Year


Author


Methods


Sketchpad


Sutherland


1963


Least mean squares fit relaxation
Network manipulation


Thinglab


Borning


1979


Relaxation

Network manipulation


Ideal


van Wyk


1980


Gaussian elimination


Constraints


Steele


1980


Network manipulation


Magritte


Gosling


1983


Gaussian elimination


Juno


Nelson


1985


Newton-Raphson iteration



Table 1: Graphical editors and languages and their methods



numerical methods is as follows. The JUNO graphical editor [27], which uses
the Newton-Raphson method to solve constraints, allows one to constrain
two line segments to be parallel. It also allows one to declare the length
or relative length of a line segment. Nelson notes that "if the user makes
a long segment parallel to a short segment, the solver tends to collapse the
short segment to a point." In other words, the length of the shorter line
segment is set to zero.

Language design is largely a matter of taste, because the limiting factor
in the solution of our main problem as posed in the first section is the
availability of fast algorithms for solving systems of equations. However,
we will discuss several distinct and innovative language designs.

The equational approach has a much richer theoretical background, but
only recently has there been much pragmatic success in topologically correct
methods.

Elimination methods eliminate successive variables un til one equation
in one variable remains. All roots are found. Such methods can be slow
(though specific methods for linear systems are fast). As Lazard notes, "if
the system consists of equations of degree rf in n variables, the final equa-
tion has, in general, degree cP" ." In other words, in general the obvious
method of ehmination is intractable. We will group all such methods under
the heading "Gaussian elimination", though the term has a more restrictive
technical definition.



18 1 TOPOLOGICALLY CORRECT EDITING

The family of Grobner basis methods provides a conceptually differ-
ent approach to elimination which is much faster under certain conditions.
These methods can be shown to be similar to elimination [20], but the
problem is phrased differently. The complexity of Grobner basis methods
in general is an open question [26].

Term rewriting systems are simply a family of methods for applying
equational axioms to initial sets of hypotheses. This paradigm is employed
by Leler to specify constraint satisfaction systems [21].

An algebraic number is defined a particular zero of a given polynomial. It
is possible to do linear order preserving arithmetic on algebraic numbers.
With algebraic numbers this is done by increasing the precision of the
intervals when necessary in the course of performing arithmetic operations.



19

2 Constraint network manipulations

In this section we discuss a few non-numerical constraint network tech-
niques that have been developed by those authors whose systems use the
constraint graph as the preferred object of computation.

We begin with a formal definition of the ba^ic constraint graph definition
assumed by all authors. Then we give names and sketches of the algorithms
for the network techniques. The purpose of the techniques is to find a
satisfying assignment for the variables constrained by the network.


1 3 4

Online LibraryLars EricsonTopologically correct graphical editing in the plane → online text (page 1 of 4)