logo资料库

CGAL Arrangements and Their Applications A Step-by-Step Guide.pdf

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：3.55M 资料格式：pdf 举报 版权申诉
第1页 / 共311页
第2页 / 共311页
第3页 / 共311页
第4页 / 共311页
第5页 / 共311页
第6页 / 共311页
第7页 / 共311页
第8页 / 共311页
资料共311页，剩余部分请下载后查看
    001Download PDF (284.5 KB)front-matter
    CGAL Arrangements and Their Applications
    Contents
    Preface
    What This Book Contains
    What You Should Know before Reading This Book
    How to Obtain and Install Cgal
    License
    Style Conventions
    Exercises
    The Cover
    Errata
    Acknowledgments
    002Download PDF (274.2 KB)fulltext
    Bibliography
    Index
    003Download PDF (468.4 KB)fulltext
    Chapter 2 Basic Arrangements
    2.1 Representation of Arrangements: The Dcel
    2.2 The Main Arrangement Class
    2.2.1 Traversing the Arrangement
    Traversal Methods for an Arrangement Vertex
    Traversal Methods for an Arrangement Halfedge
    Traversal Methods for an Arrangement Face
    2.2.2 Modifying the Arrangement
    Inserting Non-Intersecting x-Monotone Curves
    Manipulating Isolated Vertices
    Manipulating Halfedges
    Advanced Insertion Functions
    2.2.3 Input/Output Functions
    Input/Output Stream
    Output Qt-Widget Stream
    2.3 Application: Obtaining Silhouettes of Polytopes
    2.4 Bibliographic Notes and Remarks
    2.5 Exercises
    004Download PDF (371.8 KB)fulltext
    Chapter 3 Queries and Free Functions
    3.1 Issuing Queries on an Arrangement
    3.1.1 Point-Location Queries
    Choosing a Point-Location Strategy
    3.1.2 Vertical Ray Shooting
    3.2 Two Algorithmic Frameworks: Plane Sweep and Zone Construction
    The Plane-Sweep Algorithm
    The Zone-Construction Algorithm
    3.3 Batched Point-Location
    3.4 Free Insertion Functions
    3.4.1 Incremental Insertion Functions
    Inserting Non-Intersecting Curves
    Inserting (Possibly) Intersecting x-Monotone Curves
    Inserting General Curves
    Inserting Points
    3.4.2 Aggregate Insertion Functions
    3.5 Removing Vertices and Edges
    3.6 Vertical Decomposition
    3.6.1 Application: Decomposing an Arrangement of Line Segments
    3.7 Bibliographic Notes and Remarks
    3.8 Exercises
    005Download PDF (305.5 KB)fulltext
    Chapter 4 Arrangements of Unbounded Curves
    4.1 Representing Arrangements of Unbounded Curves
    4.1.1 Basic Manipulation and Traversal Methods
    4.1.2 Free Functions
    4.2 Point-Line Duality
    4.2.1 Application: Minimum-Area Triangle
    4.2.2 A Note on the Input Precision
    4.3 Bibliographic Notes and Remarks
    4.4 Exercises
    006Download PDF (924.6 KB)fulltext
    Chapter 5 Arrangement-Traits Classes
    5.1 The Hierarchy of Traits-Class Concepts
    5.1.1 The Basic Concept
    5.1.2 Supporting Intersections
    5.1.3 Supporting Arbitrary Curves
    5.1.4 The Landmark Concept
    5.1.5 Supporting Unbounded Curves
    5.1.6 The Traits Adaptor
    5.2 Traits Classes for Line Segments and Linear Objects
    5.2.1 The Caching Segment-Traits Class
    5.2.2 The Non-Caching Segment-Traits Class
    5.2.3 The Linear-Traits Class
    5.3 The Polyline-Traits Class
    5.4 Traits Classes for Algebraic Curves
    5.4.1 A Traits Class for Circular Arcs and Line Segments
    5.4.2 A Traits Class for Conic Arcs
    5.4.3 A Traits Class for Arcs of Rational Functions
    5.4.4 A Traits Class for Planar Bézier Curves
    5.4.5 A Traits Class for Planar Algebraic Curves of Arbitrary Degree
    5.5 Traits-Class Decorators
    5.6 Application: Polygon Orientation
    5.7 Bibliographic Notes and Remarks
    5.8 Exercises
    007Download PDF (455.8 KB)fulltext
    Chapter 6 Extending the Arrangement
    6.1 The Notification Mechanism
    6.2 Extending the Dcel
    6.2.1 Extending the Dcel Faces
    6.2.2 Extending All the Dcel Records
    6.2.3 Input/Output for Arrangements with Auxiliary Data
    6.3 Overlaying Arrangements
    6.4 Storing the Curve History
    6.4.1 Traversing an Arrangement with History
    6.4.2 Modifying an Arrangement with History
    6.4.3 Input/Output for Arrangements with Curve History
    6.5 Application: Polygon Repairing and Winding Numbers
    6.6 Bibliographic Notes and Remarks
    6.7 Exercises
    008Download PDF (265.9 KB)fulltext
    Chapter 7 Adapting to Boost Graphs
    7.1 The Primal Arrangement Representation
    7.2 The Dual Arrangement Representation
    7.3 Application: Largest Common Point Sets under -Congruence
    7.4 Bibliographic Notes and Remarks
    7.5 Exercises
    009Download PDF (710.0 KB)fulltext
    Chapter 8 Operations on (Curved) Polygons
    8.1 Operations on Linear Polygons
    8.1.1 Polygons with Holes
    8.1.2 Operations on Polygons with Holes
    8.1.3 Point Containment and Non-Regularized Operations
    8.1.4 Connecting Holes
    8.1.5 Operations on Polygon Sets
    8.1.6 A Sequence of Set Operations
    8.1.7 Inserting Non-Intersecting Polygons
    8.1.8 Performing Multiway Operations
    8.2 Operations on Curved Polygons
    8.2.1 The Traits-Class Concepts
    8.2.2 Operations on Polygons with Circular Arcs
    8.2.3 General-Polygon Set Traits-Adaptor
    8.3 Application: Multiway Operations on General Polygons
    8.4 Application: Obtaining Silhouettes of Polyhedra
    8.5 Bibliographic Notes and Remarks
    8.6 Exercises
    010Download PDF (577.9 KB)fulltext
    Chapter 9 Minkowksi Sums and Offset Polygons
    9.1 Computing the Minkowski Sum of Two Polygons
    9.1.1 Computing Minkowski Sum Using Convolutions
    9.1.2 Decomposition Strategies
    9.2 Offsetting a Polygon
    9.2.1 Approximating the Offset with a Guaranteed Error Bound
    9.2.2 Computing the Exact Offset
    9.3 Motion-Planning Applications
    9.3.1 Application: A Translating Polygonal Robot
    9.3.2 Application: Coordinating Two Disc Robots
    9.4 Bibliographic Notes and Remarks
    9.5 Exercises
    011Download PDF (492.3 KB)fulltext
    Chapter 10 Envelopes
    10.1 Envelopes of Curves in the Plane
    10.1.1 Representing the Envelope
    10.1.2 Constructing the Envelope Diagram
    10.1.3 The Envelope-Software Components
    10.1.4 Using the Traits Classes
    10.2 Application: Nearest Jeep over Time
    10.3 Envelopes of Surfaces in 3-Space
    10.3.1 The Envelope-Traits Concept
    10.3.2 Using the Envelope-Traits Classes
    10.4 Application: Locating the Farthest Point
    10.5 Bibliographic Notes and Remarks
    10.6 Exercises
    012Download PDF (246.3 KB)fulltext
    Chapter 11 Prospects
    11.1 Arrangements on Curved Surfaces
    11.2 Higher-Dimensional Arrangements
    11.3 Fixed-Precision Geometric Computing
    11.4 More Applications
    11.5 Exercises
    013Download PDF (274.2 KB)back-matter
    Bibliography
    Index
    Geometry and Computing Series Editors Herbert Edelsbrunner Leif Kobbelt Konrad Polthier Editorial Advisory Board Jean-Daniel Boissonnat Gunnar Carlsson Bernard Chazelle Xiao-Shan Gao Craig Gotsman Leo Guibas Myung-Soo Kim Takao Nishizeki Helmut Pottmann Roberto Scopigno Hans-Peter Seidel Steve Smale Peter Schröder Dietrich Stoyan For further volumes: www.springer.com/series/7580
    •
    Efi Fogel • Dan Halperin • Ron Wein CGAL Arrangements and Their Applications A Step-by-Step Guide 123
    Ron Wein Tel Aviv University The Blavatnik School of Computer Science Schreiber Building 69978 Tel Aviv Israel wein_r@yahoo.com Efi Fogel Tel Aviv University The Blavatnik School of Computer Science Schreiber Building 69978 Tel Aviv Israel efif@post.tau.ac.il Dan Halperin Tel Aviv University The Blavatnik School of Computer Science Schreiber Building 69978 Tel Aviv Israel danha@post.tau.ac.il ISSN 1866-6795 ISBN 978-3-642-17282-3 DOI 10.1007/978-3-642-17283-0 Springer Heidelberg Dordrecht London New York e-ISSN 1866-6809 e-ISBN 978-3-642-17283-0 Library of Congress Control Number: 2011945423 ACM Computing Classification: I.3.5, F.2.2 Mathematics Subjects Classification (2000): 65Dxx, 68U05 Springer-Verlag Berlin Heidelberg 2012 c This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
    To Ilil, Adam, Shira, and Tom. E.F. To Gili and Naomi. D.H. To Hélène, Nogah, and Shir. R.W.
    •
    Contents Preface xi xi What This Book Contains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi What You Should Know before Reading This Book . . . . . . . . . . . . . . . . . . . . . How to Obtain and Install Cgal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi Style Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Exercises Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Errata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii 1 Introduction 1.1 Arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Generic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Concepts and Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Traits Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Generic and Object-Oriented Programming . . . . . . . . . . . . . . . . . . 1.2.4 Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Geometric Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Separation of Topology and Geometry . . . . . . . . . . . . . . . . . . . . . 1.3.2 Exact Geometric Computation . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Well-Behaved Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 The Computational Geometry Algorithm Library . . . . . . . . . . . . . . . . . . . 1.4.1 Cgal Chronicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Cgal Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 The Algebraic Foundations of Cgal . . . . . . . . . . . . . . . . . . . . . . 1.4.4 The Geometry Kernel of Cgal . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.5 The State of Cgal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.6 The Namespace of Cgal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Outline of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Basic Arrangements 2.1 Representation of Arrangements: The Dcel . . . . . . . . . . . . . . . . . . . . . . 2.2 The Main Arrangement Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Traversing the Arrangement . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Modifying the Arrangement . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Input/Output Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Application: Obtaining Silhouettes of Polytopes . . . . . . . . . . . . . . . . . . . 2.4 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 2 3 5 7 7 8 8 9 10 10 10 11 12 14 15 15 17 19 19 20 22 26 33 36 40 41 vii
    viii Contents 3 Queries and Free Functions 3.1 Issuing Queries on an Arrangement . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Point-Location Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Vertical Ray Shooting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Two Algorithmic Frameworks: Plane Sweep and Zone Construction . . . . . . . . . 3.3 Batched Point-Location . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Free Insertion Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Incremental Insertion Functions . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Aggregate Insertion Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Removing Vertices and Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Vertical Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1 Application: Decomposing an Arrangement of Line Segments . . . . . . . 3.7 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Arrangements of Unbounded Curves 4.1 Representing Arrangements of Unbounded Curves . . . . . . . . . . . . . . . . . . 4.1.1 Basic Manipulation and Traversal Methods . . . . . . . . . . . . . . . . . . 4.1.2 Free Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Point-Line Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Application: Minimum-Area Triangle . . . . . . . . . . . . . . . . . . . . 4.2.2 A Note on the Input Precision . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Exercises 43 43 43 47 48 50 51 52 55 57 58 59 63 64 67 67 69 72 73 74 79 81 81 5 Arrangement-Traits Classes 5.1 The Hierarchy of Traits-Class Concepts . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 The Basic Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Supporting Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 5.1.3 Supporting Arbitrary Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.4 The Landmark Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Supporting Unbounded Curves . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.5 5.1.6 The Traits Adaptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Traits Classes for Line Segments and Linear Objects . . . . . . . . . . . . . . . . . 5.2.1 The Caching Segment-Traits Class . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 The Non-Caching Segment-Traits Class . . . . . . . . . . . . . . . . . . . . 5.2.3 The Linear-Traits Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 The Polyline-Traits Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Traits Classes for Algebraic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 83 84 85 87 88 89 91 91 92 92 94 94 97 5.4.1 A Traits Class for Circular Arcs and Line Segments 98 5.4.2 A Traits Class for Conic Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.4.3 A Traits Class for Arcs of Rational Functions . . . . . . . . . . . . . . . . . 105 5.4.4 A Traits Class for Planar Bézier Curves . . . . . . . . . . . . . . . . . . . . 109 5.4.5 A Traits Class for Planar Algebraic Curves of Arbitrary Degree . . . . . . . 111 5.5 Traits-Class Decorators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.6 Application: Polygon Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.7 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6 Extending the Arrangement 129 6.1 The Notification Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.2 Extending the Dcel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.2.1 Extending the Dcel Faces . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.2.2 Extending All the Dcel Records . . . . . . . . . . . . . . . . . . . . . . . . 134
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料