CGAL Arrangements and their applications. A step-by-step guide (Q625322): Difference between revisions

The Computational Geometry Algorithm Library CGAL is the result of the work of several research groups in Europe and Israel. The goal of these researchers was to promote research in computational geometry and translate the results into useful, reliable and efficient programs for industrial and academic applications. The authors of this book offer a good manual about how to use CGAL 2D Arrangements package to solve problems. The book is self-contained. It starts with describing the manner of obtaining CGAL, licensing matter and proceeds with teaching the reader the functionality of CGAL 2D Arrangements package in order to solve various classes of problems. The programs presented in this book are designer both to be used as they are and to be modified according to the requirements of similar but non-identic problems. Each problem is accompanied by the needed theoretical information on the concepts of algebra, geometry and computational geometry of curves, which make each chapter easy to read without going to other helping bibliographic material. The contents of this book is divided into eleven chapters, as it follows. Chapter 1, \textbf{Introduction}, discusses about geometric arrangements, generic programming, geometric computing and presents CGAL. Chapter 2, \textbf{Basic Arrangements}, deals with representation of arrangements, the DCEL and the main arrangement class. As a practical application the problem of obtaining silhouettes of polytopes is presented. Chapter 3, \textbf{Queries and Free Functions}, refers to issuing queries on an arrangement, some algorithmic frameworks (i.e. the Plane-Sweep Algorithm and the Zone Construction Algorithm), batched point-location, free insertion function, removing vertices and edges and vertical decomposition. The practical problem of decomposing an arrangement of line segments illustrates the use of this package. Chapter 4, entitled \textbf{Arrangements of Unbounded Curves}, refers to the representation of these arrangements and the point-line duality. It concludes with the solution of the problem of the minimum-area triangle. Chapter 5, \textbf{Arrangement-Traits Classes}, develops the hierarchy of traits-class concepts, the traits classes for line segments and linear objects, the polyline-traits class, the traits classes for algebraic curves and the traits-class decorators. The solution of the polygon orientation problem concludes this chapter. Chapter 6, entitled \textbf{Extending the Arrangement}, refers to the notification mechanism, extending the DCEL, overlaying arrangements and storing the curve history. The application of polygon repairing and Winding Numbers illustrates the techniques described in this section. Chapter 7, \textbf{Adapting to BOOST Graphs}, refers to how to adapt arrangement instances as BOOST graph by primal and dual representations. The application illustrating these techniques is about finding the largest common point sets under \(\varepsilon\)-congruence. Chapter 8, \textbf{Operations on (Curved) Polygons}, presents the manner of performing 2D Regularized Boolean Set-Operations package on point sets which represent either linear polygons or curved polygons. Two practical applications are fully solved: multiway operations on general polygons and obtaining silhouettes of polyhedra. Chapter 9, \textbf{Minkowski Sums and Offset Polygons}, deals with computing the Minkowski Sum of two polygons using either convolutions or by decomposition strategies. Also, the offsetting a polygon is discussed both by an exact method and using a guaranteed error bound technique. Two motion-planning applications conclude this chapter. Chapter 10, \textbf{Envelopes}, refers to representing and constructing the envelopes of curves in the plane and of surfaces in 3-space. Two applications are completely solved using the packages described in this chapter: the nearest jeep over time and the location of the farthest point. Chapter 11, entitled \textbf{Prospects}, is a closing chapter briefly discussing ongoing development as well as future directions for possible extension of the 2D Arrangements package and its relatives. The book contains a rich bibliography of 221 titles. Each chapter, with the exception of the first one, concludes with exercises divided into two categories according to their difficulty levels. This book is useful both to students and to mathematicians, engineers and researchers in all fields, which implement geometric algorithms.