Muutke küpsiste eelistusi

E-raamat: Robust and Error-Free Geometric Computing

  • Formaat: 388 pages
  • Ilmumisaeg: 27-Feb-2021
  • Kirjastus: CRC Press
  • Keel: eng
  • ISBN-13: 9781000056624
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 58,49 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Robust and Error-Free Geometric ComputingSuurem pilt
  • Formaat: 388 pages
  • Ilmumisaeg: 27-Feb-2021
  • Kirjastus: CRC Press
  • Keel: eng
  • ISBN-13: 9781000056624
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

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



    • This is a how-to book for solving problems in actual practice. The contents and accompanying source code are based on the feature requests and feedback received from industry and academics who want both the descriptions and source code for hard-to-find implementations of geometric algorithms.
    Preface xi
    Trademarks xv
    List of Figures xvii
    List of Tables xix
    Listings xxi
    1 Introduction 1(34)
    1.1 Eigendecomposition for 3 x 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(6)
    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(4)
    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(6)
    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(17)
    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(5)
    6.2.4.1 Nonsimple Real Roots
    		147(1)
    6.2.4.2 One Simple Real Root
    		148(1)
    6.2.4.3 Three Simple Real Roots
    		149(3)
    6.2.5 Quartic Polynomial
    		152(8)
    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(5)
    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 x 2 Symmetric Matrices
    		169(1)
    6.3.3 Eigendecomposition for 3 x 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(2)
    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(3)
    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(2)
    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(9)
    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(10)
    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(2)
    8.5.4.1 Case c2 not = to 0
    		262(1)
    8.5.4.2 Case c2 = 0 and c1 not = to 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(8)
    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(2)
    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(11)
    8.6.3.1 Case d4 not = to 0 and e(x) not = to 0
    		284(1)
    8.6.3.2 Case d4 not = to 0 and e(x) = 0
    		285(2)
    8.6.3.3 Case d4 = 0, d2 not = to 0 and e2. not = to 0
    		287(1)
    8.6.3.4 Case d4 = 0, d2 not = to 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(7)
    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(5)
    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(8)
    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(4)
    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(2)
    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.
    Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
    Püsilink: https://www.kriso.ee/db/97810000566242e.html
    Märksõnad: