Muutke küpsiste eelistusi

Robust and Error-Free Geometric Computing [Kõva köide]

  • Formaat: Hardback, 388 pages, kõrgus x laius: 234x156 mm, kaal: 694 g, 7 Tables, black and white; 61 Illustrations, black and white
  • Ilmumisaeg: 27-May-2020
  • Kirjastus: CRC Press
  • ISBN-10: 036735294X
  • ISBN-13: 9780367352943
Teised raamatud teemal:
Robust and Error-Free Geometric ComputingSuurem pilt
  • Formaat: Hardback, 388 pages, kõrgus x laius: 234x156 mm, kaal: 694 g, 7 Tables, black and white; 61 Illustrations, black and white
  • Ilmumisaeg: 27-May-2020
  • Kirjastus: CRC Press
  • ISBN-10: 036735294X
  • ISBN-13: 9780367352943
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780367352943.html
Märksõnad:
This is a how-to book for solving geometric problems robustly or error free in actual practice. The contents and accompanying source code are based on the feature requests and feedback received from industry professionals and academics who want both the descriptions and source code for implementations of geometric algorithms. The book provides a framework for geometric computing using several arithmetic systems and describes how to select the appropriate system for the problem at hand.

Key Features:











A framework of arithmetic systems that can be applied to many geometric algorithms to obtain robust or error-free implementations





Detailed derivations for algorithms that lead to implementable code





Teaching the readers how to use the book concepts in deriving algorithms in their fields of application





The Geometric Tools Library, a repository of well-tested code at the Geometric Tools website, https://www.geometrictools.com, that implements the book concepts
Preface xi
Trademarks xv
List of Figures
xvii
List of Tables
xix
Listings
xxi
1 Introduction
1(34)
1.1 Eigendecomposition for 3 × 3 Symmetric Matrices
6(16)
1.1.1 Computing the Eigenvalues
7(1)
1.1.2 Computing the Eigenvectors
7(1)
1.1.3 A Nonrobust Floating-Point Implementation
8(8)
1.1.4 A Robust Floating-Point Implementation
16(1)
1.1.4.1 Computing the Eigenvalues
17(2)
1.1.4.2 Computing the Eigenvectors
19(3)
1.1.5 An Error-Free Implementation
22(1)
1.2 Distance between Line Segments
22(13)
1.2.1 Nonparallel Segments
23(3)
1.2.2 Parallel Segments
26(1)
1.2.3 A Nonrobust Floating-Point Implementation
26(3)
1.2.4 A Robust Floating-Point Implementation
29(1)
1.2.4.1 Conjugate Gradient Method
29(1)
1.2.4.2 Constrained Conjugate Gradient Method
30(3)
1.2.5 An Error-Free Implementation
33(2)
2 Floating-Point Arithmetic
35(12)
2.1 Binary Encodings
36(1)
2.2 Binary Encoding of 32-bit Floating-Point Numbers
36(3)
2.3 Binary Encoding of 64-bit Floating-Point Numbers
39(2)
2.4 Rounding of Floating-Point Numbers
41(6)
2.4.1 Round to Nearest with Ties to Even
42(1)
2.4.2 Round to Nearest with Ties to Away
42(1)
2.4.3 Round toward Zero
43(1)
2.4.4 Round toward Positive
44(1)
2.4.5 Round toward Negative
44(1)
2.4.6 Rounding Support in C++
44(3)
3 Arbitrary-Precision Arithmetic
47(24)
3.1 Binary Scientific Notation
47(1)
3.2 Binary Scientific Numbers
48(3)
3.2.1 Addition
49(1)
3.2.2 Subtraction
50(1)
3.2.3 Multiplication
50(1)
3.3 Binary Scientific Rationals
51(1)
3.3.1 Addition and Subtraction
52(1)
3.3.2 Multiplication and Division
52(1)
3.4 Conversions
52(10)
3.4.1 Floating-Point Number to BSNumber
53(1)
3.4.2 BSNumber to Floating-Point Number
54(3)
3.4.3 BSRational to BSNumber of Specified Precision
57(3)
3.4.4 BSNumber to BSNumber of Specified Precision
60(2)
3.5 Performance Considerations
62(9)
3.5.1 Static Computation of Maximum Precision
62(1)
3.5.1.1 Addition and Subtraction
63(1)
3.5.1.2 Multiplication
64(4)
3.5.2 Dynamic Computation of Maximum Precision
68(1)
3.5.3 Memory Management
68(3)
4 Interval Arithmetic
71(18)
4.1 Arithmetic Operations
72(7)
4.2 Signs of Determinants
79(2)
4.3 Primal Queries
81(8)
4.3.1 Queries in 2D
81(4)
4.3.2 Queries in 3D
85(4)
5 Quadratic-Field Arithmetic
89(38)
5.1 Sources of Rounding Errors
90(4)
5.1.1 Rounding Errors when Normalizing Vectors
90(1)
5.1.2 Errors in Roots to Quadratic Equations
91(1)
5.1.3 Intersection of Line and Cone Frustum
91(3)
5.2 Real Quadratic Fields
94(4)
5.2.1 Arithmetic Operations
95(1)
5.2.2 Allowing for Non-Square-Free d
96(1)
5.2.3 Allowing for Rational d
97(1)
5.3 Comparisons of Quadratic Field Numbers
98(3)
5.4 Quadratic Fields with Multiple Square Roots
101(2)
5.4.1 Arithmetic Operations
101(1)
5.4.2 Composition of Quadratic Fields
102(1)
5.5 Estimating a Quadratic Field Number
103(24)
5.5.1 Estimating a Rational Number
103(1)
5.5.2 Estimating the Square Root of a Rational Number
104(3)
5.5.3 Estimating a 1-Root Quadratic Field Number
107(3)
5.5.4 Estimating a 2-Root Quadratic Field Number
110(1)
5.5.4.1 Two Nonzero Radical Coefficients
111(9)
5.5.4.2 Three Nonzero Radical Coefficients
120(7)
6 Numerical Methods
127(48)
6.1 Root Finding
127(14)
6.1.1 Function Evaluation
128(3)
6.1.2 Bisection
131(4)
6.1.3 Newton's Method
135(3)
6.1.4 Hybrid Newton-Bisection Method
138(1)
6.1.5 Arbitrary-Precision Newton's Method
139(2)
6.2 Polynomial Root Finding
141(24)
6.2.1 Discriminants
142(2)
6.2.2 Preprocessing the Polynomials
144(1)
6.2.3 Quadratic Polynomial
145(2)
6.2.4 Cubic Polynomial
147(1)
6.2.4.1 Nonsimple Real Roots
147(1)
6.2.4.2 One Simple Real Rxxrt
148(1)
6.2.4.3 Three Simple Real Roots
149(3)
6.2.5 Quartic Polynomial
152(1)
6.2.5.1 Processing the Root Zero
153(1)
6.2.5.2 The Biquadratic Case
153(1)
6.2.5.3 Multiplicity Vector (3, 1, 0, 0)
154(1)
6.2.5.4 Multiplicity Vector (2, 2, 0, 0)
154(1)
6.2.5.5 Multiplicity Vector (2, 1, 1, 0)
154(1)
6.2.5.6 Multiplicity Vector (1, 1, 1, 1)
155(5)
6.2.6 High-Degree Polynomials
160(1)
6.2.6.1 Bounding Root Sequences by Derivatives
161(1)
6.2.6.2 Bounding Roots by Sturm Sequences
162(2)
6.2.6.3 Root Counting by Descartes' Rule of Signs
164(1)
6.2.6.4 Real-Root Isolation
164(1)
6.3 Linear Algebra
165(10)
6.3.1 Systems of Linear Equations
165(4)
6.3.2 Eigendecomposition for 2 × 2 Symmetric Matrices
169(1)
6.3.3 Eigendecomposition for 3 × 3 Symmetric Matrices
170(2)
6.3.4 3D Rotation Matrices with Rational Elements
172(3)
7 Distance Queries
175(34)
7.1 Introduction
175(4)
7.1.1 The Quadratic Programming Problem
176(1)
7.1.2 The Linear Complementarity Problem
176(1)
7.1.3 The Convex Quadratic Programming Problem
177(1)
7.1.3.1 Eliminating Unconstrained Variables
177(1)
7.1.3.2 Reduction for Equality Constraints
178(1)
7.2 Lemke's Method
179(11)
7.2.1 Terms and Framework
180(1)
7.2.2 LCP with a Unique Solution
181(2)
7.2.3 LCP with Infinitely Many Solutions
183(2)
7.2.4 LCP with No Solution
185(1)
7.2.5 LCP with a Cycle
186(1)
7.2.6 Avoiding Cycles when Constant Terms are Zero
187(3)
7.3 Formulating a Geometric Query as a CQP
190(3)
7.3.1 Distance Between Oriented Boxes
190(1)
7.3.2 Test-Intersection of Triangle and Cylinder
191(2)
7.4 Implementation Details
193(16)
7.4.1 The LCP Solver
193(2)
7.4.2 Distance Between Oriented Boxes in 3D
195(2)
7.4.3 Test-Intersection of Triangle and Cylinder in 3D
197(2)
7.4.4 Accuracy Problems with Floating-Point Arithmetic
199(2)
7.4.5 Dealing with Vector Normalization
201(8)
8 Intersection Queries
209(92)
8.1 Method of Separating Axes
210(12)
8.1.1 Separation by Projection onto a Line
210(1)
8.1.2 Separation of Convex Polygons in 2D
211(3)
8.1.3 Separation of Convex Polyhedra in 3D
214(1)
8.1.4 Separation of Convex Polygons in 3D
215(3)
8.1.5 Separation of Moving Convex Objects
218(4)
8.1.6 Contact Set for Moving Convex Objects
222(1)
8.2 Triangles Moving with Constant Linear Velocity
222(11)
8.2.1 Two Moving Triangles in 2D
223(6)
8.2.2 Two Moving Triangles in 3D
229(4)
8.3 Linear Component and Sphere
233(6)
8.3.1 Test-Intersection Queries
234(1)
8.3.1.1 Line and Sphere
234(1)
8.3.1.2 Ray and Sphere
235(1)
8.3.1.3 Segment and Sphere
236(1)
8.3.2 Find-Intersection Queries
237(1)
8.3.2.1 Line and Sphere
237(1)
8.3.2.2 Ray and Sphere
237(1)
8.3.2.3 Segment and Sphere
238(1)
8.4 Linear Component and Box
239(20)
8.4.1 Test-Intersection Queries
240(1)
8.4.1.1 Lines and Boxes
240(3)
8.4.1.2 Rays and Boxes
243(3)
8.4.1.3 Segments and Boxes
246(3)
8.4.2 Find-Intersection Queries
249(1)
8.4.2.1 Liang Barsky Clipping
250(4)
8.4.2.2 Lines and Boxes
254(1)
8.4.2.3 Rays and Boxes
255(2)
8.4.2.4 Segments and Boxes
257(2)
8.5 Line and Cone
259(18)
8.5.1 Definition of Cones
259(2)
8.5.2 Practical Matters for Representing Infinity
261(1)
8.5.3 Definition of a Line, Ray and Segment
261(1)
8.5.4 Intersection with a Line
262(1)
8.5.4.1 Case c2 ≠ 0
262(1)
8.5.4.2 Case c2 = 0 and c1 ≠ 0
263(1)
8.5.4.3 Case c2 = 0 and c1 = 0
264(1)
8.5.5 Clamping to the Cone Height Range
264(1)
8.5.6 Pseudocode for Error-Free Arithmetic
265(1)
8.5.6.1 Intersection of Intervals
265(1)
8.5.6.2 Line-Cone Query
266(7)
8.5.7 Intersection with a Ray
273(1)
8.5.8 Intersection with a Segment
274(2)
8.5.9 Implementation using Quadratic-Field Arithmetic
276(1)
8.6 Intersection of Ellipses
277(16)
8.6.1 Ellipse Representations
277(1)
8.6.1.1 The Standard Form for an Ellipse
278(1)
8.6.1.2 Conversion to a Quadratic Equation
278(1)
8.6.2 Test-Intersection Query for Ellipses
279(3)
8.6.3 Find-Intersection Query for Ellipses
282(2)
8.6.3.1 Case d4 ≠ 0 and e(x) ≠ 0
284(1)
8.6.3.2 Case d4 ≠ 0 and e(x) = 0
285(2)
8.6.3.3 Case d4 = 0, d2 ≠ 0 and e2 ≠ 0
287(1)
8.6.3.4 Case d4 = 0, d2 ≠ 0 and e2 = 0
288(1)
8.6.3.5 Case d4 = 0 and d2 = 0
288(5)
8.7 Intersection of Ellipsoids
293(8)
8.7.1 Ellipsoid Representations
293(1)
8.7.1.1 The Standard Form for an Ellipsoid
293(1)
8.7.1.2 Conversion to a Quadratic Equation
294(1)
8.7.2 Test-Intersection Query for Ellipsoids
294(1)
8.7.3 Find-Intersection Query for Ellipsoids
294(1)
8.7.3.1 Two Spheres
295(1)
8.7.3.2 Sphere-Ellipsoid: 3-Zero Center
295(1)
8.7.3.3 Sphere-Ellipsoid: 2-Zero Center
296(2)
8.7.3.4 Sphere-Ellipsoid: 1-Zero Center
298(1)
8.7.3.5 Sphere-Ellipsoid: No-Zero Center
298(1)
8.7.3.6 Reduction to a Sphere-Ellipsoid Query
299(2)
9 Computational Geometry Algorithms
301(54)
9.1 Convex Hull of Points in 2D
301(14)
9.1.1 Incremental Construction
302(7)
9.1.2 Divide-and-Conquer Method
309(6)
9.2 Convex Hull of Points in 3D
315(6)
9.2.1 Incremental Construction
315(3)
9.2.2 Divide-and-Conquer Method
318(3)
9.3 Delaunay Triangulation
321(8)
9.3.1 Incremental Construction
322(1)
9.3.1.1 Inserting Points
323(1)
9.3.1.2 Linear Walks and Intrinsic Dimension
323(2)
9.3.1.3 The Insertion Step
325(2)
9.3.2 Construction by Convex Hull
327(2)
9.4 Minimum-Area Circle of Points
329(4)
9.5 Minimum-Volume Sphere of Points
333(2)
9.6 Minimum-Area Rectangle of Points
335(14)
9.6.1 The Exhaustive Search Algorithm
335(2)
9.6.2 The Rotating Calipers Algorithm
337(2)
9.6.2.1 Computing the Initial Rectangle
339(1)
9.6.2.2 Updating the Rectangle
340(1)
9.6.2.3 Distinct Supporting Vertices
341(1)
9.6.2.4 Duplicate Supporting Vertices
341(2)
9.6.2.5 Multiple Polygon Edges of Minimum Angle
343(2)
9.6.2.6 The General Update Step
345(1)
9.6.3 A Robust Implementation
345(1)
9.6.3.1 Avoiding Normalization
346(1)
9.6.3.2 Indirect Comparisons of Angles
347(1)
9.6.3.3 Updating the Support Information
347(1)
9.6.3.4 Conversion to a Floating-Point Rectangle
348(1)
9.7 Minimum-Volume Box of Points
349(6)
9.7.1 Processing Hull Faces
350(1)
9.7.1.1 Comparing Areas
351(1)
9.7.1.2 Comparing Volumes
351(1)
9.7.1.3 Comparing Angles
352(1)
9.7.2 Processing Hull Edges
352(1)
9.7.3 Conversion to a Floating-Point Box
353(2)
Bibliography 355(4)
Index 359
Dave Eberly is the Chief Technologist for Geometric Tools, a company that provides contracting and consulting services for software development in computational mathematics in the fields of geometry, graphics, and physics. Previously, he worked at Microsoft on various projects including multisensor cameras for volumetric video, Microsoft Surface Hub, Microsoft HoloLens, and the machine-learning-based Custom Vision Service associated with the Artificial Intelligence and Research Initiative. He also worked at Omnivor Inc., a start-up company that develops algorithms and software for volumetric video.