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 Bé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 René 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.

Moiré 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 Moiré 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 = âx1 + b̂,

where â = −a/b and b̂ = −c/b.

The coeﬃcients have geometric meaning: â 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
â = √ = √ ,
2 5
5
1
2
b̂ = √ = √ ,
2 5
5
−8
4
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 ŝ such that
p + t̂v = q + ŝw.
This may be rewritten as
t̂v − ŝw = q − p.
(3.15)
We have two equations (one for each coordinate) and two unknowns
t̂ and ŝ. 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 ŝ. 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 ŝ, 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 ŝ. 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
ŝ such that l1 (t̂) = l2 (ŝ).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
.
−
=
− ŝ
3
0
2
−1
Solve these equations, resulting in t̂ = −1 and ŝ = 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 ŝ 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 : ā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)
āx�...