Description

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 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 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 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(θ) vw

then θ = acos(s) where acos is short for arccosine. One word of

warning: in some math libraries, if s > 1 or s

−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 1 is similar: this scales v so

that it is elongated, which generates points “past” q. In the context

of linear interpolation, when 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|

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 : 4×1 + 2×2 − 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

2×1 + 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…

Purchase answer to see full

attachment

Order your essay today and save **15%** with the discount code: VACCINE