University of South Carolina 2D & 3D Local and Global Coordination Summary

I need a summary for chapter one from the book i attached. The summary is about local and global coordination in 2D and 3D. Show example to find the local and global. List one or two real life application. one page is enough.

Practical Linear Algebra
This page intentionally left blank
Practical Linear Algebra
A Geometry Toolbox
Third Edition
Gerald Farin
Dianne Hansford
CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2014 by Taylor & Francis Group, LLC
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Version Date: 20130524
International Standard Book Number-13: 978-1-4665-7958-3 (eBook – PDF)
This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but
the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to
trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained.
If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical,
or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without
written permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright
Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a
variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to
infringe.
Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com
and the CRC Press Web site at
http://www.crcpress.com
With gratitude to
Dr. James Slack and Norman Banemann.
This page intentionally left blank
Contents
Preface
xiii
Descartes’ Discovery
1.1
Local and Global Coordinates: 2D .
1.2
Going from Global to Local . . . .
1.3
Local and Global Coordinates: 3D .
1.4
Stepping Outside the Box . . . . . .
1.5
Application: Creating Coordinates .
1.6
Exercises . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
2
6
8
9
10
12
Chapter 1
.
.
.
.
.
.
Here and There: Points and Vectors in 2D
2.1
Points and Vectors . . . . . .
2.2
What’s the Diﬀerence? . . . .
2.3
Vector Fields . . . . . . . . . .
2.4
Length of a Vector . . . . . . .
2.5
Combining Points . . . . . . .
2.6
Independence . . . . . . . . .
2.7
Dot Product . . . . . . . . . .
2.8
Orthogonal Projections . . . .
2.9
Inequalities . . . . . . . . . . .
2.10 Exercises . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
16
18
19
20
23
26
26
31
32
33
Chapter 2
.
.
.
.
.
.
.
.
.
.
Lining Up:
3.1
3.2
3.3
3.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
38
39
40
44
Chapter 3
.
.
.
.
2D Lines
Deﬁning a Line . . . . . . . .
Parametric Equation of a Line
Implicit Equation of a Line . .
Explicit Equation of a Line . .
vii
viii
3.5
3.6
3.7
3.8
3.9
Chapter 4
Chapter 5
Converting Between Parametric and Implicit
Equations . . . . . . . . . . . . . . . . . . .
3.5.1 Parametric to Implicit . . . . . . . . . .
3.5.2 Implicit to Parametric . . . . . . . . . .
Distance of a Point to a Line . . . . . . . . .
3.6.1 Starting with an Implicit Line . . . . . .
3.6.2 Starting with a Parametric Line . . . .
The Foot of a Point . . . . . . . . . . . . . .
A Meeting Place: Computing Intersections .
3.8.1 Parametric and Implicit . . . . . . . . .
3.8.2 Both Parametric . . . . . . . . . . . . .
3.8.3 Both Implicit . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
45
45
47
48
50
51
52
53
55
57
58
Changing Shapes: Linear Maps in 2D
4.1
Skew Target Boxes . . . . . . . . . . .
4.2
The Matrix Form . . . . . . . . . . . .
4.3
Linear Spaces . . . . . . . . . . . . . .
4.4
Scalings . . . . . . . . . . . . . . . . . .
4.5
Reﬂections . . . . . . . . . . . . . . . .
4.6
Rotations . . . . . . . . . . . . . . . . .
4.7
Shears . . . . . . . . . . . . . . . . . .
4.8
Projections . . . . . . . . . . . . . . . .
4.9
Areas and Linear Maps: Determinants
4.10 Composing Linear Maps . . . . . . . .
4.11 More on Matrix Multiplication . . . . .
4.12 Matrix Arithmetic Rules . . . . . . . .
4.13 Exercises . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
61
62
63
66
68
71
73
75
77
80
83
87
89
91
2 × 2 Linear Systems
5.1
Skew Target Boxes Revisited . . . .
5.2
The Matrix Form . . . . . . . . . .
5.3
A Direct Approach: Cramer’s Rule
5.4
Gauss Elimination . . . . . . . . . .
5.5
Pivoting . . . . . . . . . . . . . . .
5.6
Unsolvable Systems . . . . . . . . .
5.7
Underdetermined Systems . . . . .
5.8
Homogeneous Systems . . . . . . .
5.9
Undoing Maps: Inverse Matrices . .
5.10 Deﬁning a Map . . . . . . . . . . .
5.11 A Dual View . . . . . . . . . . . . .
5.12 Exercises . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
95
96
97
98
99
101
104
104
105
107
113
114
116
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ix
Moving Things Around: Affine Maps in 2D
6.1
Coordinate Transformations . .
6.2
Aﬃne and Linear Maps . . . . .
6.3
Translations . . . . . . . . . . .
6.4
More General Aﬃne Maps . . .
6.5
Mapping Triangles to Triangles
6.6
Composing Aﬃne Maps . . . .
6.7
Exercises . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
119
120
122
124
124
126
128
132
Chapter 6
.
.
.
.
.
.
.
Eigen Things
7.1
Fixed Directions . . . . . . . . . . . .
7.2
Eigenvalues . . . . . . . . . . . . . . .
7.3
Eigenvectors . . . . . . . . . . . . . .
7.4
Striving for More Generality . . . . .
7.5
The Geometry of Symmetric Matrices
7.6
Quadratic Forms . . . . . . . . . . . .
7.7
Repeating Maps . . . . . . . . . . . .
7.8
Exercises . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
135
136
137
139
142
145
149
153
155
Chapter 7
.
.
.
.
.
.
.
.
3D Geometry
8.1
From 2D to 3D . . . . . . . . . . .
8.2
Cross Product . . . . . . . . . . . .
8.3
Lines . . . . . . . . . . . . . . . . .
8.4
Planes . . . . . . . . . . . . . . . .
8.5
Scalar Triple Product . . . . . . . .
8.6
Application: Lighting and Shading
8.7
Exercises . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
157
158
160
164
165
169
171
174
Chapter 8
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
177
178
180
181
183
184
186
190
193
196
199
200
202
Chapter 9
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Determinants
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Linear Maps in 3D
9.1
Matrices and Linear Maps
9.2
Linear Spaces . . . . . . .
9.3
Scalings . . . . . . . . . . .
9.4
Reﬂections . . . . . . . . .
9.5
Shears . . . . . . . . . . .
9.6
Rotations . . . . . . . . . .
9.7
Projections . . . . . . . . .
9.8
Volumes and Linear Maps:
9.9
Combining Linear Maps .
9.10 Inverse Matrices . . . . . .
9.11 More on Matrices . . . . .
9.12 Exercises . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Affine Maps in 3D
10.1 Aﬃne Maps . . . . . . . . . .
10.2 Translations . . . . . . . . . .
10.3 Mapping Tetrahedra . . . . .
10.4 Parallel Projections . . . . . .
10.5 Homogeneous Coordinates and
10.6 Exercises . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Perspective Maps
. . . . . . . . . . .
Interactions in 3D
11.1 Distance Between a Point and a Plane . .
11.2 Distance Between Two Lines . . . . . . . .
11.3 Lines and Planes: Intersections . . . . . . .
11.4 Intersecting a Triangle and a Line . . . . .
11.5 Reﬂections . . . . . . . . . . . . . . . . . .
11.6 Intersecting Three Planes . . . . . . . . . .
11.7 Intersecting Two Planes . . . . . . . . . .
11.8 Creating Orthonormal Coordinate Systems
11.9 Exercises . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
207
208
209
209
212
217
222
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
225
226
227
229
231
232
233
235
235
238
Gauss for Linear Systems
12.1 The Problem . . . . . . . . . . . . . . . . . .
12.2 The Solution via Gauss Elimination . . . . .
12.3 Homogeneous Linear Systems . . . . . . . .
12.4 Inverse Matrices . . . . . . . . . . . . . . . .
12.5 LU Decomposition . . . . . . . . . . . . . . .
12.6 Determinants . . . . . . . . . . . . . . . . .
12.7 Least Squares . . . . . . . . . . . . . . . . .
12.8 Application: Fitting Data to a Femoral Head
12.9 Exercises . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
243
244
247
255
257
260
264
267
271
273
Alternative System Solvers
13.1 The Householder Method . . . . . . . . . . . . . . .
13.2 Vector Norms . . . . . . . . . . . . . . . . . . . . .
13.3 Matrix Norms . . . . . . . . . . . . . . . . . . . . .
13.4 The Condition Number . . . . . . . . . . . . . . . .
13.5 Vector Sequences . . . . . . . . . . . . . . . . . . .
13.6 Iterative System Solvers: Gauss-Jacobi and GaussSeidel . . . . . . . . . . . . . . . . . . . . . . . . . .
13.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . .
277
278
285
288
291
293
295
299
xi
General Linear Spaces
14.1 Basic Properties of Linear Spaces .
14.2 Linear Maps . . . . . . . . . . . . .
14.3 Inner Products . . . . . . . . . . . .
14.4 Gram-Schmidt Orthonormalization
14.5 A Gallery of Spaces . . . . . . . . .
14.6 Exercises . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
303
304
307
310
314
316
318
Chapter 14
.
.
.
.
.
.
Eigen Things Revisited
15.1 The Basics Revisited . . . . . .
15.2 The Power Method . . . . . . .
15.3 Application: Google Eigenvector
15.4 Eigenfunctions . . . . . . . . . .
15.5 Exercises . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
323
324
331
334
337
339
Chapter 15
.
.
.
.
.
The Singular Value Decomposition
16.1 The Geometry of the 2 × 2 Case
16.2 The General Case . . . . . . . .
16.3 SVD Steps . . . . . . . . . . . .
16.4 Singular Values and Volumes . .
16.5 The Pseudoinverse . . . . . . . .
16.6 Least Squares . . . . . . . . . .
16.7 Application: Image Compression
16.8 Principal Components Analysis
16.9 Exercises . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
343
344
348
352
353
354
355
359
360
365
Chapter 16
.
.
.
.
.
.
.
.
.
Breaking It Up: Triangles
17.1 Barycentric Coordinates . .
17.2 Aﬃne Invariance . . . . . . .
17.3 Some Special Points . . . . .
17.4 2D Triangulations . . . . . .
17.5 A Data Structure . . . . . .
17.6 Application: Point Location
17.7 3D Triangulations . . . . . .
17.8 Exercises . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
367
368
370
371
374
375
377
378
379
Chapter 17
.
.
.
.
.
.
.
.
Putting Lines Together: Polylines and Polygons
18.1 Polylines . . . . . . . . . . . . . . .
18.2 Polygons . . . . . . . . . . . . . . .
18.3 Convexity . . . . . . . . . . . . . .
18.4 Types of Polygons . . . . . . . . . .
18.5 Unusual Polygons . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
381
382
382
384
385
386
Chapter 18
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xii
18.6
18.7
18.8
18.9
Turning Angles and Winding Numbers
Area . . . . . . . . . . . . . . . . . . .
Application: Planarity Test . . . . . . .
Application: Inside or Outside? . . . .
18.9.1 Even-Odd Rule . . . . . . . . . . .
18.9.2 Nonzero Winding Number . . . . .
18.10 Exercises . . . . . . . . . . . . . . . . .
Chapter 19
Chapter 20
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
387
389
393
394
394
395
396
Conics
19.1
19.2
19.3
19.4
The General Conic . . . . . . . . .
Analyzing Conics . . . . . . . . . .
General Conic to Standard Position
Exercises . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
399
400
405
406
409
Curves
20.1
20.2
20.3
20.4
20.5
20.6
20.7
20.8
Parametric Curves . . . . . . . .
Properties of Bézier Curves . . .
The Matrix Form . . . . . . . .
Derivatives . . . . . . . . . . . .
Composite Curves . . . . . . . .
The Geometry of Planar Curves
Moving along a Curve . . . . . .
Exercises . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
411
412
417
418
420
422
422
425
427
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Appendix A
Glossary
429
Appendix B
Selected Exercise Solutions
443
Bibliography
487
Index
489
Preface
Just about everyone has watched animated movies, such as Toy Story
or Shrek, or is familiar with the latest three-dimensional computer
games. Enjoying 3D entertainment sounds like more fun than studying a linear algebra book. But it is because of linear algebra that
those movies and games can be brought to a TV or computer screen.
When you see a character move on the screen, it’s animated using
some equation straight out of this book. In this sense, linear algebra
is a driving force of our new digital world: it is powering the software
behind modern visual entertainment and communication.
But this is not a book on entertainment. We start with the fundamentals of linear algebra and proceed to various applications. So it
doesn’t become too dry, we replaced mathematical proofs with motivations, examples, or graphics. For a beginning student, this will
result in a deeper level of understanding than standard theorem-proof
approaches. The book covers all of undergraduate-level linear algebra in the classical sense—except it is not delivered in a classical way.
Since it relies heavily on examples and pointers to applications, we
chose the title Practical Linear Algebra, or PLA for short.
The subtitle of this book is A Geometry Toolbox; this is meant
to emphasize that we approach linear algebra in a geometric and
algorithmic way. Our goal is to bring the material of this book to
a broader audience, motivated in a large part by our observations
of how little engineers and scientists (non-math majors) retain from
classical linear algebra classes. Thus, we set out to ﬁll a void in the
linear algebra textbook market. We feel that we have achieved this,
presenting the material in an intuitive, geometric manner that will
lend itself to retention of the ideas and methods.
xiii
xiv
Preface
Review of Contents
As stated previously, one clear motivation we had for writing PLA
was to present the material so that the reader would retain the information. In our experience, approaching the material ﬁrst in two
and then in three dimensions lends itself to visualizing and then to
understanding. Incorporating many illustrations, Chapters 1–7 introduce the fundamentals of linear algebra in a 2D setting. These
same concepts are revisited in Chapters 8–11 in a 3D setting. The
3D world lends itself to concepts that do not exist in 2D, and these
are explored there too.
Higher dimensions, necessary for many real-life applications and the
development of abstract thought, are visited in Chapters 12–16. The
focus of these chapters includes linear system solvers (Gauss elimination, LU decomposition, the Householder method, and iterative
methods), determinants, inverse matrices, revisiting “eigen things,”
linear spaces, inner products, and the Gram-Schmidt process. Singular value decomposition, the pseudoinverse, and principal components
analysis are new additions.
Conics, discussed in Chapter 19, are a fundamental geometric entity, and since their development provides a wonderful application
for aﬃne maps, “eigen things,” and symmetric matrices, they really
shouldn’t be missed. Triangles in Chapter 17 and polygons in Chapter 18 are discussed because they are fundamental geometric entities
and are important in generating computer images.
Several of the chapters have an “Application” section, giving a realworld use of the tools developed thus far. We have made an eﬀort to
choose applications that many readers will enjoy by staying away from
in-depth domain-speciﬁc language. Chapter 20 may be viewed as an
application chapter as a whole. Various linear algebra ingredients are
applied to the techniques of curve design and analysis.
The illustrations in the book come in two forms: ﬁgures and sketches.
The ﬁgures are computer generated and tend to be complex. The
sketches are hand-drawn and illustrate the core of a concept. Both are
great teaching and learning tools! We made all of them available on
the book’s website http://www.farinhansford.com/books/pla/. Many
of the ﬁgures were generated using PostScript, an easy-to-use geometric language, or Mathematica.
At the end of each chapter, we have included a list of topics, What
You Should Know (WYSK), marked by the icon on the left. This list
is intended to encapsulate the main points of each chapter. It is not
uncommon for a topic to appear in more than one chapter. We have
Preface
xv
made an eﬀort to revisit some key ideas more than once. Repetition
is useful for retention!
Exercises are listed at the end of each chapter. Solutions to selected
exercises are given in Appendix B. All solutions are available to
instructors and instructions for accessing these may be found on the
book’s website.
Appendix A provides an extensive glossary that can serve as a
review tool. We give brief deﬁnitions without equations so as to
present a diﬀerent presentation than that in the text. Also notable
is the robust index, which we hope will be very helpful, particularly
since we revisit topics throughout the text.
Classroom Use
PLA is meant to be used at the undergraduate level. It serves as an
introduction to linear algebra for engineers or computer scientists, as
well as a general introduction to geometry. It is also an ideal preparation for computer graphics and geometric modeling. We would argue
that it is also a perfect linear algebra entry point for mathematics
majors.
As a one-semester course, we recommend choosing a subset of the
material that meets the needs of the students. In the table below,
LA refers to an introductory linear algebra course and CG refers to
a course tailored to those planning to work in computer graphics or
geometric modeling.
Chapter
LA
CG
1
Descartes’ Discovery
•
•
2
Here and There: Points and Vectors in 2D
•
•
3
Lining Up: 2D Lines
4
Changing Shapes: Linear Maps in 2D
•
•
5
2×2 Linear Systems
•
•
6
Moving Things Around: Aﬃne Maps in 2D
•
•
7
Eigen Things
•
8
3D Geometry
•
•
9
Linear Maps in 3D
•
•
10
Aﬃne Maps in 3D
•
•
11
Interactions in 3D
•
•
xvi
Preface
Chapter
LA
CG
•
12
Gauss for Linear Systems
•
13
Alternative System Solvers
•
14
General Linear Spaces
•
15
Eigen Things Revisited
•
16
The Singular Value Decomposition
•
17
Breaking It Up: Triangles
•
18
Putting Lines Together: Polylines and Polygons
•
19
Conics
•
20
Curves
•
Website
Practical Linear Algebra, A Geometry Toolbox has a website:
http://www.farinhansford.com/books/pla/
This website provides:
• teaching materials,
• additional material,
• the PostScript ﬁles illustrated in the book,
• Mathematica code,
• errata,
• and more!
Gerald Farin
Dianne Hansford
March, 2013
Arizona State University
1
Descartes’ Discovery
Figure 1.1.
Local and global coordinate systems: the treasure’s local coordinates with respect to
the boat do not change as the boat moves. However, the treasure’s global coordinates,
defined relative to the lake, do change as the boat moves.
There is a collection of old German tales that take place sometime in
the 17th century, and they are about an alleged town called Schilda,
1
2
1. Descartes’ Discovery
whose inhabitants were not known for their intelligence. Here is one
story [12]:
An army was approaching Schilda and would likely conquer
it. The town council, in charge of the town treasure, had to hide
it from the invaders. What better way than to sink it in the
nearby town lake? So the town council members board the town
boat, head for the middle of the lake, and sink the treasure.
The town treasurer gets out his pocket knife and cuts a deep
notch in the boat’s rim, right where the treasure went down.
Why would he do that, the other council members wonder? “So
that we will remember where we sunk the treasure, otherwise
we’ll never ﬁnd it later!” replies the treasurer. Everyone is duly
impressed at such planning genius!
Eventually, the war is over and the town council embarks on
the town boat again, this time to reclaim the treasure from the
lake. Once out on the lake, the treasurer’s plan suddenly does
not seem so smart anymore. No matter where they went, the
notch in the boat’s rim told them they had found the treasure!
The French philosopher René Descartes (1596–1650) would have
known better: he invented the theory of coordinate systems. The
treasurer recorded the sinking of the treasure accurately by marking
it on the boat. That is, he recorded the treasure’s position relative
to a local coordinate system. But by neglecting the boat’s position
relative to the lake, the global coordinate system, he lost it all! (See
Figure 1.1.) The remainder of this chapter is about the interplay of
local and global coordinate systems.
1.1 Local and Global Coordinates: 2D
This book is written using the LATEX typesetting system (see [9] or
[13]), which converts every page to be output to a page description
language called PostScript (see [1]). It tells a laser printer where to
position all the characters and symbols that go on a particular page.
For the ﬁrst page of this chapter, there is a PostScript command that
positions the letter D in the chapter heading.
In order to do this, one needs a two-dimensional, or 2D, coordinate
system. Its origin is simply the lower left corner of the page, and the
x- and y-axes are formed by the horizontal and vertical paper edges
meeting there. Once we are given this coordinate system, we can
position objects in it, such as our letter D.
1.1. Local and Global Coordinates: 2D
3
The D, on the other hand, was designed by font designers who
obviously did not know about its position on this page or of its actual
size. They used their own coordinate system, and in it, the letter D
is described by a set of points, each having coordinates relative to D’s
coordinate system, as shown in Sketch 1.1.
We call this system a local coordinate system, as opposed to the
global coordinate system, which is used for the whole page. Positioning
letters on a page thus requires mastering the interplay of the global
and local systems.
Following Sketch 1.2, let’s make things more formal: Let (x1 , x2 ) be
coordinates in a global coordinate system, called the [e1 , e2 ]-system.
The boldface notation will be explained in the next chapter. You may
be used to calling coordinates (x, y); however, the (x1 , x2 ) notation
will streamline the material in this book, and it also makes writing
programs easier. Let (u1 , u2 ) be coordinates in a local system called
the [d1 , d2 ]-system. Let an object in the local system be enclosed by
a box with lower left corner (0, 0) and upper right corner (1, 1). This
means that the object “lives” in the unit square of the local system,
i.e., a square of edge length one, and with its lower left corner at the
origin. Restricting ourselves to the unit square for the local system
makes this ﬁrst chapter easy—we will later relax this restriction.
We wish to position our object into the global system so that it
ﬁts into a box with lower left corner (min1 , min2 ) and upper right
corner (max1 , max2 ) called the target box (drawn with heavy lines in
Sketch 1.2). This is accomplished by assigning to coordinates (u1 , u2 )
in the local system the corresponding target coordinates (x1 , x2 ) in
the global system. This correspondence is characterized by preserving
each coordinate value with respect to their extents. The local coordinates are also known as parameters. In terms of formulas, these
parameters are written as quotients,
u1 − 0
x1 − min1
=
1−0
max1 − min1
x2 − min2
u2 − 0
=
.
1−0
max2 − min2
Sketch 1.1.
A local coordinate system.
Sketch 1.2.
Thus, the corresponding formulas for x1 and x2 are quite simple:
x1 = (1 − u1 )min1 + u1 max1 ,
(1.1)
x2 = (1 − u2 )min2 + u2 max2 .
(1.2)
We say that the coordinates (u1 , u2 ) are mapped to the coordinates
(x1 , x2 ). Sketch 1.3 illustrates how the letter D is mapped. This
concept of a parameter is reintroduced in Section 2.5.
Global and local systems.
4
1. Descartes’ Discovery
Let’s check that this actually works: the coordinates (u1 , u2 ) =
(0, 0) in the local system must go to the coordinates (x1 , x2 ) =
(min1 , min2 ) in the global system. We obtain
x1 = (1 − 0) · min1 + 0 · max1 = min1 ,
x2 = (1 − 0) · min2 + 0 · max2 = min2 .
Similarly, the coordinates (u1 , u2 ) = (1, 0) in the local system must
go to the coordinates (x1 , x2 ) = (max1 , min2 ) in the global system.
We obtain
x1 = (1 − 1) · min1 + 1 · max1 = max1 ,
x2 = (1 − 0) · min2 + 0 · max2 = min2 .
Example 1.1
Sketch 1.3.
Let the target box be given by
Local and global D.
(min1 , min2 ) = (1, 3) and (max1 , max2 ) = (3, 5),
see Sketch 1.4. The coordinates (1/2, 1/2) can be thought of as
the “midpoint” of the local unit square. Let’s look at the result
of the mapping:
1
x1 = (1 − ) · 1 +
2
1
x2 = (1 − ) · 3 +
2
1
· 3 = 2,
2
1
· 5 = 4.
2
This is the “midpoint” of the target box. You see here how the
geometry in the unit square is replicated in the target box.
Sketch 1.4.
Map local unit square to a target
box.
A diﬀerent way of writing (1.1) and (1.2) is as follows: Deﬁne
Δ1 = max1 − min1 and Δ2 = max2 − min2 . Now we have
x1 = min1 + u1 Δ1 ,
(1.3)
x2 = min2 + u2 Δ2 .
(1.4)
1.1. Local and Global Coordinates: 2D
D
Figure 1.2.
D
D
D
5
D
D
D
D
Target boxes: the letter D is mapped several times. Left: centered in the unit square.
Right: not centered.
A note of caution: if the target box is not a square, then the object
from the local system will be distorted. We see this in the following
example, illustrated by Sketch 1.5. The target box is given by
(min1 , min2 ) = (−1, 1) and (max1 , max2 ) = (2, 2).
You can see how the local object is stretched in the e1 -direction by
being put into the global system. Check for yourself that the corners
of the unit square (local) still get mapped to the corners of the target
box (global).
In general, if Δ1 > 1, then the object will be stretched in the e1 direction, and it will be shrunk if 0 < Δ1 < 1. The case of max1 smaller than min1 is not often encountered: it would result in a reversal of the object in the e1 -direction. The same applies, of course, to the e2 -direction if max2 is smaller than min2 . An example of several boxes containing the letter D is shown in Figure 1.2. Just for fun, we have included one target box with max1 smaller than min1 ! Another characterization of the change of shape of the object may be made by looking at the change in aspect ratio, which is the ratio of the width to the height, Δ1 /Δ2 , for the target box. This is also written as Δ1 : Δ2 .The aspect ratio in the local system is one. Revisiting 6 1. Descartes’ Discovery Sketch 1.5. A distortion. Example 1.1, the aspect ratio of the target box is one, therefore there is no distortion of the letter D, although it is stretched uniformly in both coordinates. In Sketch 1.5, a target box is given that has aspect ratio 3, therefore the letter D is distorted. Aspect ratios are encountered many times in everyday life. Televisions and computer screens have recently changed from nearly square 4 : 3 to 16 : 9. Sketch 1.5 illustrates the kind of distortion that occurs when an old format program is stretched to ﬁll a new format screen. (Normally a better solution is to not stretch the image and allow for vertical black bars on either side of the image.) All international √ (ISO A series) paper, regardless of size, has an aspect ratio of 1√: 2. Golden rectangles, formed based on the golden ratio φ = (1 + 5)/2 with an aspect ratio of 1 : φ, provide a pleasing and functional shape, and found their way into art and architecture. Credit cards have an aspect ratio of 8 : 5, but to ﬁt into your wallet and card readers the size is important as well. This principle, by the way, acts strictly on a “don’t need to know” basis: we do not need to know the relationship between the local and global systems. In many cases (as in the typesetting example), there actually isn’t a known correspondence at the time the object in the local system is created. Of course, one must know where the actual object is located in the local unit square. If it is not nicely centered, we might have the situation shown in Figure 1.2 (right). You experience this “unit square to target box” mapping whenever you use a computer. When you open a window, you might want to view a particular image in it. The image is stored in a local coordinate system; if it is stored with extents (0, 0) and (1, 1), then it utilizes normalized coordinates. The target box is now given by the extents of your window, which are given in terms of screen coordinates and the image is mapped to it using (1.1) and (1.2). Screen coordinates are typically given in terms of pixels;1 a typical computer screen would have about 1440 × 900 pixels, which has an aspect ratio of 8 : 5 or 1.6. 1.2 Going from Global to Local When discussing global and local systems in 2D, we used a target box to position (and possibly distort) the unit square in a local [d1 , d2 ]system. For given coordinates (u1 , u2 ), we could ﬁnd coordinates (x1 , x2 ) in the global system using (1.1) and (1.2), or (1.3) and (1.4). 1 The term is short for “picture element.” 1.2. Going from Global to Local 7 How about the inverse problem: given coordinates (x1 , x2 ) in the global system, what are its local (u1 , u2 ) coordinates? The answer is relatively easy: compute u1 from (1.3), and u2 from (1.4), resulting in u1 = x1 − min1 , Δ1 (1.5) u2 = x2 − min2 . Δ2 (1.6) Applications for this process arise any time you use a mouse to communicate with a computer. Suppose several icons are displayed in a window. When you click on one of them, how does your computer actually know which one? The answer: it uses Equations (1.5) and (1.6) to determine its position. Example 1.2 Let a window on a computer screen have screen coordinates (min1 , min2 ) = (120, 300) and (max1 , max2 ) = (600, 820). The window is ﬁlled with 21 icons, arranged in a 7 × 3 pattern (see Figure 1.3). A mouse click returns screen coordinates (200, 709). Which icon was clicked? The computations that take place are as follows: 200 − 120 ≈ 0.17, 480 709 − 300 u2 = ≈ 0.79, 520 u1 = according to (1.5) and (1.6). The u1 -partition of normalized coordinates is 0, 0.33, 0.67, 1. The value 0.17 for u1 is between 0.0 and 0.33, so an icon in the ﬁrst column was picked. The u2 -partition of normalized coordinates is 0, 0.14, 0.29, 0.43, 0.57, 0.71, 0.86, 1. The value 0.79 for u2 is between 0.71 and 0.86, so the “Display” icon in the second row of the ﬁrst column was picked. 8 1. Descartes’ Discovery Figure 1.3. Selecting an icon: global to local coordinates. 1.3 Local and Global Coordinates: 3D Sketch 1.6. Airplane coordinates. These days, almost all engineering objects are designed using a Computer-Aided Design (CAD) system. Every object is deﬁned in a coordinate system, and usually many individual objects need to be integrated into one coordinate system. Take designing a large commercial airplane, for example. It is deﬁned in a three-dimensional (or 3D) coordinate system with its origin at the frontmost part of the plane, the e1 -axis pointing toward the rear, the e2 -axis pointing to the right (that is, if you’re sitting in the plane), and the e3 -axis is pointing upward. See Sketch 1.6. Before the plane is built, it undergoes intense computer simulation in order to ﬁnd its optimal shape. As an example, consider the engines: these may vary in size, and their exact locations under the wings need to be speciﬁed. An engine is deﬁned in a local coordinate system, and it is then moved to its proper location. This process will have to be repeated for all engines. Another example would be the seats in the plane: the manufacturer would design just one— then multiple copies of it are put at the right locations in the plane’s design. 1.4. Stepping Outside the Box 9 Following Sketch 1.7, and making things more formal again, we are given a local 3D coordinate system, called the [d1 , d2 , d3 ]-system, with coordinates (u1 , u2 , u3 ). We assume that the object under consideration is located inside the unit cube, i.e., all of its deﬁning points satisfy 0 ≤ u1 , u2 , u3 ≤ 1. This cube is to be mapped onto a 3D target box in the global [e1 , e2 , e3 ]system. Let the target box be given by its lower corner (min1 , min2 , min3 ) and its upper corner (max1 , max2 , max3 ). How do we map coordinates (u1 , u2 , u3 ) from the local unit cube into the corresponding target coordinates (x1 , x2 , x3 ) in the target box? Exactly as in the 2D case, with just one more equation: x1 = (1 − u1 )min1 + u1 max1 , (1.7) x2 = (1 − u2 )min2 + u2 max2 , x3 = (1 − u3 )min3 + u3 max3 . (1.8) (1.9) As an easy exercise, check that the corners of the unit cube are mapped to the corners of the target box. The analog to (1.3) and (1.4) is given by the rather obvious x1 = min1 + u1 Δ1 , (1.10) x2 = min2 + u2 Δ2 , x3 = min3 + u3 Δ3 . (1.11) (1.12) Sketch 1.7. Global and local 3D systems. As in the 2D case, if the target box is not a cube, object distortions will result—this may be desired or not. 1.4 Stepping Outside the Box We have restricted all objects to be within the unit square or cube; as a consequence, their images were inside the respective target boxes. This notion helps with an initial understanding, but it is not at all essential. Let’s look at a 2D example, with the target box given by (min1 , min2 ) = (1, 1) and (max1 , max2 ) = (2, 3), and illustrated in Sketch 1.8. The coordinates (u1 , u2 ) = (2, 3/2) are not inside the [d1 , d2 ]system unit square. Yet we can map it using (1.1) and (1.2): x1 = −min1 + 2max1 = 3, 1 3 x2 = − min2 + max2 = 4. 2 2 Sketch 1.8. A 2D coordinate outside the target box. 10 1. Descartes’ Discovery Since the initial coordinates (u1 , u2 ) were not inside the unit square, the mapped coordinates (x1 , x2 ) are not inside the target box. The notion of mapping a square to a target box is a useful concept for mentally visualizing what is happening—but it is not actually a restriction to the coordinates that we can map! Example 1.3 Without much belaboring, it is clear the same holds for 3D. An example should suﬃce: the target box is given by (min1 , min2 , min3 ) = (0, 1, 0) and (max1 , max2 , max3 ) = (0.5, 2, 1), and we want to map the coordinates (u1 , u2 , u3 ) = (1.5, 1.5, 0.5). The result, illustrated by Sketch 1.9, is computed using (1.7)–(1.9): it is (x1 , x2 , x3 ) = (0.75, 2.5, 0.5). 1.5 Application: Creating Coordinates Sketch 1.9. A 3D coordinate outside the 3D target box. Suppose you have an interesting real object, like a model of a cat. A friend of yours in Hollywood would like to use this cat in her latest hi-tech animated movie. Such movies use only mathematical descriptions of objects—everything must have coordinates! You might recall the movie Toy Story. It is a computer-animated movie, meaning that the characters and objects in every scene have a mathematical representation. So how do you give your cat model coordinates? This is done with a CMM, or coordinate measuring machine; see Figure 1.4. The CMM is essentially an arm that is able to record the position of its tip by keeping track of the angles of its joints. Your cat model is placed on a table and somehow ﬁxed so it does not move during digitizing. You let the CMM’s arm touch three points on the table; they will be converted to the origin and the e1 - and e2 -coordinate axes of a 3D coordinate system. The e3 -axis (vertical to the table) is computed automatically.2 Now when you touch your 2 Just how we convert the three points on the table to the three axes is covered in Section 11.8. 1.5. Application: Creating Coordinates 11 Figure 1.4. Creating coordinates: a cat is turned into math. (Microscribe-3D from Immersion Corporation, http://www.immersion.com.) cat model with the tip of the CMM’s arm, it will associate three coordinates with that position and record them. You repeat this for several hundred points, and you have your cat in the box! This process is called digitizing. In the end, the cat has been “discretized,” or turned into a ﬁnite number of coordinate triples. This set of points is called a point cloud. Someone else will now have to build a mathematical model of your cat.3 Next, the mathematical model will have to be put into scenes of the movie—but all that’s needed for that are 3D coordinate transformations! (See Chapters 9 and 10.) • unit square • 2D and 3D local coordinates • 2D and 3D global coordinates • coordinate transformation • • • • • parameter aspect ratio normalized coordinates digitizing point cloud 3 This type of work is called geometric modeling or computer-aided geometric design, see [7] and Chapter 20. 12 1. Descartes’ Discovery 1.6 Exercises 1. Let the coordinates of triangle vertices in the local [d1 , d2 ]-system unit square be given by (u1 , u2 ) = (0.1, 0.1), (v1 , v2 ) = (0.9, 0.2), (w1 , w2 ) = (0.4, 0.7). (a) If the [d1 , d2 ]-system unit square is mapped to the target box with (min1 , min2 ) = (1, 2) and (max1 , max2 ) = (3, 3), where are the coordinates of the triangle vertices mapped? (b) What local coordinates correspond to (x1 , x2 ) = (2, 2) in the [e1 , e2 ]-system? 2. Given local coordinates (2, 2) and (−1, −1), ﬁnd the global coordinates with respect to the target box with (min1 , min2 ) = (1, 1) and (max1 , max2 ) = (7, 3). Make a sketch of the local and global systems. Connect the coordinates in each system with a line and compare. 3. Let the [d1 , d2 , d3 ]-system unit cube be mapped to the 3D target box with (min1 , min2 , min3 ) = (1, 1, 1) and (Δ1 , Δ2 , Δ3 ) = (1, 2, 4). Where will the coordinates (u1 , u2 , u3 ) = (0.5, 0, 0.7) be mapped? 4. Let the coordinates of triangle vertices in the local [d1 , d2 , d3 ]-system unit square be given by (u1 , u2 , u3 ) = (0.1, 0.1, 0), (v1 , v2 , v3 ) = (0.9, 0.2, 1), (w1 , w2 , w3 ) = (0.4, 0.7, 0). If the [d1 , d2 , d3 ]-system unit square is mapped to the target box with (min1 , min2 ) = (1, 2, 4) and (max1 , max2 ) = (3, 3, 8), where are the coordinates of the triangle vertices mapped? Hint: See Exercise 1a. 5. Suppose we are given a global frame deﬁned by (min1 , min2 , min3 ) = (0, 0, 3) and (max1 , max2 , max3 ) = (4, 4, 4). For the coordinates (1, 1, 3) and (0, 0, 0) in this frame, what are the corresponding coordinates in the [d1 , d2 , d3 ]-system? 6. Assume you have an image in a local frame of 20 mm2 . If you enlarge the frame and the image such that the new frame covers 40 mm2 , by how much does the image size change? 1.6. Exercises 7. Suppose that local frame coordinates (v1 , v2 ) = (1/2, 1) are mapped to global frame coordinates (5, 2) and similarly, (w1 , w2 ) = (1, 1) are mapped to (8, 8). In the local frame, (u1 , u2 ) = (3/4, 1/2) lies at the midpoint of two local coordinate sets. What are its coordinates in the global frame? 8. The size of a TV set is speciﬁed by its monitor’s diagonal. In order to determine the width and height of this TV, we must know the relevant aspect ratio. What are the width and height dimensions of a 32 standard TV with aspect ratio 4 : 3? What are the dimensions of a 32 HD TV with aspect ratio 16 : 9? (This is an easy one to ﬁnd on the web, but the point is to calculate it yourself!) 9. Suppose we are given coordinates (1/2, 1/2) in the [d1 , d2 ]-system. What are the corresponding coordinates in the global frame with aspect ratio 4 : 3, (min1 , min2 ) = (0, 0), and Δ2 = 2? 10. In some implementations of the computer graphics viewing pipeline, normalized device coordinates, or NDC, are deﬁned as the cube with extents (−1, −1, −1) and (1, 1, 1). The next step in the pipeline maps the (u1 , u2 ) coordinates from NDC (u3 is ignored) to the viewport, the area of the screen where the image will appear. Give equations for (x1 , x2 ) in the viewport deﬁned by extents (min1 , min2 ) and (max1 , max2 ) that correspond to (u1 , u2 ) in NDC. 13 This page intentionally left blank 2 Here and There: Points and Vectors in 2D Figure 2.1. Hurricane Katrina: the hurricane is shown here approaching south Louisiana. (Image courtesy of NOAA, katrina.noaa.gov.) In 2005 Hurricane Katrina caused ﬂooding and deaths as it made its way from the Bahamas to south Florida as a category 1 hurricane. Over the warm waters of the Gulf, it grew into a category 5 hurricane, 15 16 2. Here and There: Points and Vectors in 2D and even though at landfall in southeast Louisiana it had weakened to a category 3 hurricane, the storm surges and destruction it created rates it as the most expensive hurricane to date, causing more than $45 billion of damage. Sadly it was also one of the deadliest, particularly for residents of New Orleans. In the hurricane image (Figure 2.1), air is moving rapidly, spiraling in a counterclockwise fashion. What isn’t so clear from this image is that the air moves faster as it approaches the eye of the hurricane. This air movement is best described by points and vectors: at any location (point), air moves in a certain direction and with a certain speed (velocity vector). This hurricane image is a good example of how helpful 2D geometry can be in a 3D world. Of course a hurricane is a 3D phenomenon; however, by analyzing 2D slices, or cross sections, we can develop a very informative analysis. Many other applications call for 2D geometry only. The purpose of this chapter is to deﬁne the two most fundamental tools we need to work in a 2D world: points and vectors. 2.1 Points and Vectors Sketch 2.1. Points and their coordinates. Sketch 2.2. Two points and a vector. The most basic geometric entity is the point. A point is a reference to a location. Sketch 2.1 illustrates examples of points. In the text, boldface lowercase letters represent points, e.g., p p= 1 . (2.1) p2 The location of p is p1 -units along the e1 -axis and p2 -units along the e2 -axis. Thus a point’s coordinates, p1 and p2 , are dependent upon the location of the coordinate origin. We use the boldface notation so there is a noticeable diﬀerence between a one-dimensional (1D) number, or scalar p. To clearly identify p as a point, the notation p ∈ E2 is used. This means that a 2D point “lives” in 2D Euclidean space E2 . Now let’s move away from our reference point. Following Sketch 2.2, suppose the reference point is p, and when moving along a straight path, our target point is q. The directions from p would be to follow the vector v. Our notation for a vector is the same as for a point: boldface lowercase letters. To get to q we say, q = p + v. To calculate this, add each component separately; that is, q1 p v p + v1 = 1 + 1 = 1 . q2 p2 v2 p2 + v2 (2.2) 2.1. Points and Vectors 17 For example, in Sketch 2.2, we have 2 2 4 . + = 1 2 3 The components of v, v1 and v2 , indicate how many units to move along the e1 - and e2 -axis, respectively. This means that v can be deﬁned as v = q − p. (2.3) This deﬁnes a vector as a diﬀerence of two points, which describes a direction and a distance, or a displacement. Examples of vectors are illustrated in Sketch 2.3. How to determine a vector’s length is covered in Section 2.4. Above we described this length as a distance. Alternatively, this length can be described as speed: then we have a velocity vector.1 Yet another interpretation is that the length represents acceleration: then we have a force vector. A vector has a tail and a head. As in Sketch 2.2, the tail is typically displayed positioned at a point, or bound to a point in order to indicate the geometric signiﬁcance of the vector. However, unlike a point, a vector does not deﬁne a position. Two vectors are equal if they have the same component values, just as points are equal if they have the same coordinate values. Thus, considering a vector as a diﬀerence of two points, there are any number of vectors with the same direction and length. See Sketch 2.4 for an illustration. A special vector worth mentioning is the zero vector, 0 . 0= 0 This vector has no direction or length. Other somewhat special vectors include 1 0 and e2 = . e1 = 0 1 In the sketches, these vectors are not always drawn true to length to prevent them from obscuring the main idea. To clearly identify v as a vector, we write v ∈ R2 . This means that a 2D vector “lives” in a 2D linear space R2 . (Other names for R2 are real or vector spaces.) 1 This is what we’ll use to continue the Hurricane Katrina example. Sketch 2.3. Vectors and their components. Sketch 2.4. Instances of one vector. 18 2. Here and There: Points and Vectors in 2D 2.2 What’s the Difference? When writing a point or a vector we use boldface lowercase letters; when programming we use the same data structure, e.g., arrays. This makes it appear that points and vectors can be treated in the same manner. Not so! Points and vectors are diﬀerent geometric entities. This is reiterated by saying they live in diﬀerent spaces, E2 and R2 . As shown in Sketch 2.5, for convenience and clarity elements of Euclidean and linear spaces are typically displayed together. The primary reason for diﬀerentiating between points and vectors is to achieve geometric constructions that are coordinate independent. Such constructions are manipulations applied to geometric objects that produce the same result regardless of the location of the coordinate origin (for example, the midpoint of two points). This idea becomes clearer by analyzing some fundamental manipulations of points and vectors. In what follows, let’s use p, q ∈ E2 and v, w ∈ R2 . Sketch 2.5. Euclidean and linear spaces illustrated separately and together. Coordinate Independent Operations: • Subtracting a point from another (p − q) yields a vector, as depicted in Sketch 2.2 and Equation (2.3). • Adding or subtracting two vectors yields another vector. See Sketch 2.6, which illustrates the parallelogram rule: the vectors v − w and v + w are the diagonals of the parallelogram deﬁned by v and w. This is a coordinate independent operation since vectors are deﬁned as a diﬀerence of points. • Multiplying by a scalar s is called scaling. Scaling a vector is a well-deﬁned operation. The result sv adjusts the length by the scaling factor. The direction is unchanged if s > 0 and reversed
for s < 0. If s = 0 then the result is the zero vector. Sketch 2.7 illustrates some examples of scaling a vector. Sketch 2.6. Parallelogram rule. • Adding a vector to a point (p + v) yields another point, as in Sketch 2.2 and Equation (2.2). Any coordinate independent combination of two or more points and/or vectors can be grouped to fall into one or more of the items above. See the Exercises for examples. 2.3. Vector Fields 19 Coordinate Dependent Operations: • Scaling a point (sp) is not a well-deﬁned operation because it is not coordinate independent. Sketch 2.8 illustrates that the result of scaling the solid black point by one-half with respect to two diﬀerent coordinate systems results in two diﬀerent points. • Adding two points (p+q) is not a well-deﬁned operation because it is not coordinate independent. As depicted in Sketch 2.9, the result of adding the two solid black points is dependent on the coordinate origin. (The parallelogram rule is used here to construct the results of the additions.) Sketch 2.7. Scaling a vector. Some special combinations of points are allowed; they are deﬁned in Section 2.5. 2.3 Vector Fields Sketch 2.8. Scaling of points is ambiguous. Figure 2.2. Vector field: simulating hurricane air velocity. Lighter gray indicates greater velocity. A good way to visualize the interplay between points and vectors is through the example of vector ﬁelds. In general, we speak of a vector ﬁeld if every point in a given region is assigned a vector. We have already encountered an example of this in Figure 2.1: Hurricane Katrina! Recall that at each location (point) we could describe the air velocity (vector). Our previous image did not actually tell us anything about the air speed, although we could presume something about the direction. This is where a vector ﬁeld is helpful. Shown in Figure 2.2 is a vector ﬁeld simulating Hurricane Katrina. By plotting all the 20 2. Here and There: Points and Vectors in 2D vectors the same length and using gray scale or varying shades of gray to indicate speed, the vector ﬁeld can be more informative than the photograph. (Visualization of a vector ﬁeld requires discretizing it: a ﬁnite number of point and vector pairs are selected from a continuous ﬁeld or from sampled measurements.) Other important applications of vector ﬁelds arise in the areas of automotive and aerospace design: before a car or an airplane is built, it undergoes extensive aerodynamic simulations. In these simulations, the vectors that characterize the ﬂow around an object are computed from complex diﬀerential equations. In Figure 2.3 we have another example of a vector ﬁeld. Sketch 2.9. Addition of points is ambiguous. Figure 2.3. Vector field: every sampled point has an associated vector. Lighter gray indicates greater vector length. 2.4 Sketch 2.10. Length of a vector. Length of a Vector As mentioned in Section 2.1, the length of a vector can represent distance, velocity, or acceleration. We need a method for ﬁnding the length of a vector, or the magnitude. As illustrated in Sketch 2.10, a vector deﬁnes the displacement necessary (with respect to the e1 and e2 -axis) to get from a point at the tail of the vector to a point at the head of the vector. In Sketch 2.10 we have formed a right triangle. The square of the length of the hypotenuse of a right triangle is well known from the Pythagorean theorem. Denote the length of a vector v as v. Then v2 = v12 + v22 . 2.4. Length of a Vector 21 Therefore, the magnitude of v is v = v12 + v22 . (2.4) This is also called the Euclidean norm. Notice that if we scale the vector by an amount k then kv = |k|v. (2.5) A normalized vector w has unit length, that is w = 1. Normalized vectors are also known as unit vectors. To normalize a vector simply means to scale a vector so that it has unit length. If w is to be our unit length version of v then v w= . v Each component of v is divided by the scalar value v. This scalar value is always nonnegative, which means that its value is zero or greater. It can be zero! You must check the value before dividing to be sure it is greater than your zero divide tolerance. The zero divide tolerance is the absolute value of the smallest number by which you can divide conﬁdently. (When we refer to checking that a value is greater than this number, it means to check the absolute value.) In Figures 2.2 and 2.3, we display vectors of varying magnitudes. But instead of plotting them using diﬀerent lengths, their magnitude is indicated by gray scales. Example 2.1 Start with Applying (2.4), v = v is deﬁned as 5 . v= 0 √ 52 + 02 = 5. Then the normalized version of 1 5/5 . = w= 0 0/5 Clearly w = 1, so this is a normalized vector. Since we have only scaled v by a positive amount, the direction of w is the same as v. 22 2. Here and There: Points and Vectors in 2D Figure 2.4. Unit vectors: they define a circle. There are inﬁnitely many unit vectors. Imagine drawing them all, emanating from the origin. The ﬁgure that you will get is a circle of radius one! See Figure 2.4. To ﬁnd the distance between two points we simply form a vector deﬁned by the two points, e.g., v = q − p, and apply (2.4). Example 2.2 Let −1 q= 2 1 . and p = 0 Then q−p= and q − p = −2 2 (−2)2 + 22 = Sketch 2.11 illustrates this example. Sketch 2.11. Distance between two points. √ 8 ≈ 2.83. 2.5. Combining Points 2.5 23 Combining Points Seemingly contrary to Section 2.2, there actually is a way to combine two points such that we get a (meaningful) third one. Take the example of the midpoint r of two points p and q; more speciﬁcally, take 3 2 1 , , q= , r= p= 0 3 6 as shown in Sketch 2.12. Let’s start with the known coordinate independent operation of adding a vector to a point. Deﬁne r by adding an appropriately scaled version of the vector v = q − p to the point p: Sketch 2.12. The midpoint of two points. 1 r= p+ v 2 1 1 2 2 + = . 6 3 −6 2 Expanding, this shows that r can also be deﬁned as 1 1 r= p+ q 2 2 1 1 3 2 1 = + . 3 2 6 2 0 This is a legal expression for a combination of points. There is nothing magical about the factor 1/2, however. Adding a (scaled) vector to a point is a well-deﬁned, coordinate independent operation that yields another point. Any point of the form r = p + tv (2.6) is on the line through p and q. Again, we may rewrite this as r = p + t(q − p) and then r = (1 − t)p + tq. (2.7) Sketch 2.13 gives an example with t = 1/3. The scalar values (1 − t) and t are coeﬃcients. A weighted sum of points where the coeﬃcients sum to one is called a barycentric combination. In this special case, where one point r is being expressed in terms of two others, p and q, the coeﬃcients 1 − t and t are called the barycentric coordinates of r. Sketch 2.13. Barycentric combinations: t = 1/3. 24 2. Here and There: Points and Vectors in 2D A barycentric combination allows us to construct r anywhere on the line deﬁned by p and q. This is why (2.7) is also called linear interpolation. If we would like to restrict r’s position to the line segment between p and q, then we allow only convex combinations: t must satisfy 0 ≤ t ≤ 1. To deﬁne points outside of the line segment between p and q, we need values of t < 0 or t > 1.
The position of r is said to be in the ratio of t : (1 − t) or t/(1 − t).
In physics, r is known as the center of gravity of two points p and q
with weights 1 − t and t, respectively. From a constructive approach,
the ratio is formed from the quotient
Sketch 2.14.
Examples of ratios.
||r − p||
.
||q − r||
Some examples are illustrated in Sketch 2.14.
ratio =
Example 2.3
Suppose we have three collinear points, p, q, and r as illustrated in
Sketch 2.15. The points have the following locations.

8
6.5
2
.
, q=
, r=
p=
8
7
4
Sketch 2.15.
Barycentric coordinates in
relation to lengths.
What are the barycentric coordinates of r with respect to p and q?
To answer this, recall the relationship between the ratio and the
barycentric coordinates. The barycentric coordinates t and (1 − t)
deﬁne r as

8
2
6.5
.
+t
= (1 − t)
8
4
7
The ratio indicates the location of r relative to p and q in terms of
relative distances. Suppose the ratio is s1 : s2 . If we scale s1 and
s2 such that they sum to one, then s1 and s2 are the barycentric
coordinates t and (1 − t), respectively. By calculating the distances
between points:
l1 = r − p ≈ 5.4,
l2 = q − r ≈ 1.8,
l3 = l1 + l2 ≈ 7.2,
we ﬁnd that
t = l1 /l3 = 0.75 and
(1 − t) = l2 /l3 = 0.25.
2.5. Combining Points
25
These are the barycentric coordinates. Let’s verify this:

8
2
6.5
.
+ 0.75 ×
= 0.25 ×
8
4
7
The barycentric coordinate t is also called a parameter. (See Section 3.2 for more details.) This parameter is deﬁned by the quotient
t=
||r − p||
.
||q − p||
We have seen how useful this quotient can be in Section 1.1 for the
construction of a point in the global system that corresponded to a
point with parameter t in the local system.
We can create barycentric combinations with more than two points.
Let’s look at three points p, q, and r, which are not collinear. Any
point s can be formed from
s = r + t1 (p − r) + t2 (q − r).
This is a coordinate independent operation of point + vector + vector.
Expanding and regrouping, we can also deﬁne s as
s = t1 p + t2 q + (1 − t1 − t2 )r
= t1 p + t2 q + t3 r.
(2.8)
Thus, the point s is deﬁned by a barycentric combination with
coeﬃcients t1 , t2 , and t3 = 1 − t1 − t2 with respect to p, q, and r,
respectively. This is another special case where the barycentric combination coeﬃcients correspond to barycentric coordinates. Sketch 2.16
illustrates this. We will encounter barycentric coordinates in more
detail in Chapter 17.
We can also combine points so that the result is a vector. For this,
we need the coeﬃcients to sum to zero. We encountered a simple case
of this in (2.3). Suppose we have the equation
e = r − 2p + q,
r, p, q ∈ E2 .
Does e have a geometric meaning? Looking at the sum of the coeﬃcients, 1 − 2 + 1 = 0, we would conclude by the rule above that e is
a vector. How to see this? By rewriting the equation as
e = (r − p) + (q − p),
it is clear that e is a vector formed from (vector + vector).
Sketch 2.16.
A barycentric combination of
three points.
26
2. Here and There: Points and Vectors in 2D
2.6
Independence
Two vectors v and w describe a parallelogram, as shown in Sketch 2.6.
It may happen that this parallelogram has zero area; then the two
vectors are parallel. In this case, we have a relationship of the form
v = cw. If two vectors are parallel, then we call them linearly dependent. Otherwise, we say that they are linearly independent.
Two linearly independent vectors may be used to write any other
vector u as a linear combination:
u = rv + sw.
How to ﬁnd r and s is described in Chapter 5. Two linearly independent vectors in 2D are also called a basis for R2 . If v and w
are linearly dependent, then you cannot write all vectors as a linear
combination of them, as the following example shows.
Example 2.4

1
v=
2
Let
If we tried to write the vector

2
.
and w =
4

1
u=
0
as u = rv + sw, then this would lead to
1 = r + 2s,
0 = 2r + 4s.
(2.9)
(2.10)
If we multiply the ﬁrst equation by a factor of 2, the two right-hand
sides will be equal. Equating the new left-hand sides now results in
the expression 2 = 0. This shows that u cannot be written as a linear
combination of v and w. (See Sketch 2.17.)
Sketch 2.17.
Dependent vectors.
2.7
Dot Product
Given two vectors v and w, we might ask:
• Are they the same vector?
2.7. Dot Product
27
• Are they perpendicular to each other?
• What angle do they form?
The dot product is the tool to resolve these questions. Assume that v
and w are not the zero vector.
To motivate the dot product, let’s start with the Pythagorean theorem and Sketch 2.18. There, we see two perpendicular vectors v and
w; we conclude
v − w2 = v2 + w2 .
(2.11)
Writing the components in (2.11) explicitly
Sketch 2.18.
Perpendicular vectors.
(v1 − w1 )2 + (v2 − w2 )2 = (v12 + v22 ) + (w12 + w22 ),
and then expanding, bringing all terms to the left-hand side of the
equation yields
(v12 − 2v1 w1 + w12 ) + (v22 − 2v2 w2 + w22 ) − (v12 + v22 ) − (w12 + w22 ) = 0,
which reduces to
v1 w1 + v2 w2 = 0.
(2.12)
We ﬁnd that perpendicular vectors have the property that the sum
of the products of their components is zero. The short-hand vector
notation for (2.12) is
v · w = 0.
(2.13)
This result has an immediate application: a vector w perpendicular
to a given vector v can be formed as

−v2
w=
v1
(switching components and negating the sign of one). Then v · w
becomes v1 (−v2 ) + v2 v1 = 0.
If we take two arbitrary vectors v and w, then v · w will in general
not be zero. But we can compute it anyway, and deﬁne
s = v · w = v1 w1 + v2 w2
(2.14)
to be the dot product of v and w. Notice that the dot product returns
a scalar s, which is why it is also called a scalar product. (Mathematicians have yet another name for the dot product—an inner product.
See Section 14.3 for more on these.) From (2.14) it is clear that
v · w = w · v.
28
2. Here and There: Points and Vectors in 2D
This is called the symmetry property. Other properties of the dot
product are given in the Exercises.
In order to understand the geometric meaning of the dot product
of two vectors, let’s construct a triangle from two vectors v and w as
illustrated in Sketch 2.19.
From trigonometry, we know that the height h of the triangle can
be expressed as
h = w sin(θ).
Squaring both sides results in
Sketch 2.19.
h2 = w2 sin2 (θ).
Geometry of the dot product.
Using the identity
sin2 (θ) + cos2 (θ) = 1,
we have
h2 = w2 (1 − cos2 (θ)).
(2.15)
We can also express the height h with respect to the other right
triangle in Sketch 2.19 and by using the Pythagorean theorem:
h2 = v − w2 − (v − w cos θ)2 .
(2.16)
Equating (2.15) and (2.16) and simplifying, we have the expression,
v − w2 = v2 + w2 − 2vw cos θ.
(2.17)
We have just proved the Law of Cosines, which generalizes the Pythagorean theorem by correcting it for triangles with an opposing angle
diﬀerent from 90◦ .
We can formulate another expression for v − w2 by explicitly
writing out
v − w2 = (v − w) · (v − w)
= v2 − 2v · w + w2 .
(2.18)
By equating (2.17) and (2.18) we ﬁnd that
v · w = vw cos θ.
(2.19)
Here is another expression for the dot product—it is a very useful one!
Rearranging (2.19), the cosine of the angle between the two vectors
can be determined as
v·w
cos θ =
.
(2.20)
vw
2.7. Dot Product
29
cos(θ)
1
90°
180°
θ
–1
Figure 2.5.
Cosine function: its values at θ = 0◦ , θ = 90◦ , and θ = 180◦ are important to remember.
By examining a plot of the cosine function in Figure 2.5, some sense
can be made of (2.20).
First we consider the special case of perpendicular vectors. Recall the dot product was zero, which makes cos(90◦ ) = 0, just as it
should be.
If v has the same (or opposite) direction as w, that is v = kw,
then (2.20) becomes
kw · w
cos θ =
.
kww
Using (2.5), we have
cos θ =
kw2
= ±1.
|k|ww
Again, examining Figure 2.5, we see this corresponds to either θ = 0◦
or θ = 180◦ , for vectors of the same or opposite direction, respectively.
The cosine values from (2.20) range between ±1; this corresponds to
angles between 0◦ and 180◦ (or 0 and π radians). Thus, the smaller
angle between the two vectors is measured. This is clear from the
derivation: the angle θ enclosed by completing the triangle deﬁned
by the two vectors must be less than 180◦ . Three types of angles can
be formed:
• right: cos(θ) = 0 → v · w = 0;
• acute: cos(θ) > 0 → v · w > 0;
• obtuse: cos(θ) < 0 → v · w < 0. These are illustrated in counterclockwise order from twelve o’clock in Sketch 2.20. Sketch 2.20. Three types of angles. 30 2. Here and There: Points and Vectors in 2D If the actual angle θ needs to be calculated, then the arccosine function has to be invoked: let v·w s= vw then θ = acos(s) where acos is short for arccosine. One word of warning: in some math libraries, if s > 1 or s < −1 then an error occurs and a nonusable result (NaN—Not a Number) is returned. Thus, if s is calculated, it is best to check that its value is within the appropriate range. It is not uncommon that an intended value of s = 1.0 is actually something like s = 1.0000001 due to roundoﬀ. Thus, the arccosine function should be used with caution. In many instances, as in comparing angles, the cosine of the angle is all you need! Additionally, computing the cosine or sine is 40 times more expensive than a multiplication, meaning that a cosine operation might take 200 cycles (operations) and a multiplication might take 5 cycles. Arccosine and arcsine are yet more expensive. Example 2.5 Let’s calculate the angle between the two vectors illustrated in Sketch 2.21, forming an obtuse angle: −1 2 . and w = v= 0 1 Sketch 2.21. The angle between two vectors. Calculate the length of each vector, √ v = 22 + 12 = 5 w = −12 + 02 = 1. The cosine of the angle between the vectors is calculated using (2.20) as (2 × −1) + (1 × 0) −2 √ cos(θ) = = √ ≈ −0.8944. 5×1 5 Then arccos(−0.8944) ≈ 153.4◦. To convert an angle given in degrees to radians multiply by π/180◦ . (Recall that π ≈ 3.14159 radians.) This means that π . 2.677 radians ≈ 153.4◦ × 180◦ 2.8. Orthogonal Projections 2.8 31 Orthogonal Projections Sketch 2.19 illustrates that the projection of the vector w onto v creates a footprint of length b = ||w|| cos(θ). This we derive from basic trigonometry: cos(θ) = b/hypotenuse. The orthogonal projection of w onto v is then the vector v v·w u = (||w|| cos(θ)) = v. (2.21) ||v|| ||v||2 Sometimes this projection is expressed as u = projV1 w, where V1 is the set of all 2D vectors kv and it is referred to as a onedimensional subspace of R2 . Therefore, u is the best approximation to w in the subspace V1 . This concept of closest or best approximation will be needed for several problems, such as ﬁnding the point at the end of the footprint in Section 3.7 and for least squares approximations in Section 12.7. We will revisit subspaces with more rigor in Chapter 14. Using the orthogonal projection, it is easy to decompose the 2D vector w into a sum of two perpendicular vectors, namely u and u⊥ (a vector perpendicular to u), such that w = u + u⊥ . (2.22) Another way to state this: we have resolved w into components with respect to two other vectors. Already having found the vector u, we now set v·w u⊥ = w − v. ||v||2 This can also be written as u⊥ = w − projV1 w, and thus u⊥ is the component of w orthogonal to the space of u. See the Exercises of Chapter 8 for a 3D version of this decomposition. Orthogonal projections and vector decomposition are at the core of constructing the Gram-Schmidt orthonormal coordinate frame in Section 11.8 for 3D and in Section 14.4 for higher dimensions. An application that uses this frame is discussed in Section 20.7. The ability to decompose a vector into its component parts is key to Fourier analysis, quantum mechanics, digital audio, and video recording. 32 2. Here and There: Points and Vectors in 2D 2.9 Inequalities Here are two important inequalities when dealing with vector lengths. Let’s start with the expression from (2.19), i.e., v · w = vw cos θ. Squaring both sides gives (v · w)2 = v2 w2 cos2 θ. Noting that 0 ≤ cos2 θ ≤ 1, we conclude that (v · w)2 ≤ v2 w2 . (2.23) This is the Cauchy-Schwartz inequality. Equality holds if and only if v and w are linearly dependent. This inequality is fundamental in the study of more general vector spaces, which are presented in Chapter 14. Suppose we would like to ﬁnd an inequality that describes the relationship between the length of two vectors v and w and the length of their sum v + w. In other words, how does the length of the third side of a triangle relate to the lengths of the other two? Let’s begin with expanding v + w2 : v + w2 = (v + w) · (v + w) = v · v + 2v · w + w · w ≤ v · v + 2|v · w| + w · w ≤ v · v + 2vw + w · w (2.24) = v2 + 2vw + w2 = (v + w)2 . Sketch 2.22. The triangle inequality. Taking square roots gives v + w ≤ v + w, which is known as the triangle inequality. It states the intuitively obvious fact that the sum of any two edge lengths in a triangle is never smaller than the length of the third edge; see Sketch 2.22 for an illustration. 2.10. Exercises 33 • point versus vector • coordinates versus components • E2 versus R2 • coordinate independent • vector length • unit vector • zero divide tolerance • Pythagorean theorem • distance between two points • parallelogram rule • scaling • ratio • barycentric combination 2.10 • • • • • • • • • • • • • linear interpolation convex combination barycentric coordinates linearly dependent vectors linear combination basis for R2 dot product Law of Cosines perpendicular vectors angle between vectors orthogonal projection vector decomposition Cauchy-Schwartz inequality • triangle inequality Exercises 1. Illustrate the parallelogram rule applied to the vectors −2 2 v= and w = . 1 1 2. The parallelogram rule states that adding or subtracting two vectors, v and w, yields another vector. Why is it called the parallelogram rule? 3. Deﬁne your own p, q following expressions that are. (a) (c) (e) (g) ∈ E2 and v, w ∈ R2 . Determine which of the are geometrically meaningful. Illustrate those p+q p+v v+w v − 2w (b) (d) (f) (h) 1 p 2 + 12 q 3p + v 2v + 12 w 3 p − 12 q 2 4. Suppose we are given p, q ∈ E2 and v, w ∈ R2 . Do the following operations result in a point or a vector? (a) (c) (e) p−q p+v v+w (b) (d) (f) 1 p 2 + 12 q 3v p + 12 w 5. What barycentric combination of the points p and q results in the midpoint of the line through these two points? 34 2. Here and There: Points and Vectors in 2D 6. Illustrate a point with barycentric coordinates (1/2, 1/4, 1/4) with respect to three other points. 7. Consider two points. Form the set of all convex combinations of these points. What is the geometry of this set? 8. Consider three noncollinear points. Form the set of all convex combinations of these points. What is the geometry of this set? 9. What is the length of the vector v= −4 ? −3 10. What is the magnitude of the vector 3 v= ? −3 11. If a vector v is length 10, then what is the length of the vector −2v? 12. Find the distance between the points 3 −2 p= and q = . 3 −3 13. Find the distance between the points −3 −2 p= and q = . −3 −3 14. What is the length of the unit vector u? −4 15. Normalize the vector v = . −3 4 16. Normalize the vector v = . 2 17. Given points p= 1 , 1 q= 7 , 7 r= 3 , 3 what are the barycentric coordinates of r with respect to p and q? 18. Given points p= 1 , 1 q= 7 , 7 r= 5 , 5 what are the barycentric coordinates of r with respect to p and q? 19. If v = 4w, are v and w linearly independent? 20. If v = 4w, what is the area of the parallelogram spanned by v and w? 2.10. Exercises 35 21. Do the vectors v1 = 1 4 and v2 = 3 0 form a basis for R2 ? 22. What linear combination allows us to express u with respect to v1 and v2 , where 1 4 6 , v2 = ? u= , v1 = 0 4 4 23. Show that the dot product has the following properties for vectors u, v, w ∈ R2 . u·v =v·u symmetric v · (sw) = s(v · w) homogeneous (v + w) · u = v · u + w · u v·v >0
if
v = 0
and
distributive
v·v =0
if
v=0
positive
24. What is v · w where
v=

5
4
and

0
?
1
w=
What is the scalar product of w and v?
25. Compute the angle (in degrees) formed by the vectors
v=

5
5

and

3
.
−3
w=
26. Compute the cosine of the angle formed by the vectors
v=

5
5
and
w=

0
.
4
Is the angle less than or greater than 90◦ ?
27. Are the following angles acute, obtuse, or right?
cos θ1 = −0.7
28. Given the vectors
cos θ2 = 0

v=
1
−1

and w =
cos θ3 = 0.7

3
,
2
ﬁnd the orthogonal projection u of w onto v. Decompose w into components u and u⊥ .
36
2. Here and There: Points and Vectors in 2D
29. For
v=
√
1/√2
1/ 2
and
w=

1
3
ﬁnd
u = projV1 w,
where V1 is the set of all 2D vectors kv, and ﬁnd
u⊥ = w − projV1 w.
30. Given vectors v and w, is it possible for (v · w)2 to be greater than
v2 w2 ?
31. Given vectors v and w, under what conditions is (v · w)2 equal to
v2 w2 ? Give an example.
32. Given vectors v and w, can the length of v + w be longer than the
length of v + w?
33. Given vectors v and w, under what conditions is v+w = v+w?
Give an example.
3
Lining Up: 2D Lines
Figure 3.1.
Moiré patterns: overlaying two sets of lines at an angle results in an interesting pattern.
“Real” objects are three-dimensional, or 3D. So why should we consider 2D objects, such as the 2D lines in this chapter? Because they
really are the building blocks for geometric constructions and play a
key role in many applications. We’ll look at various representations
37
38
3. Lining Up: 2D Lines
for lines, where each is suited for particular applications. Once we can
represent a line, we can perform intersections and determine distances
from a line.
Figure 3.1 shows how interesting playing with lines can be. Two
sets of parallel lines are overlaid and the resulting interference pattern
is called a Moiré pattern. Such patterns are used in optics for checking
the properties of lenses.
3.1 Defining a Line
As illustrated in Sketch 3.1, two elements of 2D geometry deﬁne a
line:
• two points;
• a point and a vector parallel to the line;
• a point and a vector perpendicular to the line.
Sketch 3.1.
Elements to define a line.
The unit vector that is perpendicular (or orthogonal) to a line is
referred to as the normal to the line. Figure 3.2 shows two families
of lines: one family of lines shares a common point and the other
family of lines shares the same normal. Just as there are diﬀerent
ways to specify a line geometrically, there are diﬀerent mathematical
representations: parametric, implicit, and explicit. Each representation will be examined and the advantages of each will be explained.
Additionally, we will explore how to convert from one form to another.
Figure 3.2.
Families of lines: one family shares a common point and the other shares a common
normal.
3.2. Parametric Equation of a Line
39
3.2 Parametric Equation of a Line
The parametric equation of a line l(t) has the form
l(t) = p + tv,
(3.1)
where p ∈ E2 and v ∈ R2 . The scalar value t is the parameter. (See
Sketch 3.2.) Evaluating (3.1) for a speciﬁc parameter t = t̂, generates
a point on the line.
We encountered (3.1) in Section 2.5 in the context of barycentric
coordinates. Interpreting v as a diﬀerence of points, v = q − p, this
equation was reformulated as
l(t) = (1 − t)p + tq.
(3.2)
A parametric line can be written in the form of either (3.1) or (3.2).
The latter is typically referred to as linear interpolation.
One way to interpret the parameter t is as time; at time t = 0 we
will be at point p and at time t = 1 we will be at point q. Sketch 3.2
illustrates that as t varies between zero and one, t ∈ [0, 1], points are
generated on the line between p and q. Recall from Section 2.5 that
these values of t constitute a convex combination, which is a special
case of a barycentric combination. If the parameter is a negative
number, that is t < 0, the direction of v reverses, generating points on the line “behind” p. The case t > 1 is similar: this scales v so
that it is elongated, which generates points “past” q. In the context
of linear interpolation, when t < 0 or t > 1, it is called extrapolation.
The parametric form is very handy for computing points on a line.
For example, to compute ten equally spaced points on the line segment between p and q, simply deﬁne ten values of t ∈ [0, 1] as
t = i/9,
i = 0, . . . , 9.
(Be sure this is a ﬂoating point calculation when programming!)
Equally spaced parameter values correspond to equally spaced points.
Example 3.1
Compute ﬁve points on the line deﬁned by the points

6
1
.
and q =
p=
4
2
Sketch 3.2.
Parametric form of a line.
40
3. Lining Up: 2D Lines
Deﬁne v = q − p, then the line is deﬁned as

5
1
.
+t
l(t) =
2
2
Generate ﬁve t-values as
t = i/4,
i = 0, . . . , 4.
Plug each t-value into the formulation for l(t):

1
;
i = 0, t = 0,
l(0) =
2

9/4
;
i = 1, t = 1/4, l(1/4) =
5/2

7/2
;
i = 2, t = 2/4, l(2/4) =
3

19/4
;
i = 3, t = 3/4, l(3/4) =
7/2

6
i = 4, t = 1,
l(1) =
.
4
Plot these values for yourself to verify them.
As you can see, the position of the point p and the direction and
length of the vector v determine which points on the line are generated as we increment through t ∈ [0, 1]. This particular artifact of
the parametric equation of a line is called the parametrization. The
parametrization is related to the speed at which a point traverses
the line. We may aﬀect this speed by scaling v: the larger the scale
factor, the faster the point’s motion!
3.3
Implicit Equation of a Line
Another way to represent the same line is to use the implicit equation
of a line. For this representation, we start with a point p, and as
illustrated in Sketch 3.3, construct a vector a that is perpendicular
to the line.
For any point x on the line, it holds that
a · (x − p) = 0.
(3.3)
3.3. Implicit Equation of a Line
41
This says that a and the vector (x − p) are perpendicular. If a has
unit length, it is called the normal to the line, and then (3.3) is the
point normal form of a line. Expanding this equation, we get
a1 x1 + a2 x2 + (−a1 p1 − a2 p2 ) = 0.
Commonly, this is written as
ax1 + bx2 + c = 0,
(3.4)
a = a1 ,
b = a2 ,
(3.5)
(3.6)
c = −a1 p1 − a2 p2 .
(3.7)
where
Sketch 3.3.
Implicit form of a line.
Equation (3.4) is called the implicit equation of the line.
Example 3.2
Following Sketch 3.4, suppose we know two points,

6
2
,
and q =
p=
4
2
on the line. To construct the coeﬃcients a, b, and c in (3.4), ﬁrst
form the vector

4
.
v =q−p=
2
Now construct a vector a that is perpendicular to v:

−v2
−2
a=
.
=
4
v1
(3.8)
Note, equally as well, we could have chosen a to be

2
.
−4
The coeﬃcients a and b in (3.5) and (3.6) are now deﬁned as a = −2
and b = 4. With p as deﬁned above, solve for c as in (3.7). In this
example,
c = 2 × 2 − 4 × 2 = −4.
The implicit equation of the line is complete:
−2×1 + 4×2 − 4 = 0.
Sketch 3.4.
Implicit construction.
42
3. Lining Up: 2D Lines
The implicit form is very useful for deciding if an arbitrary point lies
on the line. To test if a point x is on the line, just plug its coordinates
into (3.4). If the value f of the left-hand side of this equation,
f = ax1 + bx2 + c,
is zero then the point is on the line.
A numerical caveat is needed here. Checking equality with ﬂoating
point numbers should never be done. Instead, a tolerance around
zero must be used. What is a meaningful tolerance in this situation?
We’ll see in Section 3.6 that
d=
f
a
(3.9)
reﬂects the true distance of x to the line. Now the tolerance has a
physical meaning, which makes it much easier to specify. Sketch 3.3
illustrates the physical relationship of this tolerance to the line.
The sign of d indicates on which side of the line the point lies. This
sign is dependent upon the deﬁnition of a. (Remember, there were
two possible orientations.) Positive d corresponds to the point on the
side of the line to which a points.
Example 3.3
Let’s continue with our example for the line
−2×1 + 4×2 − 4 = 0,
as illustrated in Sketch 3.4. We want to test if the point

0
x=
1
lies on the line. First, calculate

√
a = −22 + 42 = 20.
The distance is
√
√
d = (−2 × 0 + 4 × 1 − 4)/ 20 = 0/ 20 = 0,
which indicates the point is on the line.
3.3. Implicit Equation of a Line
Test the point
43

0
.
x=
3
For this point,
√
√
d = (−2 × 0 + 4 × 3 − 4)/ 20 = 8/ 20 ≈ 1.79.
Checking Sketch 3.3, this is a positive number, indicating that it is
on the same side of the line as the direction of a. Check for yourself
that d does indeed reﬂect the actual distance of this point to the line.

Test the point
0
.
x=
0
Calculating the distance for this point, we get
√
√
d = (−2 × 0 + 4 × 0 − 4)/ 20 = −4/ 20 ≈ −0.894.
Checking Sketch 3.3, this is a negative number, indicating it is on the
opposite side of the line as the direction of a.
From Example 3.3, we see that if we want to know the distance
of many points to the line, it is more economical to represent the
implicit line equation with each coeﬃcient divided by a,
ax1 + bx2 + c
= 0,
a
which we know as the point normal form. The point normal form of
the line from the example above is
2
4
4
− √ x1 + √ x2 − √ = 0.
20
20
20
Examining (3.4) you might notice that a horizontal line takes the
form
bx2 + c = 0.
This line intersects the e2 -axis at −c/b. A vertical line takes the form
ax1 + c = 0.
This line intersects the e1 -axis at −c/a. Using the implicit form, these
lines are in no need of special handling.
44
3. Lining Up: 2D Lines
3.4
Explicit Equation of a Line
The explicit equation of a line is the third possible representation.
The explicit form is closely related to the implicit form in (3.4). It
expresses x2 as a function of x1 : rearranging the implicit equation
we have
a
c
x2 = − x1 − .
b
b
A more typical way of writing this is
x2 = âx1 + b̂,
where â = −a/b and b̂ = −c/b.
The coeﬃcients have geometric meaning: â is the slope of the line
and b̂ is the e2 -intercept. Sketch 3.5 illustrates the geometry of the
coeﬃcients for the line
x2 = 1/3×1 + 1.
Sketch 3.5.
A line in explicit form.
The slope measures the steepness of the line as a ratio of the change
in x2 to a change in x1 : “rise/run,” or more precisely tan(θ). The
e2 -intercept indicates that the line passes through (0, b̂).
Immediately, a drawback of the explicit form is apparent. If the
“run” is zero then the (vertical) line has inﬁnite slope. This makes
life very diﬃcult when programming! When we study transformations
(e.g., changing the orientation of some geometry) in Chapter 6, we
will see that inﬁnite slopes actually arise often.
The primary popularity of the explicit form comes from the study
of calculus. Additionally, in computer graphics, this form is popular
when pixel calculation is necessary. Examples are Bresenham’s line
drawing algorithm and scan line polygon ﬁll algorithms (see [10]).
3.5 Converting Between Parametric and
Implicit Equations
As we have discussed, there are advantages to both the parametric
and implicit representations of a line. Depending on the geometric
algorithm, it may be convenient to use one form rather than the other.
We’ll ignore the explicit form, since as we said, it isn’t very useful for
general 2D geometry.
3.5. Converting Between Parametric and Implicit Equations
3.5.1
Parametric to Implicit
Given: The line l in parametric form,
l : l(t) = p + tv.
Find: The coeﬃcients a, b, c that deﬁne the implicit equation of the
line
l : ax1 + bx2 + c = 0.
Solution: First form a vector a that is perpendicular to the vector v.
Choose

−v2
a=
.
v1
This determines the coeﬃcients a and b, as in (3.5) and (3.6), respectively. Simply let a = a1 and b = a2 . Finally, solve for the coeﬃcient
c as in (3.7). Taking p from l(t) and a, form
c = −(a1 p1 + a2 p2 ).
We stepped through a numerical example of this in the derivation
of the implicit form in Section 3.3, and it is illustrated in Sketch 3.4.
In this example, l(t) is given as

4
2
.
+t
l(t) =
2
2
3.5.2
Implicit to Parametric
Given: The line l in implicit form,
l : ax1 + bx2 + c = 0.
Find: The line l in parametric form,
l : l(t) = p + tv.
Solution: Recognize that we need one point on the line and a vector parallel to the line. The vector is easy: simply form a vector
perpendicular to a of the implicit line. For example, we could set

b
.
v=
−a
45
46
3. Lining Up: 2D Lines
Next, ﬁnd a point on the line. Two candidate points are the intersections with the e1 – or e2 -axis,

0
−c/a
,
or
−c/b
0
respectively. For numerical stability, let’s choose the intersection closest to the origin. Thus, we choose the former if |a| > |b|, and the latter
otherwise.
Example 3.4
Revisit the numerical example from the implicit form derivation in
Section 3.3; it is illustrated in Sketch 3.4. The implicit equation of
the line is
−2×1 + 4×2 − 4 = 0.
We want to ﬁnd a parametric equation of this line,
l : l(t) = p + tv.
First form
v=

4
.
2
Now determine which is greater in absolute value, a or b. Since
| − 2| < |4|, we choose 0 0 . = p= 1 4/4 The parametric equation is 4 0 . +t l(t) = 2 1 The implicit and parametric forms both allow an inﬁnite number of representations for the same line. In fact, in the example we just ﬁnished, the loop parametric → implicit → parametric produced two diﬀerent parametric forms. We started with 4 2 , +t l(t) = 2 2 3.6. Distance of a Point to a Line 47 and ended with l(t) = 4 0 . +t 2 1 We could have just as easily generated the line −4 0 , +t l(t) = −2 1 if v was formed with the rule v= −b . a Sketch 3.6 illustrates the ﬁrst and third parametric representations of this line. These three parametric forms represent the same line! However, the manner in which the lines will be traced will diﬀer. This is referred to as the parametrization of the line. We already encountered this concept in Section 3.2. 3.6 Distance of a Point to a Line If you are given a point r and a line l, how far is that point from the line? For example, as in Figure 3.3 (left), suppose a robot will travel along the line and the points represent objects in the room. The robot needs a certain clearance as it moves, thus we must check that no point is closer than a given tolerance, thus it is necessary to check the distance of each point to the line. In Section 2.8 on orthogonal Figure 3.3. Left: robot path application where clearance around the robot’s path must be measured. Right: measuring the perpendicular distance of each point to the line. Sketch 3.6. Two parametric representations for the same line. 48 3. Lining Up: 2D Lines projections, we learned that the smallest distance d(r, l) of a point to a line is the orthogonal or perpendicular distance. This distance is illustrated in Figure 3.3 (right). 3.6.1 Starting with an Implicit Line Suppose our problem is formulated as follows: Given: A line l in implicit form deﬁned by (3.3) or (3.4) and a point r. Find: d(r, l), or d for brevity. Solution: The implicit line is given by coeﬃcients a, b, and c, and thus also the vector a . a= b d= ar1 + br2 + c , a or in vector notation d= a · (r − p) , a where p is a point on the line. Let’s investigate why this is so. Recall that the implicit equation of a line was derived through use of the dot product a · (x − p) = 0, Sketch 3.7. Distance point to line. as in (3.3); a line is given by a point p and a vector a normal to the line. Any point x on the line will satisfy this equality. As in Sketch 3.7, we now consider a point r that is clearly not on the line. As a result, the equality will not be satisﬁed; however, let’s assign a value v to the left-hand side: v = a · (r − p). To simplify, deﬁne w = r − p, as in Sketch 3.7. Recall the deﬁnition of the dot product in (2.19) as v · w = vw cos θ. Thus, the expression for v becomes v = a · w = aw cos(θ). (3.10) 3.6. Distance of a Point to a Line 49 The right triangle in Sketch 3.7 allows for an expression for cos(θ) as cos(θ) = d . w Substituting this into (3.10), we have v = ad. This indicates that the actual distance of r to the line is a · (r − p) ar1 + br2 + c v = = . d= a a a (3.11) If many points will be checked against a line, it is advantageous to store the line in point normal form. This means that a = 1, eliminating the division in (3.11). Example 3.5 Start with the line and the point l : 4x1 + 2x2 − 8 = 0; r= 5 . 3 Find the distance from r to the line. (Draw your own sketch for this example, similar to Sketch 3.7.) First, calculate √ a = 42 + 22 = 2 5. Then the distance is 4×5+2×3−8 9 √ = √ ≈ 4.02. 2 5 5 As another exercise, let’s rewrite the line in point normal form with coeﬃcients 4 2 â = √ = √ , 2 5 5 1 2 b̂ = √ = √ , 2 5 5 −8 4 c = √ = −√ , ĉ = a 2 5 5 thus making the point normal form of the line 1 4 2 √ x1 + √ x2 − √ = 0. 5 5 5 d(r, l) = 50 3. Lining Up: 2D Lines 3.6.2 Starting with a Parametric Line Alternatively, suppose our problem is formulated as follows: Given: A line l in parametric form, deﬁned by a point p and a vector v, and a point r. Find: d(r, l), or d for brevity. Again, this is illustrated in Sketch 3.7. Solution: Form the vector w = r − p. Use the relationship d = w sin(α). Later in Section 8.2, we will see how to express sin(α) directly in terms of v and w; for now, we express it in terms of the cosine: sin(α) = 1 − cos(α)2 , and as before v·w . vw Thus, we have deﬁned the distance d. cos(α) = Example 3.6 We’ll use the same line as in the previous example, but now it will be given in parametric form as 2 0 . +t l(t) = −4 4 We’ll also use the same point r= 5 . 3 Add any new vectors for this example to the sketch you drew for the previous example. First create the vector 5 0 5 . = − w= −1 4 3 √ √ Next calculate w = 26 and v = 20. Compute 5 2 · −1 −4 cos(α) = √ √ ≈ 0.614. 26 20 3.7. The Foot of a Point 51 Thus, the distance to the line becomes √ d(r, l) ≈ 26 1 − (0.614)2 ≈ 4.02, which rightly produces the same result as the previous example. 3.7 The Foot of a Point Section 3.6 detailed how to calculate the distance of a point from a line. A new question arises: which point on the line is closest to the point? This point will be called the foot of the given point. If you are given a line in implicit form, it is best to convert it to parametric form for this problem. This illustrates how the implicit form is handy for testing if a point is on the line; however, it is not as handy for ﬁnding points on the line. The problem at hand is thus: Given: A line l in parametric form, deﬁned by a point p and a vector v, and another point r. Find: The point q on the line that is closest to r. (See Sketch 3.8.) Solution: The point q can be deﬁned as q = p + tv, (3.12) so our problem is solved once we have found the scalar factor t. From Sketch 3.8, we see that cos(θ) = tv , w where w = r − p. Using cos(θ) = we ﬁnd v·w , vw v·w t= . v2 Example 3.7 Given: The parametric line l deﬁned as 0 0 , +t l(t) = 2 1 Sketch 3.8. Closest point q on line to point r. 52 3. Lining Up: 2D Lines and point 3 . r= 4 Find: The point q on l that is closest to r. This example is easy enough to ﬁnd the answer by simply drawing a sketch, but let’s go through the steps. Solution: Deﬁne the vector w = r−p = 3 0 3 . = − 3 1 4 Compute v · w = 6 and v = 2. Thus, t = 3/2 and 0 . q= 4 2 . Try this example with r = −1 3.8 A Meeting Place: Computing Intersections Finding a point in common between two lines is done many times over in a CAD or graphics package. Take for example Figure 3.4: the top part of the ﬁgure shows a great number of intersecting lines. In order to color some of the areas, as in the bottom part of the ﬁgure, it is necessary to know the intersection points. Intersection problems arise in many other applications. The ﬁrst question to ask is what type of information do you want: • Do you want to know merely whether the lines intersect? • Do you want to know the point at which they intersect? • Do you want a parameter value on one or both lines for the intersection point? The particular question(s) you want to answer along with the line representation(s) will determine the best method for solving the intersection problem. 3.8. A Meeting Place: Computing Intersections 53 Figure 3.4. Intersecting lines: the top figure may be drawn without knowing where the shown lines intersect. By finding line/line intersections (bottom), it is possible to color areas— creating an artistic image! 3.8.1 Parametric and Implicit We then want to solve the following: Given: Two lines l1 and l2 : l1 : l1 (t) = p + tv l2 : ax1 + bx2 + c = 0. Find: The intersection point i. See Sketch 3.9 for an illustration.1 Solution: We will approach the problem by ﬁnding the speciﬁc parameter t̂ with respect to l1 of the intersection point. This intersection point, when inserted into the equation of l2 , will cause the left-hand side to evaluate to zero: a[p1 + t̂v1 ] + b[p2 + t̂v2 ] + c = 0. 1 In Section 3.3, we studied the conversion from the geometric elements of a point q and perpendicular vector a to the implicit line coeﬃcients. Sketch 3.9. Parametric and implicit line intersection. 54 3. Lining Up: 2D Lines This is one equation and one unknown! Just solve for t̂, t̂ = −c − ap1 − bp2 , av1 + bv2 (3.13) then i = l(t̂). But wait—we must check if the denominator of (3.13) is zero before carrying out this calculation. Besides causing havoc numerically, what else does a zero denominator infer? The denominator denom = av1 + bv2 can be rewritten as denom = a · v. We know from (2.7) that a zero dot product implies that two vectors are perpendicular. Since a is perpendicular to the line l2 in implicit form, the lines are parallel if a · v = 0. Of course, we always check for equality within a tolerance. A physically meaningful tolerance is best. Thus, it is better to check the quantity a·v cos(θ) = ; (3.14) av the tolerance will be the cosine of an angle. It usually suﬃces to use a tolerance between cos(0.1◦ ) and cos(0.5◦ ). Angle tolerances are particularly nice to have because they are dimension independent. Note that we do not need to use the actual angle, just the cosine of the angle. If the test in (3.14) indicates the lines are parallel, then we might want to determine if the lines are identical. By simply plugging in the coordinates of p into the equation of l2 , and computing, we get d= ap1 + bp2 + c . a If d is equal to zero (within tolerance), then the lines are identical. Example 3.8 Given: Two lines l1 and l2 , l1 : l2 : −2 0 +t −1 3 2x1 + x2 − 8 = 0. l1 (t) = 3.8. A Meeting Place: Computing Intersections 55 Find: The intersection point i. Create your own sketch and try to predict what the answer should be. Solution: Find the parameter t̂ for l1 as given in (3.13). First check the denominator: denom = 2 × (−2) + 1 × (−1) = −5. This is not zero, so we proceed to ﬁnd t̂ = 8−2×0−1×3 = −1. −5 Plug this parameter value into l1 to ﬁnd the intersection point: 2 −2 0 . = + −1 l1 (−1) = 4 −1 3 3.8.2 Both Parametric Another method for ﬁnding the intersection of two lines arises by using the parametric form for both, illustrated in Sketch 3.10. Sketch 3.10. Given: Two lines in parametric form, l1 : l2 : Intersection of lines in parametric form. l1 (t) = p + tv l2 (s) = q + sw. Note that we use two diﬀerent parameters, t and s, here. This is because the lines are independent of each other. Find: The intersection point i. Solution: We need two parameter values t̂ and ŝ such that p + t̂v = q + ŝw. This may be rewritten as t̂v − ŝw = q − p. (3.15) We have two equations (one for each coordinate) and two unknowns t̂ and ŝ. To solve for the unknowns, we could formulate an expression for t̂ using the ﬁrst equation, and substitute this expression into 56 3. Lining Up: 2D Lines the second equation. This then generates a solution for ŝ. Use this solution in the expression for t̂, and solve for t̂. (Equations like this are treated systematically in Chapter 5.) Once we have t̂ and ŝ, the intersection point is found by inserting one of these values into its respective parametric line equation. If the vectors v and w are linearly dependent, as discussed in Section 2.6, then it will not be possible to ﬁnd a unique t̂ and ŝ. The lines are parallel and possibly identical. Example 3.9 Given: Two lines l1 and l2 , −2 0 +t l1 : l1 (t) = −1 3 −1 4 . l2 : l2 (s) = +s 2 0 Find: The intersection point i. This means that we need to ﬁnd t̂ and ŝ such that l1 (t̂) = l2 (ŝ).2 Again, create your own sketch and try to predict the answer. Solution: Set up the two equations with two unknowns as in (3.15). t̂ 0 4 −1 −2 . − = − ŝ 3 0 2 −1 Solve these equations, resulting in t̂ = −1 and ŝ = 2. Plug these values into the line equations to verify the same intersection point is produced for each: 2 −2 0 = + −1 4 −1 3 2 −1 4 . l2 (2) = = +2 4 2 0 l1 (−1) = 2 Really we only need t̂ or ŝ to ﬁnd the intersection point. 3.8. A Meeting Place: Computing Intersections 3.8.3 57 Both Implicit And yet a third method: Given: Two lines in implicit form, l1 : ax1 + bx2 + c = 0, l2 : āx1 + b̄x2 + c̄ = 0. As illustrated in Sketch 3.11, each line is geometrically given in terms of a point and a vector perpendicular to the line. Find: The intersection point x̂ i = x̂ = 1 x̂2 that simultaneously satisﬁes l1 and l2 . Solution: We have two equations ax̂1 + bx̂2 = −c, (3.16) āx�...

Turn in your highest-quality paper
Get a qualified writer to help you with

“ University of South Carolina 2D & 3D Local and Global Coordination Summary ”

Get high-quality paper

NEW! AI matching with writer

Are you stuck with your online class?

Get help from our team of writers!

Order Today