1Release History 2=============== 3 4[Release 5.3](https://github.com/CGAL/cgal/releases/tag/v5.3) 5----------- 6 7Release date: July 2021 8 9### [General changes](https://doc.cgal.org/5.3/Manual/general_intro.html) 10 11- The support for the compiled version of CGAL is dropped. Only the header-only version is supported. 12 13- On Windows, the type used for `Exact_rational`, in `Epick` and indirectly (through `Lazy_exact_nt`) 14 `Epeck` may now be `boost::multiprecision::mpq_rational`, as has been the case on other platforms 15 for several releases. This depends on various options and is added to a list that includes 16 `mpq_class`, `CGAL::Gmpq`, `leda_rational` and `CGAL::Quotient<CGAL::MP_Float>`. 17 18### [Quadtrees, Octrees, and Orthtrees](https://doc.cgal.org/5.3/Manual/packages.html#PkgOrthtree) (new package) 19 20- This package implements a tree data structure in which each node encloses a hypercubic section 21 of space and each non-leave node has hypercubic children whose edge lengths are half its edge length. 22 Such a data structure is known as a quadtree in 2D, an octree in 3D, and is generalized 23 as an "orthtree" in higher dimensions. 24 25### [Triangulations on the Sphere](https://doc.cgal.org/5.3/Manual/packages.html#PkgTriangulationOnSphere2) (new package) 26 27- This package enables the construction and manipulation of Delaunay triangulations on the 2-sphere. 28 Triangulations are built incrementally and can be modified by insertion or removal of vertices. 29 Point location querying and primitives to build the dual Voronoi diagram are provided. 30 31### File Input / Output 32 33- Point set, polygon soup, and polygon mesh file I/O functions have been harmonized and documented: 34 - Point set I/O functions can be found in the packages [Point_set_processing_3](https://doc.cgal.org/5.3/Manual/packages.html#PkgPolygonMeshProcessing), and [Point_set_3](https://doc.cgal.org/5.3/Manual/packages.html#PkgPointSet3). 35 - Polygon mesh I/O functions can be found in the package [BGL](https://doc.cgal.org/5.3/Manual/packages.html#PkgBGL). 36 - Polygon soup I/O can be found in the package [Stream_support](https://doc.cgal.org/5.3/Manual/packages.html#PkgStreamSupport). 37 38A comprehensive list of the supported file formats is available in the Stream_support package 39[here](https://doc.cgal.org/5.3/Stream_support/index.html#IOstreamSupportedFormats); 40inversely, the following [page](https://doc.cgal.org/5.3/Stream_support/IOStreamSupportedFileFormats.html) 41can be used to find out which CGAL data structures can be used given a specific file format. 42 43### [Requirements](https://doc.cgal.org/5.3/Manual/thirdparty.html) 44 45- The CMake minimal version is now `3.14`. 46- The GNU compiler g++ versions 6 and 7 are no longer tested. Only version 8.3 or later are supported 47 48### [2D and 3D Linear Geometry Kernel](https://doc.cgal.org/5.3/Manual/packages.html#PkgKernel23) 49 50- Added `is_translation()`, `is_scaling()`, `is_reflection()`, and `is_rotation()` to the classes 51 [`Aff_transformation_2`](https://doc.cgal.org/5.3/Kernel_23/classCGAL_1_1Aff__transformation__2.html) 52 and [`Aff_transformation_3`](https://doc.cgal.org/5.3/Kernel_23/classCGAL_1_1Aff__transformation__3.html), 53 which enable determining if the transformations use a specialized representation internally. 54 55### [2D Regularized Boolean Set-Operations](https://doc.cgal.org/5.3/Manual/packages.html#PkgBooleanSetOperations2) 56- Added documentation for the free functions [`oriented_side(const Point_2& p, ....)`](https://doc.cgal.org/5.3/Boolean_set_operations_2/group__boolean__oriented__side.html) 57 that accept a point and a polygon. 58- Documentation has been improved across the whole package. 59 60### [Polygon Mesh Processing](https://doc.cgal.org/5.3/Manual/packages.html#PkgPolygonMeshProcessing) 61 62- Added the class [`CGAL::Polyhedral_envelope`](https://doc.cgal.org/5.3/Polygon_mesh_processing/structCGAL_1_1Polyhedral__envelope.html), 63 providing a way to quickly check if a primitive (point, segment, or triangle) 64 is within a polyhedral envelope around a set of triangles. It is based on the work of 65 Bolun Wang, Teseo Schneider, Yixin Hu, Marco Attene, and Daniele Panozzo. 66 "Exact and efficient polyhedral envelope containment check." (ACM Trans. Graph., 39-4, July 2020). 67- Added more functions in the [visitor of the corefinement based methods](https://doc.cgal.org/5.3/Polygon_mesh_processing/classPMPCorefinementVisitor.html) 68 to track all edge creations. 69 70### [Surface Mesh Topology](https://doc.cgal.org/5.3/Manual/packages.html#PkgSurfaceMeshTopologySummary) 71- Added the function [`CGAL::Surface_mesh_topology::Curves_on_surface_topology::is_homotopic_to_simple_cycle()`](https://doc.cgal.org/5.3/Surface_mesh_topology/classCGAL_1_1Surface__mesh__topology_1_1Curves__on__surface__topology.html#a8d7c4cba2cf2cff542f5cd93117233db), 72 which can be used to determine whehter a closed path on a surface mesh can be continously 73 transformed to a cycle without self intersection. 74 75### [Surface Mesh Simplification](https://doc.cgal.org/5.3/Manual/packages.html#PkgSurfaceMeshSimplification) 76- Added a filtering mechanism so that costly tests get only applied to the next candidate for the edge collapse. 77- Added the class [`Polyhedral_envelope_filter`](https://doc.cgal.org/5.3/Surface_mesh_simplification/classCGAL_1_1Surface__mesh__simplification_1_1Polyhedral__envelope__filter.html), 78 which enables to perform mesh simplification inside a polyhedral envelope of the input mesh. 79 80### [2D Polyline Simplification](https://doc.cgal.org/5.3/Manual/packages.html#PkgPolylineSimplification2) 81- When polylines have common subsequences of vertices, these subsequences may now be simplifified simultaneously. 82 83### [dD Triangulations](https://doc.cgal.org/5.3/Manual/packages.html#PkgTriangulations) 84- Added the function [`insert_if_in_star()`](https://doc.cgal.org/5.3/Triangulation/classCGAL_1_1Regular__triangulation.html#aa8df2d138f341939e834bcdd7cb6c71a) 85 to the class [`CGAL::Regular_triangulation`](https://doc.cgal.org/5.3/Triangulation/classCGAL_1_1Regular__triangulation.html), 86 which enables users to insert a point `p` in a regular triangulation on the condition that `p` 87 appears post-insertion in the star of a user-specified, existing vertex. 88 89### [2D and 3D Alpha Shapes](https://doc.cgal.org/5.3/Manual/packages.html#PkgAlphaShapes2) 90- **Breaking change**: The following deprecated classes have been removed: `Alpha_shape_euclidean_traits_2`, 91 `Weighted_alpha_shape_euclidean_traits_2`, `Alpha_shape_euclidean_traits_3`, and 92 `Weighted_alpha_shape_euclidean_traits_3`. All CGAL kernel can be used directly as models 93 of the concepts of the 2D and 3D Alpha Shape packages. 94 95### [Classification](https://doc.cgal.org/5.3/Manual/packages.html#PkgClassification) 96- **Breaking change**: the support for TensorFlow has been dropped; the 97 classifier `CGAL::TensorFlow::Neural_network_classifier` has been removed. 98 99 100[Release 5.2](https://github.com/CGAL/cgal/releases/tag/v5.2) 101----------- 102 103Release date: December 2020 104 105### [dD Geometry Kernel](https://doc.cgal.org/5.2/Manual/packages.html#PkgKernelD) 106 107- The kernels [`Epick_d`](https://doc.cgal.org/5.2/Kernel_d/structCGAL_1_1Epick__d.html) 108 and [`Epeck_d`](https://doc.cgal.org/5.2/Kernel_d/structCGAL_1_1Epeck__d.html) gain two new functors: 109 [`Compute_power_product_d`](https://doc.cgal.org/5.2/Kernel_d/classCGAL_1_1Epeck__d_1_1Compute__power__product__d.html) 110 and [`Construct_power_sphere_d`](https://doc.cgal.org/5.2/Kernel_d/classCGAL_1_1Epeck__d_1_1Construct__power__sphere__d.html), 111 to deal with weighted points. 112 113### [CGAL and the Boost Graph Library (BGL)](https://doc.cgal.org/5.2/Manual/packages.html#PkgBGL) 114 115- Added a convenience header, [`CGAL/boost/graph/graph_traits_inheritance_macros.h`](https://doc.cgal.org/5.2/BGL/graph__traits__inheritance__macros_8h.html), 116 which enables easily making any class inheriting from a model of a face graph concept, a model of the same concept. 117- Added the function [`can_add_face()`](https://doc.cgal.org/5.2/BGL/group__PkgBGLEulerOperations.html#ga7dc63595108097b6e28b04fe962135f0), 118 which tests whether a new face defined by a range of vertices can be added. 119 120### [3D Fast Intersection and Distance Computation (AABB Tree)](https://doc.cgal.org/5.2/Manual/packages.html#PkgAABBTree) 121 122- Added the move constructor and the assignment operator to the 123 [AABB Tree](https://doc.cgal.org/5.2/AABB_tree/classCGAL_1_1AABB__tree.html) class. 124 125### [2D Arrangements](https://doc.cgal.org/5.2/Manual/packages.html#PkgArrangementOnSurface2) 126 127- Replaced the use of legacy 128 [`CGAL::Object`](https://doc.cgal.org/5.2/STL_Extension/classCGAL_1_1Object.html) 129 to modern `boost::variant`. 130- Changed make-x-monotone return type from legacy 131 [`CGAL::Object`](https://doc.cgal.org/5.2/STL_Extension/classCGAL_1_1Object.html) 132 to `boost::variant` in all traits concepts and models. 133 As there exists an implicit conversion from `boost::variant` to `CGAL::Object`, 134 the new code is backward compatible. However, it is recommended that all calls 135 to the make-x-monotone functions are fixed to use the new return type. 136- Changed [`decompose()`](https://doc.cgal.org/5.2/Arrangement_on_surface_2/group__PkgArrangementOnSurface2Funcs.html#gae20b2917f6de15db9bf025f83abf8e89) 137 interface to use `boost::variant` instead of legacy 138 [`CGAL::Object`](https://doc.cgal.org/5.2/STL_Extension/classCGAL_1_1Object.html) 139 As explained above, the code is backward compatible. However, it is recommended 140 that all calls to `decompose()` are fixed to use the new interface. 141 142### [Surface Mesh](https://doc.cgal.org/5.2/Manual/packages.html#PkgSurfaceMesh) 143 144- Added the function [`clear_without_removing_property_maps()`](https://doc.cgal.org/5.2/Surface_mesh/classCGAL_1_1Surface__mesh.html#aad000a07a5ada30536f194b28b59d111) 145 to clear a mesh but keep all the created property maps added. 146- Added the functions [`remove_property_maps<Index_type>()`](https://doc.cgal.org/5.2/Surface_mesh/classCGAL_1_1Surface__mesh.html#a2a3dd8c01f7fba7b640d85bfd1c41d90) 147 and [`remove_all_property_maps()`](https://doc.cgal.org/5.2/Surface_mesh/classCGAL_1_1Surface__mesh.html#a5696da09300f3d0eafed117668bb3bec) 148 to remove all added property maps by index type or all of them respectively. 149- Added the functions [`set_recycle_garbage()`](https://doc.cgal.org/5.2/Surface_mesh/classCGAL_1_1Surface__mesh.html#a40ada5068bf6d529a511c46767dfd21d) 150 and [`does_recycle_garbage()`](https://doc.cgal.org/5.2/Surface_mesh/classCGAL_1_1Surface__mesh.html#a081a87aaf7e56e6b4f9afba99967f8f4) 151 to the class `Surface_mesh`. 152 153### [Polygon Mesh Processing](https://doc.cgal.org/5.2/Manual/packages.html#PkgPolygonMeshProcessing) 154 155- Added a visitor to the functions 156 [`CGAL::Polygon_mesh_processing::triangulate_face()`](https://doc.cgal.org/5.2/Polygon_mesh_processing/group__PMP__meshing__grp.html#ga70d65044f8c7309c24ade88fa280124a) 157 and [`CGAL::Polygon_mesh_processing::triangulate_faces()`](https://doc.cgal.org/5.2/Polygon_mesh_processing/group__PMP__meshing__grp.html#gacaaff4d520500c530d9c3d5ebe2a0760), 158 that enables the user to keep track of the newly created faces through the triangulation process. 159- Added an option in [`CGAL::Polygon_mesh_processing::corefine()`](https://doc.cgal.org/5.2/Polygon_mesh_processing/group__PMP__corefinement__grp.html#ga6447dee822aaf92016f34512ce0b3456), 160 [`CGAL::Polygon_mesh_processing::split()`](https://doc.cgal.org/5.2/Polygon_mesh_processing/group__PMP__corefinement__grp.html#gaa491feee9e41f725332bea0ea1215578) 161 and [`CGAL::Polygon_mesh_processing::clip()`](https://doc.cgal.org/5.2/Polygon_mesh_processing/group__PMP__corefinement__grp.html#ga30082762ba2d947cba304e2884d96a99) 162 functions, which enable the operations to be performed on a mesh with 163 self-intersections present in the intersection area. 164- Added an optional range parameter to [`CGAL::Polygon_mesh_processing::stitch_borders()`](https://doc.cgal.org/5.2/Polygon_mesh_processing/group__PMP__repairing__grp.html#ga8ae4352e67d2b099994ac8990c13bd41), 165 which can be used to specify which boundary cycles are eligible for stitching. 166 167### [Surface Mesh Parameterization](https://doc.cgal.org/5.2/Manual/packages.html#PkgSurfaceMeshParameterization) 168 169- Added a new parameterization method, [Iterative Authalic Parameterization](https://doc.cgal.org/5.2/Surface_mesh_parameterization/index.html#title11). 170 It is based on the work of Jain, Hardik, Manuel Wollhaf, and Olaf Hellwich, 171 "Learning to Reconstruct Symmetric Shapes using Planar Parameterization of 3D Surface." 172 (IEEE International Conference on Computer Vision Workshops, 2019). 173 174### [Classification](https://doc.cgal.org/5.2/Manual/packages.html#PkgClassification) 175 176- **Breaking change**: new IO format for the [`ETHZ::Random_Forest`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1ETHZ_1_1Random__forest__classifier.html) classifier: 177 a conversion function from the outdated format to the new one is provided. 178 179- Added new functions to the class [`CGAL::Classification::Evaluation`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Evaluation.html): 180 [`append()`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Evaluation.html#a20c5fc43af44c96ce0cae40375be934f) 181 to enrich the evaluation with additional results; 182 [`confusion()`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Evaluation.html#a706a85bb1deefee350ce71855bc023e9) 183 to access the confusion matrix; 184 output functions to save the evaluation to and `ASCII` or `HTML` stream. 185- Added a new operator, [`CGAL::Classification::feature_cast<>`](https://doc.cgal.org/5.2/Classification/group__PkgClassificationFeature.html#gaf4b1504270f25061f63f05743a17e5d1), 186 for easy conversions. 187- The classes [`CGAL::Classification::Feature_set`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Feature__set.html) 188 and [`CGAL::Classification::Label_set`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Label__set.html) 189 are now models of the concept [`Range`](https://doc.cgal.org/5.2/Circulator/classRange.html). 190- The class [`CGAL::Classification::Label`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Label.html) 191 now has attributes `index`, `standard_index` and `color`, 192 with automatic selection if the ASPRS standard names are used. 193- Added new functions in [`CGAL::Classification::Point_set_feature_iterator`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Point__set__feature__generator.html), 194 to enable users to select which features should be generated. 195- Added a new function, [`CGAL::Classification::Label_set::is_valid_ground_truth()`](https://doc.cgal.org/5.2/Classification/classCGAL_1_1Classification_1_1Label__set.html#adeb3b046f640c091b1f123e982386e43), 196 to help users check if a ground truth matches a given label set. 197 198### [Point Set Processing](https://doc.cgal.org/5.2/Manual/packages.html#PkgPointSetProcessing3) 199 200- Added a function [`CGAL::scanline_orient_normals()`](https://doc.cgal.org/5.2/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga221d4efde44f42aefe153cb927138efe), 201 which orients a point cloud by estimating a line of sight. 202 203### [3D Convex Hulls](https://doc.cgal.org/5.2/Manual/packages.html#PkgConvexHull3) 204 205- Added the function [`CGAL::halfspace_intersection_interior_point_3()`](https://doc.cgal.org/5.2/Convex_hull_3/group__PkgConvexHull3Functions.html#ga9a1ead3126e42fbf46ef269466cddc8f), 206 which can be used to retrieve the point that is the most interior a convex closed volume 207 defined by the intersection of a set of halfspaces. 208 209### [3D Triangulations](https://doc.cgal.org/5.2/Manual/packages.html#PkgTriangulation3) 210 211- Added new classes and functions to visit the cells and simplices intersected by a line segment, 212 see Sections [Segment Cell Iterator](https://doc.cgal.org/5.2/Triangulation_3/classCGAL_1_1Triangulation__3.html#amgrp0d087ed77bb99ca595c92d2cd2ab59b9) 213 and [Segment Simplex Iterator](https://doc.cgal.org/5.2/Triangulation_3/classCGAL_1_1Triangulation__3.html#amgrp2447c1d2dce281951a0a4d8aecd3f35d), respectively. 214 215 216[Release 5.1](https://github.com/CGAL/cgal/releases/tag/v5.1) 217----------- 218 219Release date: September 2020 220 221### [Tetrahedral Remeshing](https://doc.cgal.org/5.1/Manual/packages.html#PkgTetrahedralRemeshing) (new package) 222 223- This package implements a tetrahedral isotropic remeshing algorithm, 224 that improves the quality of tetrahedra in terms of dihedral angles, 225 while targeting a given edge length. 226 227 See also the associated [blog entry](https://www.cgal.org/2020/08/07/Tetrahedral-remeshing/). 228 229### [Surface Mesh Topology](https://doc.cgal.org/5.1/Manual/packages.html#PkgSurfaceMeshTopologySummary) (new package) 230 231- This package enables the computation of some topological invariants of surfaces, such as: 232 - test if two (closed) curves on a combinatorial surface are homotopic. Users can choose 233 between free homotopy and homotopy with fixed endpoints; 234 - test is a curve is contractible; 235 - compute shortest non-contractible cycles on a surface, with or without weights on edges. 236 237 See also the associated [blog entry](https://www.cgal.org/2020/05/08/Surface_mesh_topology/). 238 239### [Optimal Bounding Box](https://doc.cgal.org/5.1/Manual/packages.html#PkgOptimalBoundingBox) (new package) 240 241- This package implements an optimization algorithm that aims to construct a close approximation 242 of the *optimal bounding box* of a mesh or a point set, which is defined as the smallest 243 (in terms of volume) bounding box that contains a given mesh or point set. 244 245 See also the associated [blog entry](https://www.cgal.org/2020/04/20/Optimal_bounding_box/). 246 247### Installation 248 249- The CGAL\_Core library no longer requires `Boost.Thread`, even if the g++ compiler is used. 250- The minimal supported version of Boost is now 1.66.0. 251 252### [Tutorials](https://doc.cgal.org/5.1/Manual/tutorials.html) 253 254- Two new, detailed tutorials have been added: 255 - [Surface Reconstruction from Point Clouds](https://doc.cgal.org/5.1/Manual/tuto_reconstruction.html), 256 which goes over a typical full processing pipeline in a CGAL environment. 257 - [Geographic Information Systems (GIS)](https://doc.cgal.org/5.1/Manual/tuto_gis.html), 258 which demonstrates usage of CGAL data structures and algorithms in the context of a typical GIS application. 259 260 Both tutorials provide complete code. 261 262### [2D and 3D Linear Geometry Kernel](https://doc.cgal.org/5.1/Manual/packages.html#PkgKernel23) 263 264- Added the functor [`CompareSignedDistanceToLine_2`](https://doc.cgal.org/5.1/Kernel_23/classKernel_1_1CompareSignedDistanceToLine__2.html) 265 to the 2D/3D [`Kernel`](https://doc.cgal.org/5.1/Kernel_23/classKernel.html) concept to compare 266 the signed distance of two points to a line, or the line passing through two given points. 267 Corresponding functors in the model ([`Compare_signed_distance_to_line_2`](https://doc.cgal.org/5.1/Kernel_23/classKernel.html#a066d07dd592ac36ba7ee90988abd349f)) are also added. 268 269### [dD Geometry Kernel](https://doc.cgal.org/5.1/Manual/packages.html#PkgKernelD) 270 271- The kernels [`Epick_d`](https://doc.cgal.org/5.1/Kernel_d/structCGAL_1_1Epick__d.html) 272 and [`Epeck_d`](https://doc.cgal.org/5.1/Kernel_d/structCGAL_1_1Epeck__d.html) gain two new functors: 273 [`Power_side_of_bounded_power_sphere_d`](https://doc.cgal.org/5.1/Kernel_d/classCGAL_1_1Epeck__d_1_1Power__side__of__bounded__power__sphere__d.html) 274 and [`Compute_squared_radius_smallest_orthogonal_sphere_d`](https://doc.cgal.org/5.1/Kernel_d/classCGAL_1_1Epeck__d_1_1Compute__squared__radius__smallest__orthogonal__sphere__d.html). 275 Those are essential for the computation of weighted alpha-complexes. 276 277### [Surface Mesh](https://doc.cgal.org/5.1/Manual/packages.html#PkgSurfaceMesh) 278 279- **Breaking change**: The function [`CGAL::Surface_mesh::clear()`](https://doc.cgal.org/5.1/Surface_mesh/classCGAL_1_1Surface__mesh.html#a247d4ad3e6b106ae22e5306203812642) 280 now removes all non-default properties instead of just emptying them. 281 282### [CGAL and the Boost Graph Library (BGL)](https://doc.cgal.org/5.1/Manual/packages.html#PkgBGL) 283 284- Added the function [`CGAL::alpha_expansion_graphcut()`](https://doc.cgal.org/5.1/BGL/group__PkgBGLPartition.html#ga79c3f58b577af51d1140450729d38f22), 285 which regularizes a multi-label partition over a user-defined graph. 286- Added the function [`CGAL::regularize_face_selection_borders()`](https://doc.cgal.org/5.1/BGL/group__PkgBGLSelectionFct.html#gac71322b0cc7d7d59447531d5e5e345b6), 287 which uses this alpha expansion graphcut to regularize the borders of a selected faces on a triangle mesh. 288- Added the function [`CGAL::set_triangulation_ids()`](https://doc.cgal.org/5.1/BGL/group__BGLGraphExternalIndices.html#ga1a22cf8bdde32fcdf1a4a78966eed630), 289 which must be used to initialize vertex, edge, and face indices of a triangulation meant to be used with BGL algorithms. 290 291### [3D Fast Intersection and Distance Computation (AABB Tree)](https://doc.cgal.org/5.1/Manual/packages.html#PkgAABBTree) 292 293- The behavior of the internal search tree used to accelerate distance queries has changed: 294 usage of the internal search tree will now be enabled by default, and its construction 295 will be triggered by the first distance query. Automatic construction and usage can be disabled 296 by calling [`CGAL::AABB_tree::do_not_accelerate_distance_queries()`](https://doc.cgal.org/5.1/AABB_tree/classCGAL_1_1AABB__tree.html#abde62f52ccdf411847151aa5000ba4a4) 297 before the first distance query, and the tree can be built at any moment by calling 298 [`CGAL::AABB_tree::accelerate_distance_queries()`](https://doc.cgal.org/5.1/AABB_tree/classCGAL_1_1AABB__tree.html#a5d3877d3f2afbd09341eb4b8c230080b). 299- **Breaking change**: [`CGAL::AABB_tree::accelerate_distance_queries()`](https://doc.cgal.org/5.1/AABB_tree/classCGAL_1_1AABB__tree.html#a5d3877d3f2afbd09341eb4b8c230080b) 300 and [`CGAL::AABB_tree::do_not_accelerate_distance_queries()`](https://doc.cgal.org/5.1/AABB_tree/classCGAL_1_1AABB__tree.html#abde62f52ccdf411847151aa5000ba4a4) 301 are no longer `const` functions. 302 303### [2D Arrangements](https://doc.cgal.org/5.1/Manual/packages.html#PkgArrangementOnSurface2) 304 305 - Changed intersection return type from legacy [`CGAL::Object`](https://doc.cgal.org/5.1/STL_Extension/classCGAL_1_1Object.html) 306 to modern `boost::variant` in all traits concepts and models. 307 As there exists an implicit conversion from `boost::variant` to `CGAL::Object`, the 308 new code is backward compatible. However, it is recommended that all calls 309 to the intersection functions are fixed to use the new return type. 310 311### [2D Regularized Boolean Set-Operations](https://doc.cgal.org/5.1/Manual/packages.html#PkgBooleanSetOperations2) 312 313 - Changed intersection return type from legacy [`CGAL::Object`](https://doc.cgal.org/5.1/STL_Extension/classCGAL_1_1Object.html) 314 to modern `boost::variant` in the concept [`ArrDirectionalTraits::Intersect_2`](https://doc.cgal.org/5.1/Boolean_set_operations_2/namespaceArrDirectionalTraits.html) 315 and its models. 316 317### [2D Minkowski Sums](https://doc.cgal.org/5.1/Manual/packages.html#PkgMinkowskiSum2) 318 319 - Changed intersection return type from legacy [`CGAL::Object`](https://doc.cgal.org/5.1/STL_Extension/classCGAL_1_1Object.html) 320 to modern `boost::variant` in the (internally used) model `Arr_labeled_traits_2`. 321 322### [dD Spatial Searching](https://doc.cgal.org/5.1/Manual/packages.html#PkgSpatialSearchingD) 323 324- The kd-tree can now be built in parallel: [`CGAL::Kd_tree::build()`](https://doc.cgal.org/5.1/Spatial_searching/classCGAL_1_1Kd__tree.html#a8559dbe4d7136fbc8ebab5ee290cbe06) 325 is given an optional template parameter `ConcurrencyTag` (default 326 value remains [`CGAL::Sequential_tag`](https://doc.cgal.org/5.1/STL_Extension/structCGAL_1_1Sequential__tag.html) 327 for backward compatibility). 328- Improved the performance of the kd-tree in some cases: 329 - Not storing the points coordinates inside the tree usually 330 generates a lot of cache misses, leading to non-optimal 331 performance. This is the case for example 332 when indices are stored inside the tree, or to a lesser extent when the points 333 coordinates are stored in a dynamically allocated array (e.g., [`Epick_d`](https://doc.cgal.org/5.1/Kernel_d/structCGAL_1_1Epick__d.html) 334 with dynamic dimension) — we says "to a lesser extent" because the points 335 are re-created by the kd-tree in a cache-friendly order after its construction, 336 so the coordinates are more likely to be stored in a near-optimal order 337 on the heap. 338 In these cases, the new `EnablePointsCache` template parameter of the 339 [`CGAL::Kd_tree`](https://doc.cgal.org/5.1/Spatial_searching/classCGAL_1_1Kd__tree.html) 340 class can be set to `CGAL::Tag_true`. The points coordinates 341 will then be cached in an optimal way. This will increase memory 342 consumption but provides better search performance. See the updated 343 [`GeneralDistance`](https://doc.cgal.org/5.1/Spatial_searching/classGeneralDistance.html) 344 and [`FuzzyQueryItem`](https://doc.cgal.org/5.1/Spatial_searching/classFuzzyQueryItem.html) 345 concepts for additional requirements when using such a cache. 346 - In most cases (e.g., Euclidean distance), the distance computation 347 algorithm knows before its end that the distance will be greater 348 than or equal to some given value. This is used in the (orthogonal) 349 k-NN search to interrupt some distance computations before its end, 350 saving precious milliseconds, in particular in medium-to-high dimension. 351 352### [Intersecting Sequences of dD Iso-oriented Boxes](https://doc.cgal.org/5.1/Manual/packages.html#PkgBoxIntersectionD) 353 354- Added parallel versions of the functions 355 [`CGAL::box_intersection_d()`](https://doc.cgal.org/5.1/Box_intersection_d/group__PkgBoxIntersectionD__box__intersection__d.html) 356 and [`CGAL::box_self_intersection_d()`](https://doc.cgal.org/5.1/Box_intersection_d/group__PkgBoxIntersectionD__box__self__intersection__d.html). 357 358### [Spatial Sorting](https://doc.cgal.org/5.1/Manual/packages.html#PkgSpatialSorting) 359 360- Added parallel versions of the functions 361 [`CGAL::hilbert_sort()`](https://doc.cgal.org/5.1/Spatial_sorting/group__PkgSpatialSortingFunctions.html#ga9da67204747ac19dff65f9c9ff2fca9e) 362 and [`CGAL::spatial_sort()`](https://doc.cgal.org/5.1/Spatial_sorting/group__PkgSpatialSortingFunctions.html#ga7c597c11a3b3859234ff68526cead84d) 363 in 2D and 3D when the median policy is used. 364 The parallel versions use up to four threads in 2D, and up to eight threads in 3D. 365 366### [3D Convex Hulls](https://doc.cgal.org/5.1/Manual/packages.html#PkgConvexHull3) 367 368- A new overload for [`CGAL::convex_hull_3()`](https://doc.cgal.org/5.1/Convex_hull_3/group__PkgConvexHull3Functions.html#gaa02a3013808fc9a2e5e2f42b9fde8e30) 369 that takes a model of [`VertexListGraph`](https://doc.cgal.org/5.1/BGL/classVertexListGraph.html) has been added. 370- The long-deprecated function `CGAL::convex_hull_3_to_polyhedron_3()` has been removed. 371 The function [`CGAL::convex_hull_3_to_face_graph()`](https://doc.cgal.org/5.1/Convex_hull_3/group__PkgConvexHull3Functions.html#ga2750f7f197588ed643679835c748c671) 372 should be used instead. 373 374### [Polygon Mesh Processing](https://doc.cgal.org/5.1/Manual/packages.html#PkgPolygonMeshProcessing) 375 376- Added the function [`CGAL::Polygon_mesh_processing::volume_connected_component()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__orientation__grp.html#ga133e58280959c152770525f27bb42b91), 377 which can be used to get information about the nesting of the connected components of a given triangle mesh and about 378 the volumes defined. 379- Added the function [`CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__repairing__grp.html#gac544fcaba1d59d330a3a1536caff392a), 380 which can be used to remove connected components whose area or volume is under a certain threshold. 381 Area and volume thresholds are either specified by the user or deduced from the bounding box of the mesh. 382- Added a new named parameter for [`CGAL::Polygon_mesh_processing::keep_large_connected_components()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__keep__connected__components__grp.html#ga48e7b3e6922ee78cf8ce801e3e325d9a) 383 and [`CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__repairing__grp.html#gac544fcaba1d59d330a3a1536caff392a), 384 which can be used to perform a dry run of the operation, meaning that the function will return the number of connected 385 components that would be removed with the specified threshold, but without actually removing them. 386- Added the function [`CGAL::Polygon_mesh_processing::split()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__corefinement__grp.html#gaa491feee9e41f725332bea0ea1215578), 387 which can be used to split meshes along a mesh or a plane. 388- Added the function [`CGAL::Polygon_mesh_processing::split_connected_components()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__keep__connected__components__grp.html#ga9ddd1e4b915a4232b1ce5611985302aa) 389 to split a single mesh containing several connected components into several meshes containing one connected component. 390- Added the functions [`CGAL::Polygon_mesh_processing::merge_reversible_connected_components()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__orientation__grp.html#gae25c1198a89c53d5df2f29dd57fda5ca), 391 [`CGAL::Polygon_mesh_processing::duplicate_non_manifold_edges_in_polygon_soup()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__orientation__grp.html#ga2aa4f7b500dc51d1fc4747705a050946), 392 and [`CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_mesh()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__orientation__grp.html#ga31779672b3afd660664fc9a6c4fdf74d), 393 which can be helpful when repairing a polygon soup. 394- Added the function [`CGAL::Polygon_mesh_processing::sample_triangle_soup()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__distance__grp.html#gac7af41d13bf1a7c30852be266ac81db5), 395 which generates points on a triangle soup surface. 396- Added parallel versions of the functions [`CGAL::Polygon_mesh_processing::does_self_intersect()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__intersection__grp.html#gad9fe5d8b433545b69154f43935a11a3b) 397 and [`CGAL::Polygon_mesh_processing::self_intersections()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__intersection__grp.html#gaf19c80ec12cbff7ebe9e69453f1d40b8). 398- The function [`CGAL::Polygon_mesh_processing::stitch_borders()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__repairing__grp.html#ga8ae4352e67d2b099994ac8990c13bd41) 399 now returns the number of halfedge pairs that were stitched. 400- Added the function [`CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup()`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__repairing__grp.html#ga76648a509409ff3c3ad3f71eff8ce9d9). 401- The function [`CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh`](https://doc.cgal.org/5.1/Polygon_mesh_processing/group__PMP__repairing__grp.html#ga0dec58e8a0112791f72ebbe77bac074b) 402 now allows passing a point map (for the point range) and a vertex point map (for the polygon mesh) via named parameters. 403 404### [Point Set Processing](https://doc.cgal.org/5.1/Manual/packages.html#PkgPointSetProcessing3) 405 406- **Breaking change:** [`CGAL::remove_outliers()`](https://doc.cgal.org/5.1/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga1ab1dcee59caadde50572c5a504cc41a) 407 has been parallelized and thus has a new template parameter `ConcurrencyTag`. 408 To update your code simply add as first template parameter `CGAL::Sequential_tag` or `CGAL::Parallel_tag` 409 when calling this function. 410- Add a function [`CGAL::cluster_point_set()`](https://doc.cgal.org/5.1/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#gafee41d60b5a257ae034e9157d0af8e46) 411 that segments a point cloud into connected components based on a distance threshold. 412- Added wrapper functions for registration: 413 - [`CGAL::OpenGR::compute_registration_transformation()`](https://doc.cgal.org/5.1/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#gab81663c718960780ddb176aad845e8cd), 414 which computes the registration transformation for two point sets using the Super4PCS algorithm 415 implemented in the third party library [OpenGR](https://storm-irit.github.io/OpenGR/index.html). 416 - [`CGAL::OpenGR::register_point_sets()`](https://doc.cgal.org/5.1/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga6194087f512e4e23dd945a9364d0931d), 417 which computes the registration transformation for two point sets using the Super4PCS algorithm 418 implemented in the third party library [OpenGR](https://storm-irit.github.io/OpenGR/index.html), 419 and registers the points sets by transforming the data point set using the computed transformation. 420 - [`CGAL::pointmatcher::compute_registration_transformation()`](https://doc.cgal.org/5.1/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#gaf75af5c1634fa83fa05a33e95570b127) 421 computes the registration transformation for two point sets using ICP algorithm implemented 422 in the third party library [libpointmatcher](https://github.com/ethz-asl/libpointmatcher). 423 - [`CGAL::pointmatcher::register_point_sets()`](https://doc.cgal.org/5.1/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#gaa222278e20a3ce41930d37326cd54ef9), 424 which computes the registration transformation for two point sets using ICP algorithm implemented 425 in the third party library [libpointmatcher](https://github.com/ethz-asl/libpointmatcher), and registers 426 the points sets by transforming the data point set using the computed transformation. 427 428### [2D Triangulations](https://doc.cgal.org/5.1/Manual/packages.html#PkgTriangulation2) 429 430- To fix an inconsistency between code and documentation and to clarify which types of intersections 431 are truly allowed in constrained Delaunay triangulations, the tag [`CGAL::No_intersection_tag`](https://doc.cgal.org/5.1/Triangulation_2/structCGAL_1_1No__intersection__tag.html) 432 has been deprecated in favor of two new tags: [`CGAL::No_constraint_intersection_tag`](https://doc.cgal.org/5.1/Triangulation_2/structCGAL_1_1No__constraint__intersection__tag.html) 433 and [`CGAL::No_constraint_intersection_requiring_constructions_tag`](https://doc.cgal.org/5.1/Triangulation_2/structCGAL_1_1No__constraint__intersection__requiring__constructions__tag.html). 434 The latter is equivalent to the now-deprecated `CGAL::No_intersection_tag`, and allows constraints 435 to intersect as long as no new point has to be created to represent that intersection (for example, 436 the intersection of two constraint segments in a 'T'-like junction is an existing point 437 and as such does not require any new construction). The former tag, `CGAL::No_constraint_intersection_tag`, 438 does not allow any intersection, except for the configuration of two constraints having a single 439 common endpoints, for convience. 440- Added the function [`CGAL::split_subconstraint_graph_into_constraints()`](https://doc.cgal.org/5.1/Triangulation_2/classCGAL_1_1Constrained__triangulation__plus__2.html#adea77f5db5cd4dfae302e4502f1caa85) 441 to [`Constrained_triangulation_plus_2`](https://doc.cgal.org/5.1/Triangulation_2/classCGAL_1_1Constrained__triangulation__plus__2.html) to initialize the constraints 442 from a soup of disconnected segments that should first be split into polylines. 443 444### [3D Triangulations](https://doc.cgal.org/5.1/Manual/packages.html#PkgTriangulation3) 445 446- The member function [`CGAL::Triangulation_3::file_input()`](https://doc.cgal.org/5.1/Triangulation_3/group__PkgIOTriangulation3.html#gadd94d0613e2dd9cdd2e88d2c74d5b1c8) 447 have been added. It allows to load a [`CGAL::Triangulation_3`](https://doc.cgal.org/5.1/Triangulation_3/classCGAL_1_1Triangulation__3.html) 448 from an input stream, using functors to create vertices and cells. 449 450### [3D Triangulation Data Structure](https://doc.cgal.org/5.1/Manual/packages.html#PkgTDS3) 451 452- The member function [`CGAL::TDS_3::file_input()`](https://doc.cgal.org/5.1/TDS_3/group__PkgIOTDS3.html#ga381446a02a9240cc83e79c48b37cd119) 453 have been added. It allows to load a [`CGAL::Triangulation_data_structure_3`](https://doc.cgal.org/5.1/TDS_3/classCGAL_1_1Triangulation__data__structure__3.html) 454 from an input stream, using functors to create vertices and cells. 455 456### [Surface Mesh Simplification](https://doc.cgal.org/5.1/Manual/packages.html#PkgSurfaceMeshSimplification) 457 458- Added a [new simplification method](https://doc.cgal.org/5.1/Surface_mesh_simplification/classCGAL_1_1Surface__mesh__simplification_1_1GarlandHeckbert__policies.html) 459 based on the quadric error defined by Garland and Heckbert. 460- The concept `EdgeProfile` has been removed. This concept was not actually in use as the CGAL-provided model [`CGAL::Edge_profile`](https://doc.cgal.org/5.1/Surface_mesh_simplification/classCGAL_1_1Surface__mesh__simplification_1_1Edge__profile.html) 461 was imposed to the user. Other concepts have been clarified to reflect the fact that the API uses this particular class. 462 463### [STL Extensions for CGAL](https://doc.cgal.org/5.1/Manual/packages.html#PkgSTLExtension) 464 465- Added a new concurrency tag: [`CGAL::Parallel_if_available_tag`](https://doc.cgal.org/5.1/STL_Extension/structCGAL_1_1Parallel__if__available__tag.html). 466 This tag is a convenience typedef to [`CGAL::Parallel_tag`](https://doc.cgal.org/5.1/STL_Extension/structCGAL_1_1Parallel__tag.html) 467 if the third party library TBB has been found and linked with, and to 468 [`CGAL::Sequential_tag`](https://doc.cgal.org/5.1/STL_Extension/structCGAL_1_1Sequential__tag.html) otherwise. 469 470 471[Release 5.0](https://github.com/CGAL/cgal/releases/tag/releases%2FCGAL-5.0) 472----------- 473 474Release date: November 2019 475 476### General changes 477 478- CGAL 5.0 is the first release of CGAL that requires a C++ compiler 479 with the support of C++14 or later. The new list of supported 480 compilers is: 481 - Visual C++ 14.0 (from Visual Studio 2015 Update 3) or later, 482 - Gnu g++ 6.3 or later (on Linux or MacOS), 483 - LLVM Clang version 8.0 or later (on Linux or MacOS), and 484 - Apple Clang compiler versions 7.0.2 and 10.0.1 (on MacOS). 485- Since CGAL 4.9, CGAL can be used as a header-only library, with 486 dependencies. Since CGAL 5.0, that is now the default, unless 487 specified differently in the (optional) CMake configuration. 488- The section "Getting Started with CGAL" of the documentation has 489 been updated and reorganized. 490- The minimal version of Boost is now 1.57.0. 491 492 493### [Polygonal Surface Reconstruction](https://doc.cgal.org/5.0/Manual/packages.html#PkgPolygonalSurfaceReconstruction) (new package) 494 495 - This package provides a method for piecewise planar object reconstruction from point clouds. 496 The method takes as input an unordered point set sampled from a piecewise planar object 497 and outputs a compact and watertight surface mesh interpolating the input point set. 498 The method assumes that all necessary major planes are provided (or can be extracted from 499 the input point set using the shape detection method described in Point Set Shape Detection, 500 or any other alternative methods).The method can handle arbitrary piecewise planar objects 501 and is capable of recovering sharp features and is robust to noise and outliers. See also 502 the associated [blog entry](https://www.cgal.org/2019/08/05/Polygonal_surface_reconstruction/). 503 504### [Shape Detection](https://doc.cgal.org/5.0/Manual/packages.html#PkgShapeDetection) (major changes) 505 - **Breaking change:** The concept `ShapeDetectionTraits` has been renamed to [`EfficientRANSACTraits`](https://doc.cgal.org/5.0/Shape_detection/classEfficientRANSACTraits.html). 506 - **Breaking change:** The `Shape_detection_3` namespace has been renamed to [`Shape_detection`](https://doc.cgal.org/5.0/Shape_detection/annotated.html). 507 - Added a new, generic implementation of region growing. This enables for example applying region growing to inputs such as 2D and 3D point sets, 508 or models of the [`FaceGraph`](https://doc.cgal.org/5.0/BGL/classFaceGraph.html) concept. Learn more about this new algorithm with this [blog entry](https://www.cgal.org/2019/07/30/Shape_detection/). 509 510### [dD Geometry Kernel](https://doc.cgal.org/5.0/Manual/packages.html#PkgKernelD) 511 - A new exact kernel, [`Epeck_d`](https://doc.cgal.org/5.0/Kernel_d/structCGAL_1_1Epeck__d.html), is now available. 512 513### [2D and 3D Linear Geometry Kernel](https://doc.cgal.org/5.0/Manual/packages.html#PkgKernel23) 514 - Added a new concept, [`ComputeApproximateAngle_3`](https://doc.cgal.org/5.0/Kernel_23/classKernel_1_1ComputeApproximateAngle__3.html), 515 to the 3D Kernel concepts to compute the approximate angle between two 3D vectors. Corresponding functors 516 in the model ([`Compute_approximate_angle_3`](https://doc.cgal.org/5.0/Kernel_23/classKernel.html#a183c9ac358a4ccddc04e680f8ed16c0b)) 517 and free function ([`approximate_angle`](https://doc.cgal.org/5.0/Kernel_23/group__approximate__angle__grp.html)) 518 have also been added. 519 - The following objects are now hashable and thus trivially usable 520 with [`std::unordered_set`](https://en.cppreference.com/w/cpp/container/unordered_set) 521 and [`std::unordered_map`](https://en.cppreference.com/w/cpp/header/unordered_map): 522 `CGAL::Aff_transformation_2`, `CGAL::Aff_transformation_3`, 523 `CGAL::Bbox_2`, `CGAL::Bbox_3`, `CGAL::Circle_2`, 524 `CGAL::Iso_cuboid_3`, `CGAL::Iso_rectangle_2`, `CGAL::Point_2`, 525 `CGAL::Point_3`, `CGAL::Segment_2`, `CGAL::Segment_3`, 526 `CGAL::Sphere_3`, `CGAL::Vector_2`, `CGAL::Vector_3`, 527 `CGAL::Weighted_point_2` and `CGAL::Weighted_point_3`. 528 529### [Polygon Mesh Processing](https://doc.cgal.org/latest/Manual/packages.html#PkgPolygonMeshProcessing) 530 - Introduced a [wide range of new functions](https://doc.cgal.org/5.0/Polygon_mesh_processing/index.html#title36) 531 related to location of queries on a triangle mesh, 532 such as [`CGAL::Polygon_mesh_processing::locate(Point, Mesh)`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__PMP__locate__grp.html#gada09bd8740ba69ead9deca597d53cf15). 533 The location of a point on a triangle mesh is expressed as the pair of a face and the barycentric 534 coordinates of the point in this face, enabling robust manipulation of locations 535 (for example, intersections of two 3D segments living within the same face). 536 - Added the mesh smoothing function [`smooth_mesh()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__PMP__meshing__grp.html#gaa0551d546f6ab2cd9402bea12d8332a3), 537 which can be used to improve the quality of triangle elements based on various geometric characteristics. 538 - Added the shape smoothing function [`smooth_shape()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__PMP__meshing__grp.html#gaaa083ec78bcecf351e04d1bbf460b4a2), 539 which can be used to smooth the surface of a triangle mesh, using the mean curvature flow to perform noise removal. 540 (See also the new entry in the [User Manual](https://doc.cgal.org/5.0/Polygon_mesh_processing/index.html#title8)) 541 - Added the function [`CGAL::Polygon_mesh_processing::centroid()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__measure__grp.html#ga6da5119ce2c50729fda11a90ae7fb9ba), 542 which computes the centroid of a closed triangle mesh. 543 - Added the functions [`CGAL::Polygon_mesh_processing::stitch_boundary_cycle()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__PMP__repairing__grp.html#ga9c12c4878c08a117b3733bb45f1a34cf) 544 and [`CGAL::Polygon_mesh_processing::stitch_boundary_cycles()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__PMP__repairing__grp.html#ga24d5ae37f62064b3fc576ba48a4ccc63), 545 which can be used to try and merge together geometrically compatible but combinatorially different halfedges 546 that belong to the same boundary cycle. 547 - It is now possible to pass a face-size property map to [`CGAL::Polygon_mesh_processing::keep_large_connected_components()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__keep__connected__components__grp.html#ga48e7b3e6922ee78cf8ce801e3e325d9a) 548 and [`CGAL::Polygon_mesh_processing::keep_largest_connected_components()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__keep__connected__components__grp.html#ga68c6c29dfc6a26a6a2f8befe6944f19d), enabling users to define 549 how the size of a face is computed (the size of the connected component is the sum of the sizes of its faces). 550 If no property map is passed, the behavior is unchanged to previous versions: the size 551 of a connected component is the number of faces it contains. 552 - Added the function [`CGAL::Polygon_mesh_processing::non_manifold_vertices()`](https://doc.cgal.org/5.0/Polygon_mesh_processing/group__PMP__repairing__grp.html#ga36098d2415efd0604b7b996163bc22db), 553 which can be used to collect all the non-manifold vertices (i.e. pinched vertices, 554 or vertices appearing in multiple umbrellas) of a mesh. 555 556### [3D Point Set](https://doc.cgal.org/5.0/Manual/packages.html#PkgPointSet3) 557 - The [PLY IO functions](https://doc.cgal.org/5.0/Point_set_3/group__PkgPointSet3IO.html) now take an additional optional parameter to 558 read/write comments from/in the PLY header. 559 560### [Point Set Processing](https://doc.cgal.org/latest/Manual/packages.html#PkgPointSetProcessing3) 561 - **Breaking change**: the API using iterators and overloads for optional parameters (deprecated since 562 CGAL 4.12) has been removed. The current (and now only) API uses ranges and Named Parameters. 563 - Added the possibility to use the named parameter 564 [`neighbor_radius`](https://doc.cgal.org/5.0/Point_set_processing_3/group__psp__namedparameters.html#PSP_neighbor_radius) 565 to use spherical neighbor queries instead of K-nearest neighbors queries for the following functions: 566 [`CGAL::bilateral_smooth_point_set()`](https://doc.cgal.org/5.0/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga4f82723e2f0bb33f3677e29e0208a256), 567 [`CGAL::jet_estimate_normals()`](https://doc.cgal.org/5.0/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga0cd0f87de690d4edf82740e856efa491), 568 [`CGAL::jet_smooth_point_set()`](https://doc.cgal.org/5.0/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga549402c0a8a8b6b71875181e93961521), 569 [`CGAL::mst_orient_normals()`](https://doc.cgal.org/5.0/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga50c98d5c5ae5535bce6f32eddbd03f33), 570 [`CGAL::pca_estimate_normals()`](https://doc.cgal.org/5.0/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#ga8c642da96a025ab32445aeb6cc219b0b) and 571 [`CGAL::remove_outliers()`](https://doc.cgal.org/5.0/Point_set_processing_3/group__PkgPointSetProcessing3Algorithms.html#gafd0b5a21ec5042e4bca09cb43f1847f9). 572 573### [2D Triangulations](https://doc.cgal.org/5.0/Manual/packages.html#PkgTriangulation2) 574 - **Breaking change**: Removed the deprecated functions `CGAL::Constrained_triangulation_plus_2:: 575 vertices_in_constraint_{begin/end}(Vertex_handle va, Vertex_handle vb) const;`, 576 and `CGAL::Constrained_triangulation_plus_2::remove_constraint(Vertex_handle va, Vertex_handle vb)`, 577 that is a pair of vertex handles is no longer a key for a polyline constraint. 578 Users must use a version prior to 5.0 if they need this functionality. 579 - **Breaking change**: Removed the deprecated classes `CGAL::Regular_triangulation_euclidean_traits_2`, 580 `CGAL::Regular_triangulation_filtered_traits_2`. Users must use a version prior to 5.0 if they need these classes. 581 - **Breaking change**: The [graph traits](https://doc.cgal.org/5.0/BGL/group__PkgBGLTraits.html) enabling CGAL's 2D triangulations to be used as a parameter 582 for any graph-based algorithm of CGAL (or boost) have been improved to fully model the [`FaceGraph`](https://doc.cgal.org/5.0/BGL/classFaceGraph.html) concept. 583 In addition, only the finite simplicies (those not incident to the infinite vertex) of the 2D triangulations 584 are now visibile through this scope. The complete triangulation can still be accessed as a graph, 585 by using the graph traits of the underlying triangulation data structure (usually, 586 [`CGAL::Triangulation_data_structure_2`](https://doc.cgal.org/5.0/TDS_2/classCGAL_1_1Triangulation__data__structure__2.html)). 587 - **Breaking change**: The `insert()` function 588 of 589 [`CGAL::Triangulation_2`](https://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Triangulation__2.html) 590 which takes a range of points as argument is now guaranteed to 591 insert the points following the order of `InputIterator`. Note 592 that this change only affects the base class `Triangulation_2` 593 and not any derived class, such as `Delaunay_triangulation_2`. 594- Added a new [constructor](https://doc.cgal.org/5.0/Triangulation_2/classCGAL_1_1Triangulation__2.html#a6cfa7d3aaa375a25d217858b49e2eb07=) 595 and [`insert()`](https://doc.cgal.org/5.0/Triangulation_2/classCGAL_1_1Triangulation__2.html#ac5e9bc8adef80dc01a0b31c2d0234545) 596 function to [`CGAL::Triangulation_2`](https://doc.cgal.org/5.0/Triangulation_2/classCGAL_1_1Triangulation__2.html) 597 that takes a range of points with info. 598 - Introduced a new face base class, [`Triangulation_face_base_with_id_2`](https://doc.cgal.org/5.0/BGL/classCGAL_1_1Triangulation__face__base__with__id__2.html) 599 which enables storing user-defined integer IDs in the face of any 2D triangulation, a precondition to use some 600 BGL algorithms. 601 - Added range types and functions that return ranges, for example for all vertices, enabling the use of `C++11` `for`-loops. 602 See [this new example](https://doc.cgal.org/5.0/Triangulation_2/Triangulation_2_2for_loop_2_8cpp-example.html) for a usage demonstration. 603 604### [3D Triangulations](https://doc.cgal.org/5.0/Manual/packages.html#PkgTriangulation3) 605 - **Breaking change**: The [constructor](https://doc.cgal.org/5.0/Triangulation_3/classCGAL_1_1Triangulation__3.html#a63f67cf6aaadcee14318cf56a36d247a) 606 and the [`insert()`](https://doc.cgal.org/5.0/Triangulation_3/classCGAL_1_1Triangulation__3.html#ad3353128386bbb51f79d0263e7f67337) 607 function of [`CGAL::Triangulation_3`](https://doc.cgal.org/5.0/Triangulation_3/classCGAL_1_1Triangulation__3.html) 608 which take a range of points as argument are now guaranteed to 609 insert the points following the order of `InputIterator`. Note 610 that this change only affects the base class `Triangulation_3` 611 and not any derived class, such as `Delaunay_triangulation_3`. 612 - Added constructor and [`insert()`](https://doc.cgal.org/5.0/Triangulation_3/classCGAL_1_1Triangulation__3.html#a8aa85f88733d30aa3ec5385538e13ace) 613 function to `CGAL::Triangulation_3` that takes a range of points with info. 614 - Added range types and functions that return ranges, for example for all vertices, which enables to use C++11 for-loops. 615 See [this new example](https://doc.cgal.org/5.0/Triangulation_3/Triangulation_3_2for_loop_8cpp-example.html) for a usage demonstration. 616 617### [Surface Mesh](https://doc.cgal.org/5.0/Manual/packages.html#PkgSurfaceMesh) 618 - Introduced new functions to read and write using the PLY format, 619 [`CGAL::read_ply()`](https://doc.cgal.org/5.0/Surface_mesh/group__PkgSurface__mesh.html#ga42f6ad486ddab74e13d3dc53f511c343) 620 and [`CGAL::write_ply()`](https://doc.cgal.org/5.0/Surface_mesh/group__PkgSurface__mesh.html#ga77bbb79d449c981895eedb6c3c23bd14), 621 enabling users to save and load additional property maps of the surface mesh. 622 623### [CGAL and Solvers](https://doc.cgal.org/5.0/Manual/packages.html#PkgSolverInterface) 624 - Added [concepts](https://doc.cgal.org/5.0/Solver_interface/group__PkgSolverInterfaceConcepts.html) 625 and [models](https://doc.cgal.org/5.0/Solver_interface/group__PkgSolverInterfaceRef.html) 626 for solving Mixed Integer Programming (MIP) problems with or without constraints. 627 628### [3D Boolean Operations on Nef Polyhedra](https://doc.cgal.org/5.0/Manual/packages.html#PkgNef3) 629 - Added a function to convert a Nef_polyhedron_3 to a polygon soup: [`CGAL::convert_nef_polyhedron_to_polygon_soup()`](https://doc.cgal.org/5.0/Nef_3/group__PkgNef3IOFunctions.html#ga28a9eb4da0cd6153f0c16f7f9eaf6665) 630 631### [IO Streams](https://doc.cgal.org/5.0/Manual/packages.html#PkgStreamSupport) 632- **Breaking change:** The API of [`CGAL::Color`](https://doc.cgal.org/5.0/Stream_support/classCGAL_1_1Color.html) has been cleaned up. 633- Added new functions to support some parts of the WKT file format: 634 * [`CGAL::read_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gad2872abfe6fcf17d705d38567fdd6248) 635 * [`CGAL::read_point_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gadbd2705b183e467507abd2f167446eba) 636 * [`CGAL::read_multi_point_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#ga4fb72e49a1fd385bbed35ea20297aa8d) 637 * [`CGAL::read_linestring_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gaaa236308b9da5dbf217ef281fdb55de4) 638 * [`CGAL::read_multi_linestring_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gad6046c7f9d36512b8a014be82c1e2220) 639 * [`CGAL::read_polygon_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gaa36ccd3ac4b3fe3e3fd8a76715c56b9a) 640 * [`CGAL::read_multi_polygon_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#ga4ceaa71b9cb3b3f7984bed19afff6fc6) 641 * [`CGAL::write_point_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gab1a2d277b43c218bf128a2056eb53ced) 642 * [`CGAL::write_polygon_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gab5365a4726893aa4f51739ede63f5a09) 643 * [`CGAL::write_linestring_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#gaa37ed77d1a01567b93c872a48198efa6) 644 * [`CGAL::write_multi_point_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#ga98de4b4e5cccb370febe5daf66bb582d) 645 * [`CGAL::write_multi_polygon_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#ga4ded40ab50f57e0b410640e28964935e) 646 * [`CGAL::write_multi_linestring_WKT()`](https://doc.cgal.org/5.0/Stream_support/group__PkgStreamSupportRef.html#ga219987f7a9c0b871c1733aa0c38f26b3) 647 648 649Release 4.14 650------------ 651 652Release date: March 2019 653 654### 2D Periodic Hyperbolic Triangulations (new package) 655 656 - This package allows the computation of Delaunay triangulations of 657 the Bolza surface. The Bolza surface is the most symmetric 658 hyperbolic surface of genus 2. Its fundamental domain is the 659 regular hyperbolic octagon with angles π/4 centered at the origin 660 of the Poincaré disk. Triangulations of the Bolza surface can be 661 seen as triangulations of the hyperbolic plane that are periodic 662 in the four directions defined by the sides of this regular 663 octagon. 664 665### 2D Hyperbolic Triangulations (new package) 666 667 - This package allows the computation of Delaunay Triangulations of 668 sets of points in the Poincaré disk, which is one of the 669 conformal models for the hyperbolic plane. 670 671### The Heat Method (new package) 672 673- This package provides an algorithm that solves the single- or 674 multiple-source shortest path problem by returning an 675 approximation of the geodesic distance for all vertices of a 676 triangle mesh to the closest vertex in a given set of source 677 vertices. 678 679### Triangulated Surface Mesh Approximation (new package) 680 681- This package implements the Variational Shape Approximation method 682 to approximate an input surface triangle mesh by a simpler surface 683 triangle mesh. 684 685### Polygon Mesh Processing package 686 687- Added the following new functions to detect and repair issues in 688 polygon soups: 689 - `CGAL::Polygon_mesh_processing::remove_isolated_points_in_polygon_soup()`, 690 which detects and removes points that are not used in any 691 polygon of the soup. 692 - `CGAL::Polygon_mesh_processing::merge_duplicate_points_in_polygon_soup()`, 693 which detects and merges points that share the same geometric 694 position. 695 - `CGAL::Polygon_mesh_processing::merge_duplicate_polygons_in_polygon_soup()`, 696 which detects and merges polygons that are identical. 697 - `CGAL::Polygon_mesh_processing::repair_polygon_soup()`, which 698 applies a number of repairing steps (a subset of which are the 699 functions above) to clean and repair a polygon soup. 700 701- Added the following new functions to detect and repair 702 degeneracies in polygon meshes: 703 - `CGAL::Polygon_mesh_processing::degenerate_edges()` 704 - `CGAL::Polygon_mesh_processing::degenerate_faces()` 705 - `CGAL::Polygon_mesh_processing::is_non_manifold_vertex()` 706 - `CGAL::Polygon_mesh_processing::is_degenerate_triangle_face()` 707 - `CGAL::Polygon_mesh_processing::is_degenerate_edge()` 708 - `CGAL::Polygon_mesh_processing::is_needle_triangle_face()` 709 - `CGAL::Polygon_mesh_processing::is_cap_triangle_face()` 710 - `CGAL::Polygon_mesh_processing::duplicate_non_manifold_vertices()` 711 - `CGAL::Polygon_mesh_processing::extract_boundary_cycles()` 712 - `CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle()` 713 - `CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycles()` 714 715- Added the class `CGAL::Rigid_triangle_mesh_collision_detection` to 716 detect intersections between meshes and volumes undergoing affine 717 transformations. 718 719### Regularized Boolean Set Operations in 2D package 720 721- Fixed the validation of orientation of relative simple polygons. 722 723### Point Set Processing 724 725- `CGAL::mst_orient_normals()` can now be called with a set of 726 user-selected seed points that are known to be already oriented. A 727 new optional named parameter `point_is_constrained_map` is added 728 for this purpose. The original behavior (using one unique and 729 automatically selected seed) is kept if this parameter is not 730 used. 731 732### Classification 733 734- Added a new experimental classifier 735 `TensorFlow::Neural_network_classifier`. 736 737- For uniformity, `ETHZ_random_forest_classifier` is renamed 738 `ETHZ::Random_forest_classifier` and 739 `OpenCV_random_forest_classifier` is renamed 740 `OpenCV::Random_forest_classifier`. 741 742- The training algorithm of `ETHZ::Random_forest_classifier` was 743 parallelized. 744 745- Added a constructor to copy a `ETHZ::Random_forest_classifier` 746 using a different data set as input. 747 748- Added 3 new geometric features, `Height_above`, `Height_below` and 749 `Vertical_range`. 750 751### 3D Fast Intersection and Distance Computation 752 753- The primitives `AABB_face_graph_triangle_primitive` and 754 `AABB_halfedge_graph_segment_primitive` now use as `Id` a pair of 755 descriptor and graph pointer in the case they are configured to 756 deal with a possible different graph per primitive (configuration 757 set using a template tag). 758 759### 2D Arrangements 760 761- Fixed a bug in the surface-sweep framework (`Surface_sweep_2`) 762 that ensures that an event is never left without (left or right) 763 curves. 764 765- Fixed a constructor of `Arr_counting_traits.h`. (In particular, 766 added missing const of a parameter). 767 768- Fixed zone computation of a curve in cases where the lexicographic 769 smallest end of the curve lies on the parameter space. 770 771- Implemented missing function object `Compare_x_near_boundary` of 772 `Arr_polyline_traits_2`, `Arr_polycurve_traits_2`, and 773 `Arr_polycurve_basic_traits_2`. 774 775### 2D and 3D Mesh Generation 776 777- Added two functions for writing in XML VTK formats: 778 - `CGAL::write_vtu()`, that writes a 2D mesh in a `.vtu` file, 779 - `CGAL::output_to_vtu()`, that writes a 3D mesh in a `.vtu` file. 780 781### 2D Minkowski Sums 782 783- Fixed a bug in the function that computed the Minkowski sum using 784 the reduced-convolution method. In particular, correctly handled 785 the case where one of the summands does not have an outer 786 boundary. 787 788### 3D Point Set 789 790- Added a method `copy_properties()` that allows to copy the 791 properties from a point set to another one (without copying the 792 content); 793 794- Added a method `insert(const Point_set&, const Index&)` to copy a 795 point along with all its associated properties from another point 796 set; 797 798- `remove()` methods now only invalidate the `end()` iterator 799 instead of invalidating all iterators; 800 801- Added a method `is_removed()` that takes an index as argument; 802 803- Added a method `cancel_removals()` to restore removed points (if 804 no point was inserted since then an garbage was not collected); 805 806- **Breaking change:** unified API of method `add_normal_map()` with 807 `add_property_map()`: it now returns a pair of property map + bool 808 (that tells if the property was added) instead of just the 809 property map; 810 811- Added a method `properties_and_types()` in addition to 812 `properties()`: this new one returns pairs of `std::string` + 813 `std::type_info` in order to also know the type of each property. 814 815### CGAL and the Boost Graph Library (BGL) 816 817- Added function `write_wrl()` for writing into VRML 2.0 format. 818- Added functions `CGAL::write_vtp()` for writing a triangulated 819 face graph in a `.vtp` file (XML VTK format). 820 821 822Release 4.13 823------------ 824 825Release date: October 2018 826 827### 3D Periodic Mesh Generation (new package) 828 829- This package generates 3-dimensional periodic meshes. It computes 830 isotropic simplicial meshes for domains described through implicit 831 functional boundaries over the flat torus (which can also seen in 832 the Euclidean space as a periodic cube). The output is a periodic 833 3D mesh of the domain volume and conformal surface meshes for all 834 the boundary and subdividing surfaces. The package is closely 835 related to the 3D Mesh Generation package, with similar concepts, 836 classes, and API. 837 838### Installation 839 840- The library `CGAL_Qt5` now contains a fork of the version 2.7.0 of 841 `libQGLViewer`. The corresponding code is in the package 842 `GraphicsView`. The dependency for the external library 843 `libQGLViewer` is therefore dropped for all demos. 844 845### General 846 847 - A new function `CGAL::draw()` is added in the packages Polyhedral 848 Surface, Surface Mesh, Linear Cell Complex, 2D Triangulations, and 849 3D Triangulations, enabling to draw the corresponding data 850 structures. 851 852### 2D and 3D Linear Geometry Kernel 853 854- An `operator()` that takes a `Ray_3` has been added to the concept 855 `ConstructProjectedPoint_3`. 856 857### Convex hull 3 858 859- Added the function `extreme_points_3()` computing the points on 860 the convex hull without underlying connectivity. 861 862- Added a traits adapter called `Extreme_points_traits_adapter_3` 863 that enables the use of the function `extreme_points_3()` on a 864 range of keys, each key being associated to 3D point using a 865 property map. This can be used to get the vertices of a mesh that 866 are on it convex hull, or the indices of points in a range that 867 are on it convex hull. 868 869- Fix a bug in the computation of the 3D convex hull that was 870 leaving extra points within subset of coplanar points that do not 871 belong to the minimal convex hull. 872 873 874### 2D and 3D Triangulations 875 876- Added a new type of intersection to handle the insertion of 877 intersecting constraints in a `Constrained_triangulation_2`. 878 879- **Breaking change:** The long-deprecated class 880 `Triangulation_cell_base_with_circumcenter_3` and its associated 881 concept have been removed. Users should use the classes 882 `Delaunay_cell_base_with_circumcenter_3` or 883 `Regular_cell_base_with_circumcenter_3`, depending on which type 884 of triangulation they are using. 885 886- **Breaking change:** The deprecated functions `mirror_index` and 887 `mirror_vertex` of the class `Triangulation_face_base_2` have been 888 removed. Users should use the equivalent functions from the class 889 `Triangulation_2`. 890 891### 3D Mesh Generation 892 893- **Breaking change:** The template parameters of the class template 894 `Labeled_mesh_domain_3` have been simplified. The three 895 constructors of that class template have been replaced by a new 896 unique constructor using Boost named parameters. Three new static 897 template member functions that act as named constructors have been 898 added: 899 - `create_gray_image_mesh_domain()`, to create a domain from a 3D 900 gray image, 901 - `create_labeled_image_mesh_domain()`, to create a domain from a 3D 902 labeled image, and 903 - `create_implicit_mesh_domain()`, to create a domain from an 904 implicit function. 905 906- The class templates `Implicit_mesh_domain_3`, 907 `Gray_image_mesh_domain_3`, and `Labeled_image_mesh_domain_3` are 908 now deprecated. 909 910- **Breaking change:** The headers 911 `<CGAL/Mesh_3/Implicit_to_labeled_function_wrapper.h>` and 912 `<CGAL/Mesh_3/Labeled_mesh_domain_3.h>`, that were deprecated 913 since CGAL 4.5, have been removed. 914 915- **Breaking change:** the concepts `MeshCellCriteria_3` and 916 `MeshFacetCriteria_3` now require the triangulation to be passed 917 in their `operator()`. Models of these concepts that are provided 918 by CGAL have been modified accordingly. 919 920- **Breaking change:** It is no longer possible to use the 921 deprecated, pre-CGAL 3.8 specifications in `MeshCellCriteria_3` 922 and `MeshFacetCriteria_3` (that is, using `Facet_badness` and 923 `Cell_badness` instead of `Is_facet_bad` and `Is_cell_bad`). 924 925- The concept `MeshFacetCriteria_3` no longer requires the function 926 `operator()(Cell_handle c, int i)`. 927 928- The concept `MeshEdgeCriteria_3` no longer requires the function 929 `operator()(const Edge& e)`. 930 931- The concept `MeshComplexWithFeatures_3InTriangulation_3` no longer 932 requires the functions `number_of_edges(Curve_index index)` and 933 `number_of_corners(Corner_index index)`. 934 935- Introduced the concept `MeshTriangulationTraits_3`, which covers 936 the needs of the traits class used in `Mesh_3` (and 937 `Periodic_3_mesh_3`). The traits class used as template parameter 938 of `Mesh_triangulation_3` and `Periodic_3_mesh_triangulation_3` 939 must be a model of this concept. 940 941- Added the function 942 `Mesh_domain_with_polyline_features_3::add_corner()`, which allows 943 users to add a single corner (that is not incident to any 944 polyline) to the mesh complex. 945 946- **Breaking change**: `CGAL::lloyd_optimize_mesh_3` now depends on 947 the _Eigen_ library. 948 949### Polygon Mesh Processing 950 951- Added a named parameter in stitching functions that allows to 952 choose whether the operation should be performed per connected 953 component or globally. 954 955- Added a function, `CGAL::Polygon_mesh_processing::transform()`, to 956 apply a transformation to a mesh. 957 958- Added a named parameter `visitor` in corefinement-related 959 functions that makes it possible to pass a visitor to the function 960 in order to track the creation of new faces. 961 962- Added a named parameter `throw_on_self_intersection` in all 963 corefinement-related functions, which enables to check for 964 self-intersecting faces involved in the intersection before trying 965 to corefine the input meshes. This new parameter replaces the 966 `bool` parameter in `corefine()`. 967 968- Added the function `corefine_and_compute_boolean_operations()`, 969 which can be used to compute the result of several Boolean 970 operations between two volumes at the same time. 971 972- Added the function `clip()`, which can be used to clip a 973 triangulated surface mesh by a plane or a clipping volume. 974 975- Constrained vertices are now guaranteed to be kept in the mesh 976 after calling `isotropic_remeshing()` (and not only the points 977 associated to constrained vertices, as it was before). 978 979- Added a function, `CGAL::Polygon_mesh_processing::extrude_mesh()`, 980 to perform an extrusion of an open polygon mesh. 981 982### Estimation of Local Differential Properties of Point-Sampled Surfaces Reference 983 984- **Breaking change**: `CGAL::Monge_via_jet_fitting` now depends on 985 the _Eigen_ library. 986 987### Point Set Processing 988 989- Added a callback mechanism to the following functions: 990 `CGAL::bilateral_smooth_point_set()`, 991 `CGAL::compute_average_spacing()`, 992 `CGAL::grid_simplify_point_set()`, 993 `CGAL::hierarchy_simplify_point_set()`, 994 `CGAL::jet_estimate_normals()`, `CGAL::jet_smooth_point_set()`, 995 `CGAL::pca_estimate_normals()`, `CGAL::remove_outliers()` and 996 `CGAL::wlop_simplify_and_regularize_point_set()`. 997 998 999### Classification 1000 1001- Added data structures to handle classification of Surface Meshes 1002 and of Clusters. 1003 1004- Added public API to compute features in parallel. 1005 1006- **Breaking change**: features based on products/divisions of 1007 eigenvalues are replaced by simple eigenvalue features. Features 1008 based on statistics on the HSV color channels are replaced by 1009 simple HSV color channel features. 1010 1011- **Breaking change**: the API of 1012 `CGAL::Classification::Point_set_feature_generator` has been 1013 simplified. 1014 1015 1016### Bounding Volumes 1017 1018- **Breaking change**: `CGAL::Approximate_min_ellipsoid_d` now 1019 depends on the _Eigen_ library. 1020 1021### Interpolation 1022 1023- The output of the natural and regular neighbor functions 1024 (resp. the gradient fitting functions) is no longer restricted to 1025 a Point/Coordinate pair (resp. Point/Vector pair). Instead, users 1026 can provide their own functor to format the output as they desire. 1027 1028- The interpolation functions can now operate on any combination of 1029 Type/Coordinate, provided that the values and gradients functors 1030 can also be evaluated using 'Type'. 1031 1032 The combination of these two changes allow, for example, to 1033 operate with Vertex/Coordinate pairs, which enables a more 1034 efficient access to values and gradients by storing information 1035 directly in the vertex. 1036 1037- The concepts `InterpolationTraits` and `GradientFittingTraits` 1038 have been updated to reflect the real needs of the code (some 1039 types and operators were used in the code but did not appear in 1040 the concepts). 1041 1042### CGAL and the Boost Graph Library (BGL) 1043 1044- Added a helper function, `CGAL::is_valid_polygon_mesh`, that 1045 checks the validity of a polygon mesh using BGL functions. 1046 1047- Improved the function `CGAL::Euler::collapse_edge` such that the 1048 target vertex of the collapsed edge is now always kept after the 1049 collapse. 1050 1051- The function `copy_face_graph()` now uses named parameters, some 1052 allowing it to use property maps instead of output iterators. 1053 1054- Addition of the following named parameters : 1055 - vertex_to_vertex_output_iterator 1056 - halfedge_to_halfedge_output_iterator 1057 - face_to_face_output_iterator 1058 - vertex_to_vertex_map 1059 - halfedge_to_halfedge_map 1060 - face_to_face_map 1061 1062### CGAL and Solvers 1063 1064- **Breaking change**: `CGAL::Diagonalize_traits` is now deprecated 1065 and should not be used. The class `CGAL::Eigen_diagonalize_traits` 1066 (along with the _Eigen_ library) should be used instead. 1067 1068### CGAL and Boost Property Maps 1069 1070- Added a read-write property map to convert on-the-fly geometric 1071 objects from Cartesian kernels. 1072 1073### 2D Arrangements 1074 1075- Refracted and fixed the `graph_traits` for the dual of an arrangement of the 1076 following types: 1077 `Arrangement_on_surface_2`, 1078 `Arrangement_2`, 1079 `Arrangement_on_surface_with_history_2`, and 1080 `Arrangement_with_history_2`. 1081 1082- **Breaking change**: The old `<CGAL/graph_traits_Dual_Arrangement_2.h>` 1083 header file has been replaced by the four header files below; each defines 1084 the `graph_traits` for dual of the corresponding arrangement type. 1085 `<CGAL/graph_traits_dual_arrangement_on_surface_2.h>`, 1086 `<CGAL/graph_traits_dual_arrangement_2.h>`, 1087 `<CGAL/graph_traits_dual_arrangement_on_surface_with_history_2.h>`, and 1088 `<CGAL/graph_traits_dual_arrangement_with_history_2.h`. 1089 1090 1091Release 4.12 1092------------ 1093 1094Release date: April 2018 1095 1096 1097### Important Notice 1098 1099- The CMake scripts used by CGAL have been changed to use modern patterns 1100 introduced by CMake 2.8.12 and CMake 3.0: instead of setting CMake 1101 variables, the script now defines imported targets and uses link 1102 interfaces. 1103 1104 That is mostly backward-compatible with existing usages of CGAL CMake 1105 scripts. The only non-compatible effect is that the `CMAKE_BUILD_TYPE` 1106 and compilation flags are no longer copied from the `CGAL_DIR` to the 1107 project using it. Note also that the `CMAKE_BUILD_TYPE` is no longer 1108 set to `Release` by default. For a developer using the Visual Studio 1109 IDE or the Xcode IDE, the change should be transparent. Developers using 1110 makefiles or the Ninja build-system should set the `CMAKE_BUILD_TYPE` 1111 to `Release` manually, to avoid using CGAL libraries without any 1112 compile-time optimization. 1113 1114### Header-only Mode 1115 1116- Since CGAL-4.9, it has been possible to use CGAL by configuring it 1117 using CMake, but without compiling the CGAL libraries. With CGAL-4.12, 1118 it is now possible to use CGAL header-only, without even configuring 1119 it. CMake is then used only to configure programs using CGAL. 1120 1121### Compiler Support 1122 1123- The Microsoft Visual C++ 2017 version 15.3 has introduced support for 1124 C++17, with the compilation flag `/std:c++17`. CGAL 4.12 has an initial 1125 support for that flag: the code will compile, but a lot of deprecation 1126 warnings will remain. Note that Boost version 1.67 is the first version 1127 of Boost supporting `/std:c++17`. 1128 1129- The compilation flag `/permissive-` of Visual C++ is now supported. 1130 1131### 2D Movable Separability of Sets (new package) 1132 1133- A new package called "2D Movable Separability of Sets" has been 1134 introduced. It handles a class of problems that deal with moving 1135 sets of objects in the plane; the challenge is to avoid collisions 1136 between the objects while considering different kinds of motions and 1137 various definitions of separation. 1138 1139 At this point this package consists of the implementations of 1140 various predicates and constructions related to castings of 1141 polygonal objects. In particular, it can be used to determine 1142 whether a feasible mold for a polygonal object does exist. If a mold 1143 exists, the package can also be used to compute all possible 1144 orientations of the feasible molds and the corresponding motions 1145 needed to remove the casted object from the mold. 1146 1147### Classification (new package) 1148 1149- This package offers an algorithm that classifies a data set into a 1150 user-defined set of labels (such as ground, vegetation, buildings, 1151 etc.). A flexible API is provided so that users can classify any 1152 type of data, compute their own local features on the input data 1153 set, and define their own labels. 1154 1155### Kinetic Data Structures (removed package) 1156 1157- This package has been removed from CGAL-4.12. Users of the package 1158 will have to keep using the source code available in CGAL-4.11 or 1159 earlier. 1160 1161 1162### 3D Convex Hull 1163 1164- **Breaking change**: The header `<CGAL/convex_hull_3.h>` no longer 1165 includes `<CGAL/Polyhedron_3.h>`, as the convex hull function works 1166 with any model of the concept `MutableFaceGraph`. 1167 1168### 2D Arrangements 1169 1170- When removing an edge from an arrangement and the user has requested to 1171 remove the end-vertices in case they become redundant (either isolated or 1172 approach infinity), defer the removal of the such end-vertices to occur 1173 after the observer is notified that the edge has been removed. This is 1174 symmetric (opposite) to the order of notification when an edge is inserted. 1175 1176 The user can restore old (non-symmetric) behaviour by defining the macro: 1177 1178 `CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY` 1179 1180### 2D Periodic Triangulations 1181 1182- **Breaking change**: The class 1183 `Periodic_2_triangulation_hierarchy_vertex_base_2` (and its 1184 corresponding header) have been removed. Users should directly use 1185 the class `Triangulation_hierarchy_vertex_base_2`, which is 1186 identical. 1187- **Breaking change**: The functions `circumcenter()`, 1188 `side_of_oriented_circle()`, and `is_extensible_in_1_sheet_h[12]()` 1189 are related to Delaunay triangulations and have been moved from 1190 `Periodic_2_triangulation_2` to 1191 `Periodic_2_Delaunay_triangulation_2`. 1192 1193### 2D Alpha Shapes 1194 1195- It is now possible to use `CGAL::Periodic_2_triangulation_2` as 1196 underlying triangulation for `Alpha_shape_2`. 1197 1198### 3D Surface Mesh Generation 1199 1200- Add the function `facets_in_complex_2_to_triangle_mesh()` that 1201 exports `Surface_mesh_complex_2_in_triangulation_3` facets into 1202 a `MutableFaceGraph`. 1203 1204### 3D Mesh Generation 1205 1206- Add the function `facets_in_complex_3_to_triangle_mesh()` that 1207 exports `Mesh_complex_3_in_triangulation_3` facets into a 1208 `MutableFaceGraph`. 1209- **Breaking change:** The concept `MeshDomainWithFeatures_3` has been 1210 modified, to improve the performance and the reliability of the 1211 sampling of 1D curves of the domain. 1212- Add the ability to ensure that the output mesh surface describes a 1213 manifold, when the input surface is a manifold. New named parameters 1214 `manifold()`, `manifold_with_boundary()`, and `non_manifold()` are 1215 added. 1216 1217### Optimal Transportation Curve Reconstruction 1218 1219- New method `run_under_wasserstein_tolerance()` which allows the 1220 user to perform curve reconstruction by relying on a threshold on 1221 the Wasserstein distance. This is useful when the number of edges 1222 in the expected output reconstruction is not known. 1223 1224### Polygon Mesh Processing 1225 1226- Added two functions for orienting connected components : 1227 - `CGAL::Polygon_mesh_processing::orient()` 1228 - `CGAL::Polygon_mesh_processing::orient_to_bound_a_volume()` 1229 1230- Added a new function for intersection tests between triangle meshes 1231 and/or polylines or range of polylines, and another one to report 1232 all the pairs of meshes intersecting from a range of meshes: 1233 - `CGAL::Polygon_mesh_processing::do_intersect()` 1234 - `CGAL::Polygon_mesh_processing::intersecting_meshes()` 1235 1236- Added new functions for feature detection and feature-guided 1237 segmentation: 1238 - `CGAL::Polygon_mesh_processing::detect_sharp_edges()` 1239 - `CGAL::Polygon_mesh_processing::detect_vertex_incident_patches()` 1240 - `CGAL::Polygon_mesh_processing::sharp_edges_segmentation()` 1241 1242### Point Set Shape Detection 1243 1244- **Breaking change**: 1245 `CGAL::Shape_detection_3::Efficient_RANSAC_traits` is now called 1246 `CGAL::Shape_detection_3::Shape_detection_traits`. 1247- New algorithm: `CGAL::Region_growing`. This is a deterministic 1248 alternative to RANSAC for plane detection. 1249- **Breaking change**: the API of `CGAL::regularize_planes()` is 1250 generalized to accept other types of input than the RANSAC output. 1251- Add a callback mechanism for both `CGAL::Efficient_RANSAC` and 1252 `CGAL::Region_growing`. 1253 1254### Point Set Processing 1255 1256- **Breaking change**: the API of `CGAL::structure_point_set()` is 1257 generalized to accept other types of input than the RANSAC output. 1258- **Breaking change**: the API of all functions of Point Set 1259 Processing is modified to use ranges (instead of iterators) and 1260 Named Parameters (similarly to the API of Polygon Mesh 1261 Processing). The old API is kept as deprecated. 1262 1263### CGAL and the Boost Graph Library (BGL) 1264 1265- Add helper function `CGAL::expand_face_selection_for_removal` that 1266 expands a face selection to avoid creating a non manifold mesh when 1267 removing the selected faces. 1268 1269- Added support for dynamic property maps. 1270 1271- Added an interface to the [METIS library], which allows to partition 1272 any mesh that is a model of `FaceListGraph`. Wrappers to the 1273 METIS functions `METIS_PartMeshNodal` and `METIS_PartMeshDual` are 1274 offered. 1275 1276 [METIS library]: http://glaros.dtc.umn.edu/gkhome/metis/metis/overview 1277 1278 1279Release 4.11 1280------------ 1281 1282Release date: September 2017 1283 1284### 3D Periodic Regular Triangulations (new feature) 1285 1286- Added the class `Periodic_3_regular_triangulation_3`, which provides 1287 functionality for 3D periodic weighted Delaunay triangulations. The 1288 construction is fully dynamic: it provides both point insertion and 1289 vertex removal. 1290 1291### dD Regular Triangulations (new feature) 1292 1293- Added the class `Regular_triangulation`, which provides 1294 functionality for dD weighted Delaunay triangulations. Note that the 1295 removal of points is not yet supported. 1296 1297### 2D and 3D Linear Geometry Kernel (breaking change) 1298 1299- **Breaking change**: The dangerous implicit conversions between 1300 weighted points and points in the concept `Kernel` have been 1301 disabled. Constructors offering to build a weighted point from a 1302 point (and reversely) are still requested by the concept `Kernel` 1303 but must now be marked with the `explicit` specifier. 1304- **Breaking change**: The removal of implicit conversions between 1305 points and weighted points in the concept `Kernel` has incidentally 1306 created various minor breaking changes in the following packages: 2D 1307 Alpha Shapes, 2D and 3D Triangulations, and 3D Mesh Generation. See 1308 the full changelog for details. 1309 1310### Surface Mesh 1311 1312- **Breaking change**: 1313 `operator >>(std::istream&, Surface_mesh&)` no longer clears 1314 the surface mesh. 1315 1316### Triangulated Surface Mesh Parameterization (breaking change) 1317 1318- **Breaking change**: The package has been rewritten and can operate 1319 on any model of the `MutableFaceGraph` concept. All previous 1320 parameterization methods are still offered, although with a 1321 different, simpler API. The documentation has been updated and 1322 offers a gentle introduction to the new API. Users who wish to use 1323 the former API must use a version prior to 4.11. 1324- **Breaking change**: The adapter to add virtual seams is now the 1325 class `CGAL::Seam_mesh` in the package *CGAL and the BGL*. 1326- **Breaking change**: The package has been restructured and most 1327 headers have been moved. In a general manner, users should replace 1328 `<CGAL/XXX.h>` with `<CGAL/Surface_mesh_parameterization/XXX.h>` 1329- Add the *As Rigid As Possible Parameterization* method. This 1330 parameterization allows the user to prioritize angle preservation, 1331 shape preservation, or a balance of both. 1332- Add the *Orbifold Tutte Embedding* method. This parameterization 1333 method allows to parameterize meshes that are topological spheres. 1334 1335### 3D Surface Subdivision Methods (breaking changes) 1336 1337- The subdivision algorithms now work on any model of a 1338 `MutableFaceGraph`. A new API to the subdivision methods is offered, 1339 which uses optional named parameters to pass the number of 1340 iterations and a vertex property map. 1341- **Breaking change**: Removed the headers 1342 `<CGAL/Subdivision_method_3.h>` and `<CGAL/Subdivision_mask_3.h>`. 1343 The headers `<CGAL/Subdivision_method_3/subdivision_methods_3.h>` 1344 and `<CGAL/Subdivision_method_3/subdivision_masks_3.h>` should 1345 respectively be used instead. 1346- Sqrt3 subdivision can now handle input surfaces with a border. 1347 1348### Scale-Space Surface Reconstruction (breaking change) 1349 1350- **Breaking change**: the API was rewritten to separate the smoothing 1351 and meshing algorithm and making it possible for the user to use 1352 different ones. The default algorithms used are the same as before 1353 this API change, but methods are moved to the classes 1354 `Weighted_PCA_smoother` and `Alpha_shape_mesher`. 1355- Alternative smoothing and meshing methods are provided: 1356 `Jet_smoother` and `Advancing_front_mesher`. 1357 1358### 2D Alpha Shapes 1359 1360- **Breaking change**: Mirrored the concepts of the 2D alpha shape 1361 package with those of the 3D Alpha Shapes package. Consequently, a 1362 new concept, `WeightedAlphaShapeTraits_2`, is introduced to provide 1363 requirements on the traits class for 2D weighted alpha shapes. All 1364 models of the concept `Kernel` are models of this new concept. 1365- The concept `AlphaShapeTraits_2` now provides requirements on the 1366 traits class for 2D basic alpha shapes, and refines 1367 `DelaunayTriangulationTraits_2`. 1368 1369### Interpolation 1370 1371- **Breaking change**: The concept `GradientFittingTraits` now 1372 additionally requests a weighted point type `Weighted_point_d` and a 1373 functor `Construct_point_d`. The model 1374 `CGAL::Interpolation_gradient_fitting_traits_2` has been 1375 appropriately modified to still be a model of the concept 1376 `GradientFittingTraits`. 1377 1378### 2D and 3D Triangulations 1379 1380- **Breaking change**: Added a new functor requirement, 1381 `Construct_point_2`, to the concepts `TriangulationTraits_2` and 1382 `RegularTriangulationTraits_2` and a new functor requirement, 1383 `Construct_point_3`, to the concepts `TriangulationTraits_3` and 1384 `RegularTriangulationTraits_3`. All models of the concept `Kernel` 1385 already provide these functors. 1386- **Breaking change**: Introduced the concepts 1387 `RegularTriangulationVertexBase_2` and 1388 `RegularTriangulationVertexBase_3`. These concepts describe the 1389 requirements on classes meant to represent a vertex of a regular 1390 triangulation. Concepts that previously refined 1391 `TriangulationVertexBase_2` or `TriangulationVertexBase_3` but 1392 described in fact a vertex class used in a regular triangulation, 1393 such as the concept `MeshVertexBase_3` in the 3D mesh generation 1394 package, now refine the corresponding new regular vertex concept. 1395- **Breaking change**: Uniformized the point type across all vertex 1396 and cell concepts. The triangulation point type name is now always 1397 `Point`. Note that this does not change the requirements but only 1398 the name: `Point` is still expected to be equal to 1399 `Traits::Point_[23]` for basic and Delaunay triangulations or to 1400 `Traits::Weighted_point_[23]` for regular triangulations. 1401 Consequently: 1402 - The concept `RegularTriangulationVertexBase_2` now requests a 1403 `Point` type (equal to `Traits::Weighted_point_2`) 1404 - The concept `RegularTriangulationCellBase_3` now requests a 1405 `Point` type instead of a `Weighted_point` type (but still equal 1406 to `Traits::Weighted_point_3`) 1407 - The concept `DelaunayTriangulationCellBase_3` now requests a 1408 `Point` type instead of a `Point_3` type (but still equal to 1409 `Traits::Point_3`). 1410- Introduced a new concept, 1411 `RegularTriangulationCellBaseWithWeightedCircumcenter_3`, which 1412 describes the requirements on a cell of a regular triangulation that 1413 caches its circumcenter. The existing class 1414 `Regular_triangulation_cell_base_with_weighted_circumcenter_3` is 1415 the default model of this concept. 1416- Added a new 3D traits class, 1417 `Robust_weighted_circumcenter_filtered_traits_3` which provides 1418 robust versions of the kernel functors 1419 `Construct_weighted_circumcenter_3`, `Compute_squared_radius_3`, and 1420 `Compute_squared_radius_smallest_orthogonal_sphere_3`. This class 1421 can be used as traits class in the `Mesh_3` package to 1422 efficiently yet robustly generate 3D meshes. 1423- Add a new type of polyhedral domain with features, 1424 `Polyhedral_complex_mesh_domain_3`. The domain is defined by a 1425 collection of triangulated surfaces, forming a complex. 1426 1427### 3D Periodic Triangulations 1428 1429- Added new locate and geometric access functions for 3D periodic 1430 triangulations. 1431- The class `Periodic_3_Delaunay_triangulation_traits_3` now inherits 1432 `Periodic_3_triangulation_traits_3`. 1433- **Breaking change**: Some geometric access functions in 1434 `Periodic_3_triangulation_3` were renamed. The introduction of 1435 `Periodic_3_regular_triangulation_3` required to distinguish between 1436 functions such as `segment()` returning a segment of weightless 1437 points, or a segment of weighted points. As a general rule, previous 1438 geometrical access functions will return objects with point type 1439 that of the triangulation (thus, weighted objects when using 1440 weighted triangulations) and functions containing `construct` in the 1441 name will always return weightless geometrical objects. 1442- **Breaking change**: The concept `Periodic_3TriangulationTraits_3` 1443 now requests a domain getter: `get_domain()`. 1444- Introduced a new concept, 1445 `RegularTriangulationCellBaseWithWeightedCircumcenter_3`, which 1446 describes the requirements on a cell of a regular triangulation that 1447 caches its circumcenter. The existing class 1448 `Regular_triangulation_cell_base_with_weighted_circumcenter_3` is 1449 the default model of this concept. 1450 1451### 3D Mesh Generation 1452 1453- **Breaking change**: The type of the surface center in the concept 1454 `MeshCellBase_3` has been changed from `Triangulation::Point` to 1455 `TriangulationTraits::Point_3` to reflect that it is a weightless 1456 point. 1457- **Breaking change**: The function `invalidate_circumcenter()` of the 1458 concept `MeshCellBase_3` is renamed to 1459 `invalidate_weighted_circumcenter_cache()` and moved to the new 1460 concept `RegularTriangulationCellBaseWithWeightedCircumcenter_3`, 1461 which the concept `MeshCellBase_3` now refines. 1462 1463### Poisson Surface Reconstruction 1464 1465- A new global function 1466 `CGAL::poisson_surface_reconstruction_delaunay()` is provided in 1467 addition to the current class-based API in order to make it easier 1468 to use. 1469 1470### Point Set Processing 1471 1472- New functions to read from and write to LAS/LAZ files (LIDAR 1473 format), with or without taking additional properties into account. 1474- **Breaking change:** The API of the PLY function to read points with 1475 properties is modified for unification with LAS (see 1476 `CGAL::read_ply_points_with_properties()`). A new function to write 1477 PLY with properties is provided 1478 (`CGAL::write_ply_points_with_properties()`). 1479 1480### Spatial Searching 1481 1482- Add function `Kd_tree::remove(Point)`. 1483 1484### 3D Fast Intersection and Distance Computation 1485 1486- Add a template parameter to `AABB_traits` for a property map that 1487 associates a bounding box to a primitive 1488 1489### CGAL and the Boost Graph Library 1490 1491- Add a partial specialization for the class 1492 `CGAL::Linear_cell_complex_for_combinatorial_map` so that it is a 1493 model of the graph concepts `BidirectionalGraph` and 1494 `EdgeAndVertexListGraph` and of the concept `MutableFaceGraph`. This 1495 class can thus now be used in all BGL functions and algorithms. 1496- Helper functions to create an icosahedron, a regular prism and a 1497 pyramid have been added. 1498- Add class `CGAL::Face_filtered_graph` that wraps an existing graph 1499 and hide all simplices that are not in the selected connected 1500 components. 1501- Added the class `CGAL::Seam_mesh`. The `Seam_mesh` is a graph 1502 adaptor which allows to create virtual borders when marking edges as 1503 seam edges. 1504- Add the functions `read_off()` and `write_off()`. 1505 1506Release 4.10 1507------------ 1508 1509Release date: May 2017 1510 1511### Installation 1512 1513- The minimum required version of CMake is now 3.1. All CMake versions 1514 up to 3.7 are supported. 1515- The compilation of some demo may require a C++11 compiler. The CGAL 1516 library itself still support C++03 compilers. 1517- The shell script `cgal_create_cmake_script` now enables C++14 by 1518 default. 1519- A new mechanism to check which packages of CGAL are used have been 1520 added. It is particularly interesting for commercial users to ensure 1521 they have a valid commercial license for the packages they used. 1522 This can also be used to make sure only LGPL header files are used. 1523- Because of a bug in the g++ compiler about the C++11 keyword 1524 `thread_local`, the CGAL\_Core library now always requires 1525 `Boost.Thread` if the g++ compiler is used. 1526 1527### Generalized Maps (new package) 1528 1529- This package implements Generalized Maps in d dimensions. A 1530 generalized map is a data structure enabling to represent an 1531 orientable or non orientable subdivided object by describing all the 1532 cells of the subdivision (for example in 3D vertices, edges, faces, 1533 volumes) and all the incidence and adjacency relationships between 1534 these cells. This data structure is the generalization of the 1535 combinatorial maps in order to be able to represent non orientable 1536 objects. 1537 1538### 3D Point Set (new package) 1539 1540- This package provides a flexible data structure `CGAL::Point_set_3` 1541 that allows the user to easily handle point sets with an arbitrary 1542 number of attributes (such as normal vectors, colors, labeling, 1543 etc.). 1544 1545### Combinatorial Maps and Linear cell complex 1546 1547- **Breaking change**: the requirements of the item class used to 1548 customize a combinatorial map and a linear cell complex changed. 1549 Instead of defining the type of darts used, you have to define the 1550 information you want to add in each dart. You can define the 1551 `CGAL_CMAP_DART_DEPRECATED` macro to keep the old behavior. 1552 1553### Triangulated Surface Mesh Shortest Paths 1554 1555- **Breaking change**: Rename all functions, types, and enums using 1556 *barycentric coordinate* to *barycentric coordinates*. 1557 1558### CGAL and the Boost Graph Library (BGL) 1559 1560- **Breaking change**: Addition of a free function `reserve()` in the 1561 concept `MutableFaceGraph`. Models provided by CGAL have been 1562 updated. 1563 1564### 2D and 3D Linear Geometry Kernel 1565 1566- **Breaking change**: The function `compare_slopes()` was renamed 1567 `compare_slope`. 1568- Added a 2D and 3D weighted point class and predicates and 1569 constructions. 1570- Add functions `l_infinity_distance()` for 2D and 3D. 1571- Add a new functor in CGAL Kernel concept to compare the slope of two 1572 3D segments. All models of the Kernel concept now provide the 1573 functor `Compare_slope_3`, and the free function `compare_slope()` 1574 is available. 1575- Add an operator in CGAL Kernel concept `Angle_3` to qualify the 1576 angle between the normal of the triangle given by three points, and 1577 a vector. 1578 1579### 3D Convex Hull 1580 1581- The convex hull function can also produce a `Surface_mesh`, and 1582 generally speaking any model of the concept `MutableFaceGraph` 1583- The function `convex_hull_3_to_polyhedron_3()` is deprecated and 1584 `convex_hull_3_to_face_graph.h` should be used instead. 1585- The class `Convex_hull_traits_3` now documents a nested type 1586 `Polygon_mesh` instead of `Polyhedron_3`. The other nested type is 1587 kept for backward compatibility. 1588- Remove the function `CGAL::convex_hull_incremental_3()` deprecated 1589 since CGAL 4.6. 1590 1591### 3D Boolean Operations on Nef Polyhedra 1592 1593- Add a new constructor from a face graph model 1594 1595### Linear cell complex 1596 1597- Deprecate class `Linear_cell_complex` which is now renamed 1598 `Linear_cell_complex_for_combinatorial_map_dart`. 1599 1600### 2D Triangulation data structure 1601 1602- Add function `insert_in_hole`. 1603 1604### 2D Triangulations 1605 1606- **Breaking change**: Removed the arbitrary dimensional weighted 1607 point class. Users must use a version prior to 4.9 if they need this 1608 class. 1609- **Breaking change**:The number type of weighted points in regular 1610 triangulations is no longer a template parameter but the field type 1611 of the geometric traits class. Users who need this feature must use 1612 a version prior to 4.9 1613- The class `Regular_triangulation_filtered_traits_2` deprecated since 1614 CGAL 3.6 has been removed. 1615- Deprecate the class `Regular_triangulation_euclidean_traits_2`, as 1616 the weighted point and the function objects for weighted points are 1617 part of the concept `Kernel`/ 1618- The class `Regular_triangulation_2` can take a kernel as template 1619 argument, that is one no longer has to use 1620 `Regular_triangulation_euclidea_traits_2`, although this still 1621 works. 1622 1623### 3D Triangulations 1624 1625- **Breaking change**: The number type of weighted points in regular 1626 triangulations is no longer a template parameter but the field type 1627 of the geometric traits class. Users who need this feature must use 1628 a version prior to 4.9. 1629- The class `Regular_triangulation_filtered_traits_3` deprecated since 1630 CGAL 3.6 has been removed. 1631- Deprecate the class `Regular_triangulation_euclidean_traits_3`, as 1632 the weighted point and the function objects for weighted points are 1633 part of the concept `Kernel`/ 1634- The class `Regular_triangulation_3` can take a kernel as template 1635 argument, that is one no longer has to use 1636 `Regular_triangulation_euclidean_traits_3`, although this still 1637 works. 1638- Add function `link_to_face_graph()` to copy the set of faces 1639 incident to a vertex into a model of `FaceGraph`. 1640 1641### 3D Mesh Generation 1642 1643- The constructor 1644 `CGAL::Polyhedral_mesh_domain_with_features_3(std::string)` is 1645 deprecated. 1646 1647### Polygon Mesh Processing 1648 1649- Add fast and robust corefinement and Boolean operation functions for 1650 triangulated surface meshes: 1651 - `CGAL::Polygon_mesh_processing::corefine_and_compute_union()` 1652 - `CGAL::Polygon_mesh_processing::corefine_and_compute_difference()` 1653 - `CGAL::Polygon_mesh_processing::corefine_and_compute_intersection()` 1654 - `CGAL::Polygon_mesh_processing::corefine()` 1655 - `CGAL::Polygon_mesh_processing::does_bound_a_volume()` 1656 - `CGAL::Polygon_mesh_processing::surface_intersection()` 1657- Add functions to compute approximated Hausdorff distances between 1658 two meshes, a mesh and a point set, or a point set and a mesh: 1659 `sample_triangle_mesh()`, `approximated_Hausdorff_distance()`, 1660 `approximated_symmetric_Hausdorff_distance()`, 1661 `max_distance_to_triangle_mesh()`, `max_distance_to_point_set()`. 1662- The function `CGAL::Polygon_mesh_processing::bbox_3()` has been 1663 renamed `CGAL::Polygon_mesh_processing::bbox()`. 1664 1665### Point Set Processing 1666 1667- Function `CGAL::remove_outliers()` has an additional parameter based 1668 on a distance threshold to make it easier and more intuitive to use. 1669- New functions for automatic scale estimations: either a global scale 1670 or multiple local scales can be estimated for both 2D and 3D point 1671 sets based on the assumption that they sample a curve in 2D or a 1672 surface in 3D. 1673 1674### CGAL and the Boost Graph Library (BGL) 1675 1676- Add function `CGAL::convert_nef_polyhedron_to_polygon_mesh()` to 1677 convert a `Nef_polyhedron_3` to any model of the `MutableFaceGraph` 1678 concept. 1679- Add class `CGAL::Graph_with_descriptor_with_graph` that wraps an 1680 existing graph and provides a reference to the said graph to all of 1681 its descriptors. 1682 1683### Cone Based Spanners 1684 1685- Add a parameter to compute half Tao graph and half Theta graph. 1686- Add an ipelet for this package. 1687 1688### Geometric Object Generators 1689 1690- Add point random generators 1691 - in a 3D triangle mesh model of the concept `FaceListGraph` 1692 (`CGAL::Random_points_in_triangle_mesh_3`), 1693 - on the boundary of a tetrahedral mesh 1694 (`CGAL::Random_points_in_tetrahedral_mesh_boundary_3`), 1695 - in a tetrahedral mesh 1696 (`CGAL::Random_points_in_tetrahedral_mesh_3`), 1697 - in a 2D triangle mesh 1698 (`CGAL::Random_points_in_triangle_mesh_2`), 1699 - in a range of 2D or 3D triangles 1700 (`CGAL::Random_points_in_triangles_3` and 1701 `CGAL::Random_points_in_triangles_2`). 1702 - on a 3D segment (`CGAL::Random_points_on_segment_3`). 1703 1704Release 4.9 1705----------- 1706 1707Release date: Sept 2016 1708 1709### Header-only mode 1710 1711- CGAL can now be used in headers only mode, i.e. without compiling 1712 the CGAL libraries and linking with these libraries when compiling 1713 examples, tests and demos. Note that running CMake on CGAL is still 1714 required in order to generate some configuration files. 1715 1716### Cone Based Spanners (new package) 1717 1718- This package provides algorithms for constructing two kinds of 1719 cone-based spanners: Yao graph and Theta graph, given a set of 1720 vertices on the plane and the directions of cone boundaries. 1721 1722### 2D Minkowski Sums 1723 1724- Introduce a convex decomposition strategy, namely 1725 `Polygon_nop_decomposition_2`, that merely passed the input polygon 1726 to the list of output polygons. 1727- Introduce overloads of the function `minkowski_sum_2()`, which 1728 accepts 2 decomposition strategies. 1729- Introduce an overloaded function called 1730 `minkowski_sum_by_decomposition_2(P, Q, decom_no_holes, decomp_with_holes)`, 1731 which computes the 2D Minkowski sum using optimal choices of 1732 decomposition strategies. 1733 1734### Combinatorial Maps 1735 1736- Deprecate global functions (`make_combinatorial_hexahedron()`, 1737 `make_combinatorial_polygon()`, `make_combinatorial_tetrahedron()`, 1738 `make_edge()`, `insert_cell_0_in_cell_1()`, 1739 `insert_cell_0_in_cell_2()`, `insert_cell_1_in_cell_2()`, 1740 `insert_cell_2_in_cell_3()`, `insert_dangling_cell_1_in_cell_2()`, 1741 `is_insertable_cell_1_in_cell_2()`, 1742 `is_insertable_cell_2_in_cell_3()`, `is_removable()`, 1743 `remove_cell()`) which are now member functions in the 1744 `CombinatorialMap` concept. 1745- It is not longer possible to use the old API switched on by defining 1746 the macro `CGAL_CMAP_DEPRECATED`. This API was deprecated since CGAL 1747 4.4. 1748 1749### Point Set Processing 1750 1751- New function `CGAL::read_ply_custom_points()` that allows the user 1752 to read any additional point attribute from a PLY input point set. 1753- `CGAL::structure_point_set()`: new algorithm that takes advantage of 1754 detected planes to produce a structured point set (with flat 1755 regions, sharp edges and vertices). 1756 1757### Point Set Shape Detection 1758 1759- New post-processing algorithm: `CGAL::regularize_planes()`. This 1760 allows the user to favor parallelism, orthogonality, coplanarity 1761 and/or axial symmetry between detected planes. 1762 1763### Polygon Mesh Processing 1764 1765- Add the function 1766 `CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh()` to 1767 check whether a polygon soup is a polygon mesh. 1768- Add some new features to `CGAL::isotropic_remeshing()`: 1769 - It is now possible to select fixed vertices that survive the 1770 remeshing process, and to keep face attributes such as colors 1771 valid after remeshing. 1772 - The user can choose the number of relaxation steps happening at 1773 each loop, and to run 1-dimensional relaxation along constrained 1774 polylines. 1775- The functions `CGAL::Polygon_mesh_processing::triangulate_face()` 1776 and `CGAL::Polygon_mesh_processing::triangulate_faces()` now 1777 indicate whether some faces have not been triangulated. 1778 1779### Surface Mesh Deformation 1780 1781- Add a new tag `SRE_ARAP` to use the Smoothed Rotation Enhanced 1782 As-Rigid-As-Possible deformation algorithm. 1783 1784### 3D Fast Intersection and Distance Computation 1785 1786- Add the functions `AABB_tree::first_intersection()` and 1787 `AABB_tree::first_intersected_primitive()` that compute the 1788 intersection which is closest to the source of a ray 1789 1790### CGAL and the Boost Graph Library (BGL) 1791 1792- Add a helper function `CGAL::copy_face_graph()` to copy a source 1793 FaceListGraph into another FaceListGraph of different type. 1794- Add a class `CGAL::Dual` that creates the dual view of a `FaceGraph` 1795 and a creation function `CGAL::dual(primal)`. 1796 1797#### CGAL and Boost Property Maps 1798 1799- It is not longer possible to use the old API of the property maps 1800 provided by CGAL, switched on by defining the macro 1801 `CGAL_USE_PROPERTY_MAPS_API_V1`. This API was deprecated since CGAL 1802 4.3. 1803 1804Release 4.8 1805----------- 1806 1807Release date: April 2016 1808 1809### General 1810 1811- The support for Qt3 is dropped and all demos using it got removed. 1812 1813### Installation 1814 1815- Starting with Visual C++ 2015 we no longer require `Boost.Thread` as 1816 we use the C++11 keyword `thread_local` and the C+11 class 1817 `std::mutex` . 1818- The same holds for g++ 4.8 or later when the C++11 standard is used. 1819 1820### Optimal Transportation Curve Reconstruction (new package) 1821 1822- This package implements a method to reconstruct and simplify 2D 1823 point sets. The input is a set of 2D points with mass attributes, 1824 possibly hampered by noise and outliers. The output is a set of line 1825 segments and isolated points which approximate the input points. 1826 1827### 2D Regularized Boolean Set-Operations 1828 1829- Improve the performance of operations in some settings. 1830 **Breaking change**: This improvement requires changes of the face 1831 and halfedge type of the underlying arrangement Dcel. See the 1832 concepts `GeneralPolygonSetDcelHalfedge` and 1833 `GeneralPolygonSetDcelFace` for more details. If you use a different 1834 simplex types, inheriting your simplices from `CGAL::Gps_face_base` 1835 and `CGAL::Gps_halfedge_base` is sufficient to accommodate for the 1836 update. 1837 1838### 3D Boolean Operations on Nef Polyhedra 1839 1840- Add 3 new constructors: from a point range, from a point, and from a 1841 segment. 1842 1843### Combinatorial Maps 1844 1845- **Breaking change**: Change the type of Boolean marks, old type is 1846 int, new type is `size_type`. If no more mark is available, 1847 `get_new_mark` throws an exception, instead of returning `-1`. 1848 1849### 2D Arrangements 1850 1851- Speed up the edge removal in case the incident faces contains many 1852 holes. 1853- Set the format of polylines and polycurves. The format of a general 1854 polyline or polycurve consists of the sequence of subcurves that 1855 comprise the original curve. The format of a polyline of linear 1856 segments consists of the sequence of points that define the original 1857 curve. (The latter restores the format used before polycurves were 1858 introduced in 4.7.) Fix the extraction from istream and insertion 1859 into ostream operators of polylines and polycurves accordingly. 1860- Fix the traits class that handles Bezier curves. In particular, fix 1861 the case where the curve is closed (i.e, the first and last control 1862 points coincide). 1863 1864### 3D Mesh Generation 1865 1866- Add support of 3D gray level images as input for the tetrahedral 1867 mesh generation. 1868- **Breaking change:** All models of the concept `MeshDomain_3` must 1869 now provide a member function `bbox()`. 1870 1871### Advancing Front Surface Reconstruction 1872 1873- Optional template functor `Filter` is replaced by another optional 1874 template functor `Priority`. This allows to change the way facets 1875 are prioritized by the algorithm instead of having a simple option 1876 to reject some facets. 1877 **Breaking change**: Programs using the old `Filter` API will not 1878 compile anymore as it must be replaced with the `Priority` API as 1879 described in the manual. Codes using the default behavior are not 1880 impacted. 1881 1882### Polygon Mesh Processing 1883 1884- Add a new triangle-based isotropic remeshing algorithm for 1885 triangulated surface meshes, 1886 `CGAL::Polygon_mesh_processing::isotropic_remeshing()` and a helper 1887 function for isotropic remeshing : 1888 `CGAL::Polygon_mesh_processing::split_long_edges()` 1889- Add the function `CGAL::Polygon_mesh_processing::border_halfedges()` 1890 to collect the border of a given face range 1891- Add the function 1892 `CGAL::Polygon_mesh_processing::remove_isolated_vertices()` to be 1893 used on any polygon mesh 1894- Add the function `CGAL::Polygon_mesh_processing::triangulate_face()` 1895 to triangulate a single face of a polygon mesh 1896- Add an overload for 1897 `CGAL::Polygon_mesh_processing::triangulate_faces()` to triangulate 1898 a range of faces of a polygon mesh 1899- Add function `keep_large_connected_components()` 1900- Add measuring functions for polygon meshes, to compute length, area, 1901 and volume of simplices or group of simplices of a polygon mesh. 1902- Add function `bbox_3()` to compute the bounding box of a polygon 1903 mesh. 1904 1905### Point Set Processing 1906 1907- **Breaking change:** new template parameter `Concurrency_tag` for 1908 the functions `compute_average_spacing()`, 1909 `edge_aware_upsample_point_set()`, `jet_estimate_normals()`, 1910 `jet_smooth_point_set()`, and `pca_estimate_normals()`. To update 1911 your code simply add as first template parameter 1912 `CGAL::Sequential_tag` or `CGAL::Parallel_tag` when calling one of 1913 these functions. 1914- `CGAL::Parallel_tag` can no longer be used in Point Set Processing 1915 algorithms if TBB is not available. 1916- Add a new simplification algorithm based on hierarchical clustering: 1917 `CGAL::hierarchy_simplify_point_set()`. It allows either to 1918 uniformly simplify the point set or to automatically adapt the local 1919 density of points to the local variation of the input computed by 1920 principal component analysis. 1921- New IO functions for PLY format (Polygon File Format): 1922 `CGAL::read_ply_points()`, `CGAL::read_ply_points_and_normals()`, 1923 `CGAL::write_ply_points()` and 1924 `CGAL::write_ply_points_and_normals()`. 1925 1926### Surface Mesh Parameterization 1927 1928- `LSCM_parameterizer_3` now uses by default Eigen instead of OpenNL 1929 as a model of `SparseLinearAlgebraTraits_d`. 1930 1931### Spatial Searching 1932 1933- Add function to find any point in a range query, that is neither all 1934 points, nor the closest one. 1935 1936### Principal Component Analysis 1937 1938- Add a template parameter `DiagonalizeTraits` for functions 1939 `CGAL::linear_least_squares_fitting_2()` and 1940 `CGAL::linear_least_squares_fitting_3()`. This allows to either 1941 choose the legacy internal diagonalization code from CGAL or the 1942 Eigen implementation (or any class that is a model of 1943 `DiagonalizeTraits`). Variants of the function that automatically 1944 deduce the kernel also automatically select the diagonalizer, so the 1945 API is mostly preserved. 1946 1947### CGAL and Solvers 1948 1949- This package now includes all CGAL concepts for solvers with models 1950 using the third party Eigen library. 1951 1952### CGAL and the Boost Graph Library (BGL) 1953 1954- Add function `CGAL::split_graph_into_polylines()` that allows to 1955 extract from a soup of segments given as a graph, polylines with 1956 nodes of degree at most 2. In addition a functor can be passed to 1957 the function to specify additional polyline endpoints. 1958- New functions to manipulate selection of faces, edges and vertices 1959 in a halfedge graph are added: `CGAL::expand_face_selection()`, 1960 `CGAL::reduce_face_selection()`, `CGAL::expand_edge_selection()`, 1961 `CGAL::reduce_edge_selection()` `CGAL::expand_vertex_selection()`, 1962 `CGAL::reduce_vertex_selection()` and 1963 `CGAL::select_incident_faces()`. 1964- Add a helper function `CGAL::clear` which clears a MutableFaceGraph 1965 efficiently and generically. 1966 1967Release 4.7 1968----------- 1969 1970Release date: October 2015 1971 1972### Installation 1973 1974- The minimum required version of CMake is now 2.8.11. CMake versions 1975 3.1, 3.2, and 3.3 are supported. 1976- All Qt4 demos have been updated and now require Qt5 to be compiled. 1977 Qt5 version 5.3 or higher is required. The support for Qt4 is 1978 dropped. To compile libCGAL\_Qt5 and demos, you must set the cmake 1979 or environment variable `Qt5_DIR` to point to the path to the 1980 directory containing the file `Qt5Config.cmake` created by your Qt5 1981 installation. If you are using the open source edition it should be 1982 `/path-to/qt-everywhere-opensource-src-<version>/qtbase/lib/cmake/Qt5`. 1983- The code of the 3D demos now uses modern OpenGL, with shaders, 1984 instead of the fixed pipeline API of OpenGL-1. 1985- The Microsoft Windows Visual C++ compiler 2015 (VC14) is now 1986 supported. However, since this compiler is not officially supported 1987 by Intel TBB 4.4 and Qt 5.5 (the latest versions available at the 1988 time of this release), the parallelism features of CGAL and Qt5 1989 demos will not work. 1990 1991### L Infinity Segment Delaunay Graphs (new package) 1992 1993- The package provides the geometric traits for constructing the 1994 segment Delaunay graph in the max-norm (L Infinity). The traits also 1995 contain methods to draw the edges of the dual of the segment 1996 Delaunay graph in the max-norm i.e., the segment Voronoi diagram in 1997 the max-norm. The algorithm and traits rely on the segment Delaunay 1998 graph algorithm and traits under the Euclidean distance. The segment 1999 Voronoi diagram in the max-norm has applications in VLSI CAD. 2000 2001### Advancing Front Surface Reconstruction (new package) 2002 2003- This package provides a greedy algorithm for surface reconstruction 2004 from an unorganized point set. Starting from a seed facet, a 2005 piecewise linear surface is grown by adding Delaunay triangles one 2006 by one. The most plausible triangles are added first, in a way that 2007 avoids the appearance of topological singularities. 2008 2009### Triangulated Surface Mesh Shortest Paths (new package) 2010 2011- The package provides methods for computing shortest path on 2012 triangulated surface meshes. Given a set of source points on the 2013 surface, this package provides a data structure that can efficiently 2014 provides the shortest path from any point on the surface to the 2015 sources points. There is no restriction on the genus or the number 2016 of connected components of the mesh. 2017 2018### Triangulated Surface Mesh Skeletonization (new package) 2019 2020- This package provides a (1D) curve skeleton extraction algorithm for 2021 a triangulated polygonal mesh without borders based on the mean 2022 curvature flow. The particularity of this skeleton is that it 2023 captures the topology of the input. For each skeleton vertex one can 2024 obtain its location and its corresponding vertices from the input 2025 mesh. The code is generic and works with any model of the 2026 \`FaceListGraph\` concept. 2027 2028### 3D Point-Set Shape Detection (new package) 2029 2030- This package implements the efficient RANSAC method for shape 2031 detection, contributed by Schnabel et al. From an unstructured point 2032 set with unoriented normals, the algorithm detects a set of shapes. 2033 Five types of primitive shapes are provided by this package: plane, 2034 sphere, cylinder, cone and torus. Detecting other types of shapes is 2035 possible by implementing a class derived from a base shape. 2036 2037### 2D Visibility (new package) 2038 2039- This package provides several variants to compute the visibility 2040 area of a point within polygonal regions in two dimensions. 2041 2042### Polygon Mesh Processing (new package) 2043 2044- This package implements a collection of methods and classes for 2045 polygon mesh processing, ranging from basic operations on simplices, 2046 to complex geometry processing algorithms. The implementation of 2047 this package mainly follows algorithms and references given in 2048 Botsch et al.'s book on polygon mesh processing. 2049 2050### General 2051 2052- Support for unordered sets and maps of the stdlib and of boost for 2053 handle and index classes. 2054 2055### Approximation of Ridges and Umbilics on Triangulated Surface Meshes 2056 2057- This package now supports any model of the concept `FaceGraph`. 2058- **Breaking change:** The package no longer supports models of 2059 `TriangulatedSurfaceMesh` which are not at the same time models of 2060 the concept `FaceGraph`. 2061 2062### dD Geometry Kernel 2063 2064- Epick\_d gains 3 new functors: `Construct_circumcenter_d`, 2065 `Compute_squared_radius_d`, `Side_of_bounded_sphere_d`. Those are 2066 essential for the computation of alpha-shapes. 2067 2068### 2D Arrangements 2069 2070- Introduced a new traits class, called 2071 `Arr_polycurve_traits_2<SubcurveTraits>`, which handles general 2072 piece-wise (polycurve) curves. The pieces do not necessarily have to 2073 be linear. 2074- Introduced two new concepts called `ArrangementApproximateTraits_2` 2075 and `ArrangementConstructXMonotoneCurveTraits_2`. 2076 - The existing `ArrangementLandmarkTraits_2` concept, which has 2077 two requirements, now refines the two respective concepts above. 2078 - The template parameter of the existing 2079 `Arr_polyline_traits_2<SegmentTraits>` template must be 2080 substituted with a traits class that is a model of the 2081 `ArrangementConstructXMonotoneTraits_2` concept among the other 2082 when `Arr_polyline_traits_2` is instantiated. 2083 2084### 2D Minkowski Sums 2085 2086- Added support for polygons with holes and optimized the construction 2087 of Minkowski sums. 2088 - Introduced an implementation of the "reduced convolution" 2089 method, a variant of the method described in "2D Minkowski Sum 2090 of Polygons Using Reduced Convolution" by Behar and Lien. The 2091 new method supports polygons with holes and in many cases out 2092 pergorms the implementation of the exsisting (full) convolution 2093 method. 2094 - Introduced two new classes that decompose polygons into convex 2095 pieces (models of the `PolygonConvexDecomposition_2` concept) 2096 based on vertical decomposition and constrained Delaunay 2097 triangulation, respectively. These new models also support the 2098 convex decomposition of polygons with holes. 2099 2100### 3D Periodic Triangulations 2101 2102- Rename `Periodic_3_triangulation_traits_3` to 2103 `Periodic_3_Delaunay_triangulation_traits_3`. 2104- Rename the concept `Periodic_3TriangulationTraits_3` to 2105 `Periodic_3DelaunayTriangulationTraits_3`. 2106- Create `Periodic_3_triangulation_traits_3` and the concept 2107 `Periodic_3TriangulationTraits_3`. 2108 2109### 2D Conforming Triangulations and Meshes 2110 2111- Add an optimization method `CGAL::lloyd_optimize_mesh_2()` that 2112 implements the Lloyd (or Centroidal Voronoi Tesselation) 2113 optimization algorithm in a Constrained Delaunay Triangulation. For 2114 optimization, the triangulation data structure on which the mesher 2115 relies needs its `VertexBase` template parameter to be a model of 2116 the new concept `DelaunayMeshVertexBase_2`. 2117 2118### Point Set Processing and Surface Reconstruction from Point Sets 2119 2120- Add the function `CGAL::compute_vcm()` for computing the Voronoi 2121 Covariance Measure (VCM) of a point set. The output of this function 2122 can be used with the function `CGAL::vcm_is_on_feature_edge()` to 2123 determine whether a point is on or close to a feature edge. The 2124 former function is also internally used by 2125 `CGAL::vcm_estimate_normals()` to estimate the normals of a point 2126 set and it is particularly suited to point sets with noise. 2127 2128### Spatial Sorting 2129 2130- Add the possibility to sort points on a sphere along a space-filling 2131 curve using the functions `CGAL::hilbert_sort_on_sphere` and 2132 `CGAL::spatial_sort_on_sphere`. 2133 2134### Geometric Object Generators 2135 2136- Add new random generator of points in a 2D and 3D triangle and in a 2137 tetrahedron (`CGAL::Random_points_in_triangle_2`, 2138 `CGAL::Random_points_in_triangle_3`, 2139 `CGAL::Random_points_in_tetrahedron_3`). 2140 2141Release 4.6.2 2142------------- 2143 2144Release date: August 2015 2145 2146This release only fixes bugs. See the list of fixed bugs on Github: 2147 2148<https://github.com/CGAL/cgal/issues?q=milestone%3A4.6.2> 2149 2150Release 4.6.1 2151------------- 2152 2153Release date: June 2015 2154 2155This release only fixes bugs. See the list of fixed bugs on Github: 2156 2157<https://github.com/CGAL/cgal/issues?q=milestone%3A4.6.1+-label%3Ainvalid> 2158 2159Release 4.6 2160----------- 2161 2162Release date: April 2015 2163 2164### Installation 2165 2166- The required version of Boost is now 1.48 or higher. 2167 2168### 2D Polyline Simplification (new package) 2169 2170- This package enables to simplify polylines with the guarantee that 2171 the topology of the polylines does not change. This can be done for 2172 a single polyline as well as for a set of polyline constraints in a 2173 constrained triangulation. The simplification can be controlled with 2174 cost and stop functions. 2175 2176### 2D Generalized Barycentric Coordinates (new package) 2177 2178- This package offers an efficient and robust implementation of 2179 two-dimensional closed-form generalized barycentric coordinates 2180 defined for simple two-dimensional polygons. 2181 2182### Scale-Space Surface Reconstruction (new package) 2183 2184- This new package provides a class gathering a dedicated smoothing 2185 algorithm and some convenience functions to help the creation of a 2186 surface out of a point set using the 3D Alpha Shapes package. The 2187 particularity of this reconstruction pipeline is that the input 2188 point are in the output and no new points are created. Note that in 2189 the current version, the output is a triangle soup that is not 2190 necessarily a valid (manifold) polyhedral surface. 2191 2192### Surface Mesh (new package) 2193 2194- The surface mesh class provided by this package is an implementation 2195 of the halfedge data structure allowing to represent polyhedral 2196 surfaces. It is an alternative to the packages `CGAL::Polyhedron_3` 2197 and `CGAL::HalfedgeDS`. 2198 2199### dD Triangulation (new package) 2200 2201- This new package provides classes for manipulating triangulations in 2202 Euclidean spaces whose dimension can be specified at compile-time or 2203 at run-time. It also provides a class that represents Delaunay 2204 triangulations. 2205 2206### dD Convex Hulls and Delaunay Triangulations 2207 2208- This package is deprecated and the new package Triangulation should 2209 be used instead. 2210 2211### dD Geometry Kernel 2212 2213- It has been reported that the recently introduced `Epick_d` kernel 2214 may not work with Intel C++ Compiler prior to version 15. 2215 Documentation has been updated. 2216 2217### 3D Convex Hulls 2218 2219- Add functions `halfspace_intersection_3` and 2220 `halfspace_intersection_with_constructions_3` to compute the 2221 intersection of halfspaces defining a closed polyhedron. 2222- Fix a bug introduced in CGAL 4.5 that can appear while computing the 2223 convex hull of coplanar points. 2224- Fix a robustness issue in `Convex_hull_traits_3`. This traits is 2225 used by default with the kernel 2226 `Exact_predicates_inexact_constructions_kernel`. 2227- The function `CGAL::convex_hull_incremental_3` is deprecated and the 2228 function `convex_hull_3` should be used instead. 2229 2230### Combinatorial Maps and Linear Cell Complex 2231 2232- Added `correct_invalid_attributes`, 2233 `set_automatic_attributes_management` and 2234 `are_attributes_automatically_managed` methods in `CombinatorialMap` 2235 concept. This allows high level operations to not update non void 2236 attributes during massive calls of these operations, but only after 2237 the end of their executions. 2238 2239### 2D Triangulations 2240 2241- The class `Constrained_triangulation_plus_2` now can handle 2242 polylines as constraints. 2243- As a consequence a `Constraint_id` has been introduced which 2244 replaces `pair<Vertex_handle,Vertex_handle>` as identifier of a 2245 constraint. 2246 2247### 3D Mesh Generation 2248 2249- Add member functions `output_boundary_to_off` and 2250 `output_facets_in_complex_to_off` in the class 2251 `CGAL::Mesh_complex_3_in_triangulation_3` to export the boundary of 2252 a domain or a subdomain. 2253 2254### 3D Fast Intersection and Distance Computation 2255 2256- Add new constructors to `AABB_halfedge_graph_segment_primitive` and 2257 `AABB_face_graph_triangle_primitive` in order to be able to build 2258 primitives one by one. 2259 2260### Spatial Searching 2261 2262- Fixed a bug in `CGAL::Splitters.h` sliding midpoint rule, where 2263 degenerated point sets (e.g.,points on segment) caused the kd-tree 2264 to get linear. 2265- Improved performance of `Orthogonal_k_neighbor_search`. Note that VC 2266 2013 does not compile `boost::container::deque` of Boost 1\_55 and 2267 does hence have a workaround which does not have the improvement. 2268- **Breaking change:** The concept `OrthogonalDistance` has new 2269 function overloads for `min_distance_to_rectangle` and 2270 `max_distance_to_rectangle` with an additional reference parameter 2271 `std::vector`. 2272- **Breaking change:** The order of the points in the iterator range 2273 `[tree.begin(),tree.end()]` is not the order of insertion of the 2274 points into the tree. This was not guaranteed before but might have 2275 been observed and exploited by users. 2276- Derived `kd_tree_leaf_node` and `kd_tree_internal_node` from 2277 `kd_tree_node` to save memory. 2278 2279### Geometric Object Generators 2280 2281- Add a new function `random_convex_hull_in_disc_2` that efficiently 2282 generates a random polygon as the convex hull of uniform random 2283 points chosen in a disc. 2284 2285Release 4.5.2 2286------------- 2287 2288Release date: February 2015 2289 2290### General 2291 2292- Fix a bug that prevented the compilation with recent versions of 2293 Boost (>=1.56) when explicit conversions operators (from C++11) 2294 are supported. That prevented the compilation with Microsoft Visual 2295 Studio 2013. 2296 2297### 3D Convex Hulls 2298 2299- Fix a non-robust predicate bug that was showing up when input points 2300 where lexicographically sorted. 2301 2302### 3D Mesh Generation 2303 2304- Fix a bug in the sliver perturbation optimization method. It could 2305 create some holes on the surface of the mesh. 2306 2307Release 4.5.1 2308------------- 2309 2310Release date: December 2014 2311 2312### 3D Mesh Generation 2313 2314- Fix a bug in the sliver exudation preservation of boundaries. 2315 2316Release 4.5 2317----------- 2318 2319Release date: October 2014 2320 2321### Installation 2322 2323- Changes in the set of supported platforms: 2324 - The Microsoft Windows Visual C++ compiler 2008 (VC9) is no 2325 longer supported since CGAL-4.5. 2326- Since CGAL version 4.0, Eigen was the recommended third-party 2327 library to use with *Planar Parameterization of Triangulated Surface 2328 Meshes*, *Surface Reconstruction from Point Sets*, *Approximation of 2329 Ridges and Umbilics on Triangulated Surface Meshes*, and *Estimation 2330 of Local Differential Properties of Point-Sampled Surfaces* 2331 packages. From CGAL version 4.5, Taucs, Blas and Lapack are no 2332 longer supported. 2333- CGAL is now compatible with the new CMake version 3.0. 2334 2335### Triangulated Surface Mesh Deformation (new package) 2336 2337- This package allows to deform a triangulated surface mesh under 2338 positional constraints of some of its vertices without requiring any 2339 additional structure other than the surface mesh itself. The methods 2340 provided implements an as-rigid-as-possible deformation. Note that 2341 the main class name has changed between the 4.5-beta1 and the 4.5 2342 releases to better match the CGAL naming conventions (from 2343 `CGAL::Deform_mesh` to `CGAL::Surface_mesh_deformation`). 2344 2345### CGAL and the Boost Graph Library (major changes) 2346 2347- Cleanup of the `HalfedgeGraph` concept. In particular: 2348 - Introduction of the notion of `halfedge_descriptor` in the 2349 specialization of the class `boost::graph_traits`. 2350 - Deprecation of `halfedge_graph_traits`. 2351 - A model of `HalfedgeGraph` is considered as an undirected graph. 2352 Thus any call to `edges()` should be replaced by `halfedges()` 2353 and `num_edges()` now returns the number of (undirected) edges. 2354 - **Breaking change:** `is_border_edge` and `is_border_halfedge` 2355 properties are removed. The free functions `is_border()` and 2356 `is_border_edge()` should be used instead. 2357 - Renaming of `HalfedgeGraph` specific free functions. 2358- Introduction of the `FaceGraph` concept. 2359- Adaptation of the package *Triangulated Surface Mesh Simplification* 2360 and of the class `AABB_halfedge_graph_segment_primitive` from the 2361 package *3D Fast Intersection and Distance Computation* to the API 2362 change. 2363- Update of the package *Triangulated Surface Mesh Segmentation* and 2364 of the class `AABB_face_graph_triangle_primitive` from the package 2365 *3D Fast Intersection and Distance Computation* to accept model of 2366 the newly introduced concepts. 2367- Offer *Euler* operations as free functions for models of the graph 2368 concepts provided by CGAL. 2369- Specialization of `boost::graph_traits` for 2370 `OpenMesh::PolyMesh_ArrayKernelT` as proof of concept. A 2371 `OpenMesh::PolyMesh_ArrayKernelT` becomes a model of the 2372 aforementioned concepts when including 2373 `CGAL/boost/graph/graph_traits_PolyMesh_ArrayKernelT.h`. 2374 2375### dD Geometry Kernel 2376 2377- A new model `Epick_d` of the `Kernel_d` concept is introduced. It 2378 provides better performance through arithmetic filtering and 2379 specializations for fixed dimensions. It may not work with compilers 2380 as old as gcc-4.2, but was tested with gcc-4.4. 2381 2382### 3D Convex Hulls 2383 2384- Clean up the documentation of the concepts 2385 2386### 2D Arrangements 2387 2388- Fixed a bug in removing an unbounded curve (e.g., a ray) from an 2389 arrangement induced by unbounded curves. 2390 2391### 2D Snap Rounding 2392 2393- Replaced use of private `kd_tree` with CGAL's official `Kd_tree` 2394 from `Spatial_searching` package; results in a small performance 2395 gain. Removed the private `kd_tree` package. 2396 2397### 3D Triangulations 2398 2399- Add an experimental parallel version of the Delaunay triangulation 2400 and the regular triangulation algorithms, which allows parallel 2401 insertion and removal of point ranges. 2402- Add caching of circumcenters to `Regular_triangulation_cell_base_3`. 2403 The cache value is computed when `cell->circumcenter()` or 2404 `rt.dual(cell)` functions are called. 2405 2406### 3D Periodic Triangulations 2407 2408- Add a method to locate point with inexact predicates. 2409 2410### 3D Mesh Generation 2411 2412- Add a new constructor for the class `Labeled_mesh_domain_3` which 2413 takes an `Iso_cuboid_3`. 2414- Add a new labeling function wrapper for meshing multi-domain. 2415- The meshing functionality in the Qt demos in `demo/Polyhedron/` and 2416 `demo/Mesh_3/` can now use the handling of 1d-features, that exists 2417 in CGAL since version 3.8. 2418- Add an experimental parallel version of the 3D mesh refinement and 2419 mesh optimization methods. 2420 2421### Point Set Processing and Surface Reconstruction from Point Sets 2422 2423- The former demo has been removed and is fully merge in the 2424 Polyhedron demo. 2425 2426### Point Set Processing 2427 2428- Workaround a bug in dijsktra shortest path of boost 1.54 by shipping 2429 and using the boost header from the 1.55 release. This header will 2430 be used only if you are using the version 1.54 of boost. 2431 2432### Triangulated Surface Mesh Simplification 2433 2434- **Breaking change:** Due to the cleanup of the concepts of the 2435 package *CGAL and the Boost Graph Library*, the named parameter 2436 `edge_is_border_map` has been removed, and the named parameter 2437 `edge_is_constrained_map` now expects a property map with an edge 2438 descriptor as key type (vs. halfedge descriptor before). 2439- Add some optimization in the code making the implementation faster 2440 (depending on the cost and the placement chosen). However, for an 2441 edge which collapse is not topologically valid, the vector of 2442 vertices of the link provided by its profile might contains 2443 duplicates, thus also breaking the orientation guarantee in the 2444 vector. This must not be a problem for users as the edge is not 2445 collapsible anyway but if it is a absolute requirement for user 2446 defined cost/placement, defining the macro 2447 `CGAL_SMS_EDGE_PROFILE_ALWAYS_NEED_UNIQUE_VERTEX_IN_LINK` will 2448 restore the former behavior. 2449 2450### dD Spatial Searching 2451 2452- Added methods `reserve(size_t size)` and `size_t capacity()` 2453 to class `Kd_tree` to allocate memory to store `size` points and to 2454 report that number (STL compliance). 2455 2456### STL Extensions for CGAL 2457 2458- Add `Compact_container::operator[]`, allowing a direct access to the 2459 ith element of a compact container. 2460- Add `Concurrent_compact_container`, a compact container which allows 2461 concurrent insertion and removal. 2462 2463Release 4.4 2464----------- 2465 2466Release date: April 2014 2467 2468### Installation 2469 2470- Additional supported platforms: 2471 - The Apple Clang compiler version 5.0 is now supported on 2472 OS X Mavericks. 2473 - The Microsoft Windows Visual C++ compiler 2013 (VC12) is now 2474 supported. 2475 2476### Triangulated Surface Mesh Segmentation (new package) 2477 2478- This package implements the segmentation of triangulated surface 2479 meshes based on the Shape Diameter Function (SDF). In addition, it 2480 also provides functions to generate segmentations based on a user 2481 defined alternative to the SDF. 2482 2483### Number Types 2484 2485- A new class `CGAL::Mpzf` is introduced on some platforms for exact 2486 ring operations. It is used to improve the speed of the evaluation 2487 of predicates in degenerate situations. 2488 2489### 2D and 3D Geometry Kernel 2490 2491- Fix a bug introduced in CGAL 4.3 when computing the intersection of 2492 two 3D triangles. 2493 2494### 2D Polygon Partitioning 2495 2496- Bug fix to make the partition algorithms working with a Lazy kernel 2497 such as `Exact_predicates_exact_constructions_kernel`. 2498 2499### 2D Regularized Boolean Set-Operations 2500 2501- Fix two memory leaks in `CGAL::General_polygon_set_2`. 2502 2503### Combinatorial Maps and Linear Cell Complex 2504 2505- `null_dart_handle` is no longer a static data member in the 2506 `CombinatorialMap` concept. This implies to move the following 2507 methods of `Dart` concept into `CombinatorialMap` concept: 2508 `is_free`, `highest_nonfree_dimension`, `opposite` and 2509 `other_extremity`. We also transform the static methods 2510 `vertex_attribute` and `point` of `Linear_cell_complex` class into 2511 non static methods. You can define the CGAL\_CMAP\_DEPRECATED macro 2512 to keep the old behavior. 2513 2514### 2D Arrangements 2515 2516- Revise the API of **polylines**. In particular, *construction* is 2517 now done using functors and *iteration* is possible only on the 2518 segments of a polyline. 2519- Fix a bug in the *Landmark* point-location strategy. 2520 2521### 2D Snap Rounding 2522 2523- Fix a memory leak 2524 2525### 2D Triangulations 2526 2527- Add different overloads of the function `insert_constraints` that 2528 inserts a range of points and segments, or a range of segments. 2529 These functions uses the spatial sorting in order to speed up the 2530 time needed for the insertion. 2531 2532### 3D Alpha Shapes 2533 2534- Add member functions in `CGAL::Alpha_shape_3` to give access to the 2535 alpha status of edges and facets (`get_alpha_status())`. 2536- Add another filtration method (`filtration_with_alpha_values()`) 2537 that reports the alpha value at which each face appears in the 2538 filtration. 2539 2540### 3D Mesh Generation 2541 2542- Fix the access to functions `number_of_facets` and `number_of_cells` 2543 in `Mesh_complex_3_in_triangulation_3`. 2544- Change the internal API of the sliver perturber, to make possible 2545 for developers to optimize another criterion than the (default) 2546 minimal dihedral angle. Developers can also define a new 2547 perturbation vector (for angles we had gradient of squared 2548 circumradius, gradient of volume, gradient of minimal dihedral 2549 angle, and random) which is better suitable to optimize their 2550 criterion. 2551- Improve the use of cache values in `Mesh_cell_base_3` to (re)compute 2552 circumcenters and sliver criterion values only when needed. 2553 2554### Triangulated Surface Mesh Simplification 2555 2556- Fix a bug in the way edges can be marked as non-removable by adding 2557 a named-parameter `edge_is_constrained_map` to the function 2558 `edge_collapse` 2559 2560### dD Spatial Searching 2561 2562- Fix a documentation bug: The property map passed as template 2563 parameter to the classes `Search_traits_adapter` and 2564 `Distance_adapter` must be a lvalue property map. To avoid incorrect 2565 usage, a static assertion has been added in the CGAL code to prevent 2566 the user from instantiating these classes with an incorrect property 2567 map type. 2568 2569### CGAL ipelets 2570 2571- Better description of the demo ipelets in the user manual 2572- New ipelet for pencils of circles 2573- New ipelet for hyperbolic geometry in Poincaré model 2574- The generator ipelet now generates point in a selected zone 2575- Hilbert sort ipelet implements two policies 2576 2577Release 4.3 2578----------- 2579 2580Release date: October 2013 2581 2582### The CGAL Manual 2583 2584- The documentation of CGAL is now generated with Doxygen. 2585 2586### 2D Periodic Triangulations (new package) 2587 2588- This package allows to build and handle triangulations of point sets 2589 in the two dimensional flat torus. Triangulations are built 2590 incrementally and can be modified by insertion or removal of 2591 vertices. They offer point location facilities. The package provides 2592 Delaunay triangulations and offers nearest neighbor queries and 2593 primitives to build the dual Voronoi diagrams. 2594 2595### API Changes 2596 2597#### 2D and 3D Geometry Kernel 2598 2599- The intersection functions and functors used to return a 2600 `CGAL::Object` in order to deal with the different possible return 2601 types. However, depending on the arguments it is possible to reduce 2602 the possible return types to a small set. For this reason and to 2603 take advantage of the type safety, we decided to use 2604 `boost::variant` instead of `CGAL::Object`. The `result_of` protocol 2605 is now even more useful to determine the return type of the 2606 intersection functions and functors. The change should be relatively 2607 transparent to the user thanks to the implicit constructor added to 2608 `CGAL::Object`. However, it is recommended to upgrade your code. The 2609 previous behavior can be restored by defining the macro 2610 `CGAL_INTERSECTION_VERSION` to 1. 2611 2612#### 2D Arrangements 2613 2614- The type of the result of point location queries changed to 2615 `boost::variant` (from `CGAL::Object`). For convenience, the 2616 previous behavior can be restored by defining the macro 2617 `CGAL_ARR_POINT_LOCATION_VERSION` to 1. 2618- Introduced an optimization for operations on large and dense 2619 arrangements. 2620 2621#### 3D Fast Intersection and Distance Computation 2622 2623- Following the intersection API change, `Object_and_primitive_id` has 2624 been replaced by a template class 2625 `Intersection_and_primitive_id<Query>` to determine the type 2626 depending on the query object type. 2627 2628#### CGAL and Boost Property Maps 2629 2630- The `key_type` of the property maps provided by CGAL used to be an 2631 iterator. In order to be more easily re-used, the `key_type` has 2632 been changed to be the `value_type` of the iterator. The packages 2633 that have been updated to match these changes are **Point Set 2634 Processing** and **Surface Reconstruction from Point Sets**. 2635 However, for most users this change should be transparent if the 2636 default property maps were used. For convenience, the former 2637 behavior can be enabled by defining the macro 2638 `CGAL_USE_PROPERTY_MAPS_API_V1`. 2639 2640### Algebraic Foundations 2641 2642- For convenience, add an overload of `make_rational()` taking a pair 2643 of numbers. 2644 2645### 2D and 3D Geometry Kernel 2646 2647- A `Iso_rectangle_2` can now be constructed from a `Bbox_2` and an 2648 `Iso_cuboid_3` from a `Bbox_3`. 2649- The implementation of `CGAL::Object` has been updated and now uses 2650 `boost::shared_ptr` and `boost::any`. This implementation is faster. 2651- Add to `Bbox_2` and `Bbox_3` a `+=` operator as well as free 2652 functions to get the bounding box of a range of geometric objects. 2653 2654### Combinatorial Maps 2655 2656- Two bug fixes: do not use the 2 least significant bits for cell 2657 attribute without dart support; share the mark when copying a 2658 CMap\_cell\_iterator. 2659- Add a constructor taking a given combinatorial map as argument, 2660 possibly with different dimension and/or different attributes. This 2661 allows to transform a combinatorial map. 2662- Add operator= and swap method. 2663- Add dynamic onmerge/onsplit functions that can be associated 2664 dynamically to i-attributes and which are automatically called when 2665 i-cells are split/merged. 2666- Add a function allowing to reverse the orientation of a 2667 combinatorial map, and another one to reverse one connected 2668 component of a combinatorial map. 2669 2670### 3D Boolean Operations on Nef Polyhedra 2671 2672- Bug-fix in IO when using `Lazy_exact_nt` as number type or 2673 `Exact_predicates_exact_constructions_kernel` as kernel. 2674 2675### 2D Triangulations 2676 2677- Extend the concept `TriangulationDataStructure_2` to require a more 2678 general `copy_tds` function that allows a copy between TDS of 2679 different types. The CGAL model has been updated. 2680- Add a way to efficiently insert a range of points with information 2681 into the 2D constrained Delaunay triangulations. 2682 2683### 3D Triangulations 2684 2685- Extend the concept `TriangulationDataStructure_3` to require a more 2686 general `copy_tds` function that allows a copy between TDS of 2687 different types. The CGAL model has been updated. 2688- Add an advanced function to set the infinite vertex of the 2689 triangulation for low level operations 2690- Fix a bug in the function inserting a range of points with info when 2691 the `Fast_location` tag is used 2692 2693### 2D Segment Delaunay Graph 2694 2695- Add functions `insert_points` and `insert_segments` to insert a 2696 range of points and segments. These functions uses the spatial 2697 sorting in order to speed up the time needed for the insertion. The 2698 function 2699 `insert(Input_iterator first, Input_iterator beyond, Tag_true)` 2700 has been updated to dispatch the input when possible to these 2701 functions. 2702 2703### 2D Apollonius Graphs 2704 2705- Modified insertion algorithm so that the code can handle 2706 pseudo-circles as well. 2707- Updated implementation of the vertex conflict predicate by a faster 2708 version. 2709 2710### 3D Mesh Generation 2711 2712- Speed-up `Mesh_3` and in particular the global optimizers (Lloyd and 2713 ODT) by introducing a parameter `do_freeze` to prevent from moving 2714 vertices which would move of very small displacements. 2715- Introduce new data structures and options for speed-up and 2716 compacity. Note that `Compact_mesh_cell_base_3` and 2717 `Mesh_vertex_base_3` are now our favoured implementations of the 2718 concepts MeshCellBase\_3 and MeshVertexBase\_3. 2719- Introduce a new constructor for `Polyhedral_mesh_domain_3` that 2720 takes a bounding polyhedron to be meshed along with a polyhedral 2721 surface entirely included in it. This allows the user to mesh a 2722 polyhedral domain with internal surface(s) which can be 2723 non-watertight and even non-manifold. 2724- Several documentation bug fixes. 2725- Provide the ability to plug in custom cell\_base/vertex\_base 2726 classes into the Mesh\_triangulation\_3 class. 2727 2728### Triangulated Surface Mesh Simplification 2729 2730- Fix a segmentation fault that was happening when some edges of 2731 length 0 were in the input mesh. 2732 2733### 3D Fast Intersection and Distance Computation 2734 2735- Following the intersection API change, `Object_and_primitive_id` has 2736 been replaced by a template class 2737 `Intersection_and_primitive_id<Query>` to determine the type 2738 depending on the query object type. 2739- Introduce the class `AABB_halfedge_graph_segment_primitive`, which 2740 replaces the class `AABB_polyhedron_segment_primitive` (which is now 2741 deprecated). The new class is more general and can be used with any 2742 model of `HalfedgeGraph`. 2743- Introduce the class `AABB_face_graph_triangle_primitive` which 2744 replaces the class `AABB_polyhedron_triangle_primitive` (which is 2745 now deprecated). 2746- Document the classes `AABB_segment_primitive` and 2747 `AABB_triangle_primitive` that were already used in some examples. 2748- Add a generic primitive class `AABB_primitive` that allows to define 2749 a primitive type by defining only two property maps. 2750- Introduce a new concept of primitive `AABBPrimitiveWithSharedData`. 2751 It allows to have some data shared between the primitives stored in 2752 a `AABB_tree`. With this you can, for example have a primitive 2753 wrapping an integer which refers to the position of a geometric 2754 object in a `std::vector`. Only one reference to this vector will be 2755 stored in the traits of the tree. The concept `AABBTraits`, its 2756 model `AABB_traits` and the class `AABB_tree` have been updated 2757 accordingly. However, everything is backward compatible. 2758- Fix a memory leak in the destructor of the class `AABB-tree` 2759 2760### STL Extensions for CGAL 2761 2762- Add to `Dispatch_output_iterator` and 2763 `Dispatch_or_drop_output_iterator` an operator to accept and 2764 dispatch a tuple of values. 2765 2766### Concurrency in CGAL 2767 2768- Add a `FindTBB` CMake module so that one can easily link with TBB to 2769 write shared-memory parallel code. 2770- Introduce two new tags: Sequential\_tag and Parallel\_tag 2771 2772Release 4.2 2773----------- 2774 2775Release date: March 2013 2776 2777### Installation 2778 2779- Additional supported platforms: 2780 - The Microsoft Windows Visual C++ compiler 2012 (VC11) is now 2781 supported. 2782- With Microsoft Visual C++ (all supported versions), the compiler 2783 flags `/bigobj` and `/wd4503` are added by CGAL CMake scripts. 2784- This is the last release whose "`UseCGAL.cmake`" file (if using CGAL 2785 in a CMake build environment) contains the line 2786 2787 link_libraries(${CGAL_LIBRARIES_DIR} ${CGAL_3RD_PARTY_LIBRARIES_DIRS}) 2788 2789 as this is a deprecated CMake command. The correct way to link with 2790 CGAL's libraries (as for required 3rd party libraries) is to use 2791 '`target_link_libraries`' which specifies for each build target 2792 which libraries should be linked. The following serves as example: 2793 2794 find_package(CGAL) 2795 include(${CGAL_USE_FILE}) 2796 add_executable(myexe main.cpp) 2797 target_link_libraries(myexe ${CGAL_LIBRARIES} 2798 ${CGAL_3RD_PARTY_LIBRARIES}) 2799 2800 We also expect further changes in CGAL's CMake setup (change of 2801 variable names, consistency of filename and output, removing 2802 essential libraries, building executables, removal of 2803 '`${CGAL_3RD_PARTY_LIBRARIES}`'). 2804 2805### 2D Arrangements 2806 2807- Enhanced the 2D-arrangements demonstration program and ported it to 2808 Qt4. The new demonstration program makes use of the CGAL Graphics 2809 View framework, in which the 2D primitives are individually 2810 represented as objects in a scene. (The implementations of several 2811 demos in CGAL already make use of this framework.) This project was 2812 carried out as part of the 2012 Google Summer of Code program. 2813- Fixed a bug in the Walk-Along-A-Line point location strategy for 2814 arrangements induced by unbounded curves. 2815 2816### 2D Circular Geometry Kernel 2817 2818- Fix the intersection type computed when intersecting two identical 2819 circles. 2820- Forward correctly the result type of the linear kernel functors 2821 2822### 2D Triangulations 2823 2824- Add mechanism to avoid call stack overflow in 2825 `Delaunay_triangulation_2` and 2826 `Constrained_Delaunay_triangulation_2`. 2827- Add a constructor for `Regular_triangulation_2` and 2828 `Delaunay_triangulation_2` from a range of points or a range of 2829 points with info. 2830 2831### 2D Voronoi Diagram Adaptor 2832 2833- Bug-fix: Add ccb() method in face type as documented. 2834 2835### 3D Minkowski Sum of Polyhedra 2836 2837- Fix a memory leak. 2838 2839### 3D Fast Intersection and Distance Computation 2840 2841- Update requirements of the concepts `AABBTraits` and 2842 `AABBGeomTraits` to match the implementation of the package. 2843 2844### Generator 2845 2846- Addition of the `Combination_enumerator` 2847 2848### STL Extensions 2849 2850- Introduction of `CGAL::cpp11::result_of` as an alias to the tr1 2851 implementation from boost of the `result_of` mechanism. When all 2852 compilers supported by CGAL will have a Standard compliant 2853 implemention of the C++11 `decltype` feature, it will become an 2854 alias to `std::result_of`. 2855 2856### Surface Reconstruction from Point Sets 2857 2858- Performance improvements and addition of an option to better 2859 reconstruct undersampled zones. The poisson reconstruction plugin of 2860 the Polyhedron demo has an option to switch it on. 2861 2862Release 4.1 2863----------- 2864 2865Release date: October 2012 2866 2867### Installation 2868 2869- Additional supported platforms: 2870 - The Apple Clang compiler versions 3.1 and 3.2 are now supported 2871 on Mac OS X. 2872- Improved configuration for essential and optional external third 2873 party software 2874- Added more general script to create CMakeLists.txt files: 2875 `cgal_create_CMakeLists` 2876- Availability tests for C++11 features are now performed with the 2877 help of [Boost.Config](http://www.boost.org/libs/config). A Boost 2878 version of 1.40.0 or higher is needed to use C++11 features. 2879 2880### 2D Arrangement 2881 2882- Improved the implementation of the incremental randomized 2883 trapezoidal decomposition point-location strategy. The new 2884 implementation enables point location in unbounded arrangements. It 2885 constructs a search structure of guaranteed linear size with 2886 guaranteed logarithmic query time. 2887 2888### 2D Convex Hulls and Extreme Points 2889 2890- Speed up the preprocessing stage of the Akl-Toussaint implementation 2891 (used by the free function `convex_hull_2` when forward iterators 2892 are provided as input). 2893 2894### Combinatorial Maps 2895 2896- Minor bugfix; replace some functors by methods. 2897 2898### Linear Cell Complex 2899 2900- Improve the demo: add a widget showing all the volumes and an 2901 operation to create a Menger sponge. 2902 2903### Kernels 2904 2905- All Kernel functors now support the result\_of protocol. 2906 2907### STL\_Extensions for CGAL 2908 2909- The namespace `cpp0x` has been renamed `cpp11`. The old name is 2910 still available for backward compatibility. 2911 2912Release 4.0.2 2913------------- 2914 2915Release date: Jul 2012 2916 2917This is a bug fix release. It fixes a bug in the `CMakeLists.txt` for 2918CGAL-4.0.1, that prevented even building the libraries. 2919 2920Release 4.0.1 2921------------- 2922 2923Release date: Jul 2012 2924 2925This is a bug fix release. Apart various minor fixes in the 2926documentation, the following has been changed since CGAL-4.0: 2927 2928### 2D Voronoi Diagram Adaptor (re-added) 2929 2930- The package *2D Voronoi Diagram Adaptor* was temporarily removed 2931 from the CGAL distribution because of license issues. That package 2932 is now back into CGAL. 2933 2934### 2D and 3D Geometry Kernel 2935 2936- Fix a bug in the `Segment_3-Triangle_3` intersection function in the 2937 case the segment is collinear with a triangle edge. 2938- Fix a bug in the `Projection_traits_.._3` class in the case a 2939 segment was parallel to the x-axis. 2940 2941### Algebraic Kernel 2942 2943- Avoid the linking error "duplicate symbols" when two compilation 2944 units using the algebraic kernel are linked. 2945 2946### 3D Boolean Operations on Nef Polygons Embedded on the Sphere 2947 2948- Fix a memory leak due to the usage of an internal mechanism that has 2949 been replaced by `boost::any`. This also influences the packages 2D 2950 Boolean Operations on Nef Polygons, 3D Boolean Operations on Nef 2951 Polyhedra, Convex Decomposition of Polyhedra, and 3D Minkowski Sum 2952 of Polyhedra. 2953 2954### 2D Arrangement 2955 2956- Fix several memory leaks. 2957 2958### 2D Mesh Generation 2959 2960- Fix a compilation error in the header 2961 `<CGAL/Mesh_2/Do_not_refine_edges.h>` when g++ version 4.7 is used. 2962 2963### Surface Mesh Generation and 3D Mesh Generation 2964 2965- Fix an important bug in the `CGAL_ImageIO` library, that could lead 2966 to wrong result when meshing from a 3D image. 2967- Fix the compilation of the demo in `demo/Surface_mesher`, when Boost 2968 version 1.48 or 1.49 is used. 2969 2970### Surface Mesh Parameterization 2971 2972- Fix a memory leak. 2973- Fix a compatibility issue with Eigen-3.1 of `Eigen_solver_traits`. 2974 This fix also affects the usage of that class in the package 2975 *Surface Reconstruction from Point Sets*. 2976 2977Release 4.0 2978----------- 2979 2980Release date: March 2012 2981 2982CGAL 4.0 offers the following improvements and new functionality : 2983 2984### License Changes 2985 2986The whole CGAL-3.x series was released under a combination of LGPLv2 2987(for the foundations of CGAL), and QPL (for the high-level packages). 2988QPL was the former license of the graphical toolkit Qt, but that license 2989is not supported by any major free software project. Furthermore, the 2990terms of the LGPLv2 license are ambiguous for a library of C++ 2991templates, like CGAL. 2992 2993The CGAL project, driven by the CGAL Editorial Board, has decided to 2994change the license scheme of CGAL. We increased the major number of the 2995CGAL version to '4' in order to reflect this license change. The 2996CGAL-4.x series is released under: 2997 2998- LGPLv3+ (that is LGPL *"either version 3 of the License, or (at your 2999 option) any later version"*), for the foundations of CGAL, instead 3000 of LGPLv2, 3001- GPLv3+ for the high-level packages, instead of QPL. 3002 3003### General 3004 3005- On Windows, CGAL libraries are now built by default as shared 3006 libraries (also called DLL). To run applications that use .dll files 3007 of CGAL, you must either copy the .dll files into the directory of 3008 the application, or add the path of the directory that contains 3009 those .dll files into the PATH environment variable. 3010- On Windows, the CMake scripts of CGAL now search for shared version 3011 of the Boost libraries. You must ensure that the .dll files of Boost 3012 are found by the dynamic linker. You can, for example, add the path 3013 to the Boost .dll files to the PATH environment variable. 3014- On Windows, CMake version 2.8.6 or higher is now required. 3015- Eigen version 3.1 or later is now the recommended third party 3016 library to use in *Planar Parameterization of Triangulated Surface 3017 Meshes*, *Surface Reconstruction from Point Sets*, *Approximation of 3018 Ridges and Umbilics on Triangulated Surface Meshes*, and *Estimation 3019 of Local Differential Properties of Point-Sampled Surfaces* 3020 packages. If you use Eigen you no longer need Taucs, Lapack or Blas 3021 to use those packages (and any other in CGAL). 3022 3023### Linear Cell Complex (new package) 3024 3025- This package implements linear cell complexes, objects in 3026 d-dimension with linear geometry. The combinatorial part of objects 3027 is described by a combinatorial map, representing all the cells of 3028 the object plus the incidence and adjacency relations between cells. 3029 Geometry is added to combinatorial maps simply by associating a 3030 point to each vertex of the map. This data structure can be seen as 3031 the generalization in dD of the `Polyhedron_3`. 3032 3033### 2D Voronoi Diagram Adaptor (temporarily removed) 3034 3035- As the copyright holder of this package has not granted the right to 3036 switch from QPL to GPL, this package is removed from the 3037 distribution. Note that it is "only" an adapter, that is the 3038 functionality of point/segment/disk Voronoi diagram is offered 3039 through the Delaunay triangulation, segment Delaunay graph, and 3040 Apollonius graph. 3041 3042### AABB Tree 3043 3044- Document constness of member functions of the `AABB_tree` class. 3045- The class `AABB_tree` is now guaranteed to be read-only thread-safe. 3046 As usual in CGAL, this small overhead introduced for thread-safety 3047 can be deactivated by defining `CGAL_HAS_NO_THREADS`. 3048 3049### 2D Alpha Shapes 3050 3051- Add an extra template parameter to the class `Alpha_shape_2` that 3052 allows a certified construction using a traits class with exact 3053 predicates and inexact constructions. 3054- An object of type `Alpha_shape_2` can now be constructed from a 3055 triangulation. 3056 3057### 3D Alpha Shapes 3058 3059- Add an extra template parameter to the class `Alpha_shape_3` that 3060 allows a certified construction using a traits class with exact 3061 predicates and inexact constructions. 3062 3063### Geometric Object Generators 3064 3065- `Random_points_in_iso_box_d` (deprecated since 3.8) has been 3066 removed. Use `Random_points_in_cube_d` instead. 3067 3068### Linear and Quadratic Programming Solver 3069 3070- Minor bugfix. 3071 3072### Spatial Searching 3073 3074- The const-correctness of this package have been worked out. The 3075 transition for users should be smooth in general, however adding few 3076 const in user code might be needed in some cases. 3077- The class `Kd_tree` is now guaranteed to be read-only thread-safe. 3078 As usual in CGAL, this small overhead introduced for thread-safety 3079 can be deactivated by defining `CGAL_HAS_NO_THREADS`. 3080- Bug-fix in `Orthogonal_incremental_neighbor_search` and 3081 `Incremental_neighbor_search` classes. Several calls to `begin()` 3082 now allow to make several nearest neighbor search queries 3083 independently. 3084 3085### STL Extension 3086 3087- `CGAL::copy_n` is now deprecated for `CGAL::cpp0x::copy_n` which 3088 uses `std::copy_n`, if available on the platform. 3089- `CGAL::successor` and `CGAL::predecessor` are now deprecated for 3090 `CGAL::cpp0x::next` and `CGAL::cpp0x::prev`. These functions use the 3091 standard versions if available on the platform. Otherwise, 3092 `boost::next` and `boost::prior` are used. 3093 3094### Triangulation\_2 3095 3096- Fix a thread-safety issue in `Delaunay_triangulation_2` remove 3097 functions. As usual in CGAL, the small overhead introduced for 3098 thread-safety can be deactivated by defining `CGAL_HAS_NO_THREADS`. 3099- Add extraction operator for the class `Constrained_triangulation_2` 3100 (and thus to all inheriting classes). 3101 3102Release 3.9 3103----------- 3104 3105Release date: September 2011 3106 3107CGAL 3.9 offers the following improvements and new functionality : 3108 3109### General 3110 3111- The class `Root_of_2` is now deprecated. It is recommended to use 3112 the class `Sqrt_extension` instead. 3113- The class `Sqrt_extension` is now used everywhere in CGAL where an 3114 algebraic number of degree 2 is needed. This change has been done in 3115 the `Root_of_traits` mechanism (indirectly packages 2D Circular 3116 kernel and 3D Spherical kernel) and the packages 2D Segment Delaunay 3117 Graphs and 2D Arrangements. 3118- Various fixes in the manual. 3119 3120### Combinatorial Maps (new package) 3121 3122- This package provides a new combinatorial data structure allowing to 3123 describe any orientable subdivided object whatever its dimension. It 3124 describes all cells of the subdivision and all the incidence and 3125 adjacency relations between these cells. For example it allows to 3126 describe a 3D object subdivided in vertices, edges, faces and 3127 volumes. This data structure can be seen as the generalization in dD 3128 of the halfedge data structure. 3129 3130### 3D Convex Hull (major performance improvement) 3131 3132- The quickhull implementation of CGAL (`CGAL::convex_hull_3`) has 3133 been worked out to provide very better performances. 3134- The function `CGAL::convex_hull_3` no longer computes the plane 3135 equations of the facets of the output polyhedron. However an example 3136 is provided to show how to compute them easily. 3137- A global function `convex_hull_3_to_polyhedron_3` is now provided to 3138 extract the convex hull of a 3D points set from a triangulation of 3139 these points. 3140 3141### dD Spatial Searching (major new feature added) 3142 3143- A traits-class and distance adapter that together with a point 3144 property map, allow to make nearest neighbor queries on keys instead 3145 of points have been added. 3146- Few bug fixes in the documentation have revealed some 3147 inconsistencies that have been corrected. Two traits class concept 3148 are now documented (`RangeSearchTraits` and `SearchTraits`). Most 3149 other changes concerns only classes documented as advanced. One 3150 issue that user can encounter is due to an additional requirement on 3151 the nested class `Construct_cartesian_const_iterator_d` defined in 3152 the concept SearchTraits that must provide a nested type 3153 `result_type`. 3154 3155### Spatial Sorting (major new feature added) 3156 3157- General dimension is now supported. 3158- Hilbert sorting admits now two policies: splitting at median or at 3159 middle (see user manual). 3160- Using a property map, sorting on keys instead of points is now 3161 easier 3162 3163### dD Kernel 3164 3165- The d-dimensional kernel concept and models have been modified to 3166 additionally provide two new functors `Less_coordinate_d` and 3167 `Point_dimension_d`. 3168 3169### 2D Arrangements 3170 3171- A new geometry-traits class that handles rational arcs, namely 3172 `Arr_rational_function_traits_2`, has been introduced. It replaced 3173 an old traits class, which handled the same family of curves, but it 3174 was less efficient. The new traits exploits CGAL algebraic kernels 3175 and polynomials, which were not available at the time the old traits 3176 class was developed. 3177- A new geometry traits concept called 3178 `ArrangementOpenBoundaryTraits_2` has been introduced. A model of 3179 this concept supports curves that approach the open boundary of an 3180 iso-rectangular area called parameter space, which can be unbounded 3181 or bounded. The general code of the package, however, supports only 3182 the unbounded parameter space. We intend to enhance the general code 3183 to support also bounded parameter spaces in a future release. 3184- The deprecated member function `is_at_infinity()` of 3185 `Arrangement_2::Vertex` has been removed. It has been previously 3186 replaced new function `is_at_open_boundary()`. 3187- The tags in the geometry traits that indicate the type of boundary 3188 of the embedding surface were replaced by the following new tags: 3189 3190 Left_side_category 3191 Bottom_side_category 3192 Top_side_category 3193 Right_side_category 3194 3195 It is still possible not to indicate the tags at all. Default values 3196 are assumed. This however will produce warning messages, and should 3197 be avoided. 3198 3199Release 3.8 3200----------- 3201 3202Release date: April 2011 3203 3204CGAL 3.8 offers the following improvements and new functionality : 3205 3206### General 3207 3208- Boost version 1.39 at least is now required. 3209- Initial support for the LLVM Clang compiler (prereleases of version 3210 2.9). 3211- Full support for the options -strict-ansi of the Intel Compiler 11, 3212 and -ansi of the GNU g++ compiler. 3213- Adding a concept of ranges. In the following releases, it will be 3214 the way to provide a set of objects (vs. a couple of iterators). 3215- Fix a memory leak in CORE polynomials. 3216- Various fixes in the manual. 3217 3218### 3D Mesh Generation (major new feature added) 3219 3220- Adding the possibility to handle sharp features: the 3D Mesh 3221 generation package now offers the possibility to get in the final 3222 mesh an accurate representation of 1-dimensional sharp features 3223 present in the description of the input domain. 3224 3225### 2D Triangulations (major new feature added) 3226 3227- Add a way to efficiently insert a range of points with information 3228 into a 2D Delaunay and regular triangulation. 3229- Add member function mirror\_edge taking an edge as parameter. 3230- Fix an infinite loop in constrained triangulation. 3231 3232### 3D Triangulations (major new feature added) 3233 3234- Add a way to efficiently insert a range of points with information 3235 into a 3D Delaunay and regular triangulation. 3236- Add a member function to remove a cluster of points from a Delaunay 3237 or regular triangulation. 3238- function vertices\_in\_conflict is renamed 3239 vertices\_on\_conflict\_zone\_boundary for Delaunay and regular 3240 triangulation. Function vertices\_inside\_conflict\_zone is added to 3241 regular triangulation. 3242- Structural filtering is now internally used in locate function of 3243 Delaunay and regular triangulation. It improves average construction 3244 time by 20%. 3245- Added demo. 3246 3247### 3D Alpha Shapes (major new feature added) 3248 3249- The new class Fixed\_alpha\_shape\_3 provides a robust and faster 3250 way to compute one alpha shape (with a fixed value of alpha). 3251 3252### AABB tree 3253 3254- Adding the possibility to iteratively add primitives to an existing 3255 tree and to build it only when no further insertion is needed. 3256 3257### 2D and 3D Kernel 3258 3259- Better handling of 2D points with elevation (3D points projected 3260 onto trivial planes). More general traits classes 3261 (Projection\_traits\_xy\_3, 3262 Projection\_traits\_yz\_3,Projection\_traits\_yz\_3) are provided to 3263 work with triangulations, algorithms on polygons, alpha-shapes, 3264 convex hull algorithm... Usage of former equivalent traits classes 3265 in different packages is now deprecated. 3266- Exact\_predicates\_exact\_constructions\_kernel now better use the 3267 static filters which leads to performance improvements. 3268- Add an overload for the global function angle, taking three 3D 3269 points. 3270- In the 2D and 3D kernel concept, the constant Boolean 3271 Has\_filtered\_predicates is now deprecated. It is now required to 3272 use Has\_filtered\_predicates\_tag (being either Tag\_true or 3273 Tag\_false). 3274- Compare\_distance\_2 and Compare\_distance\_3 provide additional 3275 operators for 3 and 4 elements. 3276- Add intersection test and intersection computation capabilities 3277 between an object of type Ray\_3 and either an object of type 3278 Line\_3, Segment\_3 or Ray\_3. 3279- Improve intersection test performance between an object of type 3280 Bbox\_3 and an object of type Plane\_3 or Triangle\_3 by avoiding 3281 arithmetic filter failures. 3282 3283### 2D Envelope 3284 3285- Env\_default\_diagram\_1 is deprecated, Envelope\_diagram\_1 should 3286 be used instead. 3287 3288### 3D Envelope 3289 3290- A new demo program called `L1_Voronoi_diagram_2` has been 3291 introduced. It demonstrates how 2D Voronoi diagrams of points under 3292 the L1 metric are constructed using lower envelopes. 3293 3294### dD Kernel 3295 3296- Add functor Compute\_coordinate\_d to Kernel\_d concept. 3297 3298### Geometric Object Generators 3299 3300- CGAL::Random uses boost::rand48 instead of std::rand. 3301- Adding to CGAL::Random a way to generate random integers. 3302- Adding generators for dD points. 3303 3304### Algebraic Foundations 3305 3306- Algebraic\_structure\_traits now provides an Inverse functor for 3307 Fields. There is also a new global function inverse. 3308 3309### Bounding Volumes 3310 3311- dD Min sphere of spheres has a new traits class for the min sphere 3312 of points. 3313 3314### Triangulated Surface Mesh Simplification 3315 3316- The priority queue internally used to prioritize edge 3317 simplifications is no longer a relaxed heap but a binomial heap. 3318 This fix guarantees that all edges satisfying a simplification 3319 criteria are removed (if possible). 3320 3321### 3D Boolean Operations on Nef Polyhedra 3322 3323- Allow construction of a 3D nef polyhedron from a 3D polyhedron with 3324 normals. 3325 3326### 2D Arrangements 3327 3328- Fix a bug in the method insert\_at\_vertices of the Arrangement\_2 3329 class. 3330- Fix several bugs in the traits class Arr\_Bezier\_curve\_traits\_2 3331 for arrangement of Bezier curves. 3332 3333### 2D Minkowski Sums 3334 3335- A bug in the convolution method was fixed. 3336 3337Release 3.7 3338----------- 3339 3340Release date: October 2010 3341 3342CGAL 3.7 offers the following improvements and new functionality : 3343 3344### General 3345 3346- The configuration of CGAL libraries now requires CMake>=2.6. 3347- Changes in the set of supported platforms: 3348 - GNU g++ 4.5 supported (with or without the compilation option 3349 -std=c++0x). 3350 - Initial support for the option -strict-ansi of the Intel 3351 Compiler 11. The CGAL libraries compile with that option, and 3352 most CGAL headers have been fixed. The packages "3D Boolean 3353 Operations on Nef Polyhedra" (Nef\_3), "Convex Decomposition of 3354 Polyhedra" (Convex\_decomposition\_3), and "3D Minkowski Sum of 3355 Polyhedra" (Minkowski\_sum\_3) are known to still fail to 3356 compile with that compiler flag. 3357 - The Microsoft Windows Visual C++ compiler 2010 (VC10), that was 3358 experimentally supported by CGAL-3.6.1, is now fully supported. 3359 Note that CMake>=2.8.2 is required for that support. 3360 - The Microsoft Windows Visual C++ compiler 2005 (VC8) is no 3361 longer supported by the CGAL project since CGAL-3.7. 3362 - With Microsoft Windows Visual C++ (VC9 and VC10), the optional 3363 dependencies Gmp, Mpfr, Blas, Lapack, Taucs no longer use 3364 Boost-style name mangling. Only one variant is now provided by 3365 the CGAL Windows installer (release, with dynamic runtime). 3366- Some demos now require a version of Qt4 >= 4.3. 3367- CGAL\_PDB is no longer provided with CGAL. An alternative solution 3368 for people interested in reading PDB files is to use ESBTL 3369 (http://esbtl.sourceforge.net/). 3370- Fix issues of the CGAL wrappers around the CORE library, on 64 bits 3371 platforms. 3372 3373### Arithmetic and Algebra 3374 3375- New models Algebraic\_kernel\_d\_1 and Algebraic\_kernel\_d\_2 for 3376 the corresponding concepts. They provide generic support for various 3377 coefficient types 3378 3379### Arrangements 3380 3381- A new model Arr\_algebraic\_segment\_traits\_2 of 3382 ArrangementTraits\_2 that supports algebraic curves of arbitrary 3383 degree in the plane 3384 3385### 2D Triangulations 3386 3387- The Delaunay and regular 2D triangulations now use a symbolic 3388 perturbation to choose a particular triangulation in co-circular 3389 cases. 3390- The return type of the template member function insert(It beg, It 3391 end), taking an iterator range of points, has been changed from int 3392 to std::ptrdiff\_t. 3393- Classes Triangulation\_euclidean\_traits\_xy\_3, 3394 Triangulation\_euclidean\_traits\_yz\_3 and 3395 Triangulation\_euclidean\_traits\_xz\_3 are now model of the concept 3396 ConstrainedTriangulationTraits\_2. They can be used with and without 3397 intersection of constraints. 3398- 2D Delaunay and basic triangulations now provide vertex relocation 3399 by the mean of these two new methods: move and 3400 move\_if\_no\_collision. The methods are also available for the 3401 hierarchy (Triangulation\_hierarchy\_2). 3402 3403### 3D Triangulations 3404 3405- The return type of the template member function insert(It beg, It 3406 end), taking an iterator range of points, has been changed from int 3407 to std::ptrdiff\_t. 3408- 3D Delaunay triangulations now provide vertex relocation by the mean 3409 of these two new methods: move and move\_if\_no\_collision. This 3410 works in both Compact\_policy and Fast\_policy. 3411 3412### 2D and 3D Alpha Shapes 3413 3414- The type int in the API has been changed to std::size\_t so that 3415 CGAL can deal with large data sets (64 bit addresses). 3416 3417### 2D Mesh Generation 3418 3419- The execution of the 2D mesh generator is now deterministic (same at 3420 each run). 3421 3422### 3D Mesh Generation 3423 3424- The efficiency of the 3D mesh generator has been improved (the 3425 number of calls to the oracle per inserted vertex has globally 3426 decrease). This is achieved through a slight change of the mesh 3427 generator strategy which implies that a surface component that is 3428 not detected at the surface mesher level will never be discovered by 3429 chance, owing to the refinement of some tetrahedra, as it could 3430 happen before. Please note that defining the macro 3431 CGAL\_MESH\_3\_USE\_OLD\_SURFACE\_RESTRICTED\_DELAUNAY\_UPDATE 3432 switches back to the old behavior. 3433- A demo program is now available. 3434 3435### Surface Reconstruction from Point Sets 3436 3437- Improved performance and minor bug fix. 3438 3439### 2D Range and Neighbor Search 3440 3441- The type int in the API has been changed to std::size\_t so that 3442 CGAL can deal with large data sets (64 bit addresses). 3443 3444Release 3.6.1 3445------------- 3446 3447Release date: June 2010 3448 3449This is a bug fix release. The following has been changed since 3450CGAL-3.6: 3451 3452### General 3453 3454- Fix compilation errors with recent Boost versions (since 1.40). 3455- Initial support for the Microsoft Visual C++ compiler 10.0 (MSVC 3456 2010). For that support, CMake>=2.8.2 is required. Note also that 3457 the compiler option "/bigobj" is necessary to compile some CGAL 3458 programs with MSVC 2010. 3459 3460### Polynomial 3461 3462- Fix compilation errors with the Microsoft Visual C++ compiler and 3463 the Intel C++ compiler. 3464 3465### Polyhedron 3466 3467- Fix a compilation errors in demo/Polyhedron/: 3468- issue with the location of qglobal.h of Qt4 on MacOS X, 3469- missing texture.cpp, if TAUCS is used, 3470- Fix the location of built plugins of demo/Polyhedron/, when CGAL is 3471 configured with WITH\_demos=ON 3472 3473### 3D Periodic Triangulations 3474 3475- Fixed bug in the triangulation hierarchy for periodic 3476 triangulations. 3477 3478### 2D Mesh Generation 3479 3480- Fix a bug that lead to precondition violation. 3481- Improve the user manual about the member function is\_in\_domain() 3482 of the Face type. 3483- The 2D meshing process is now deterministic (sorting of bad faces no 3484 longer relies on pointers comparisons). 3485 3486### 3D Mesh Generation 3487 3488- Fix a linking errors (duplicate symbols) when 3489 `<CGAL/refine_mesh_3.h>` is included in different compilation units. 3490 3491### Spatial Searching 3492 3493- Fix a bug in `<CGAL/Orthogonal_k_neighbor_search.h>` when several 3494 nearest neighbors are at the same distance from the query point. 3495 3496### IO Streams 3497 3498- Fix a bug in `<CGAL/IO/VRML_2_ostream.h>` that generated VRML 2 3499 files with an invalid syntax for IndexedFaceSet nodes. 3500 3501### Triangulation\_2 3502 3503- Add missing Compare\_distance\_2 functor in trait classes 3504 Triangulation\_euclidean\_traits\_xy\_3 3505 Triangulation\_euclidean\_traits\_yz\_3 and 3506 Triangulation\_euclidean\_traits\_xz\_3. This was preventing calling 3507 member function nearest\_vertex of Delaunay\_triangulation\_2 3508 instantiated with one of these traits. 3509 3510Release 3.6 3511----------- 3512 3513Release date: March 2010 3514 3515CGAL 3.6 offers the following improvements and new functionality : 3516 3517### General 3518 3519- Boost version 1.34.1 at least is now required. 3520 3521### Arithmetic and Algebra 3522 3523#### Algebraic Kernel (new package) 3524 3525- This new package is targeted to provide black-box implementations of 3526 state-of-the-art algorithms to determine, compare and approximate 3527 real roots of univariate polynomials and bivariate polynomial 3528 systems. It includes models of the univariate algebraic kernel 3529 concept, based on the library RS. 3530 3531#### Number Types 3532 3533- Two new arbitrary fixed-precision floating-point number types have 3534 been added: the scalar type Gmpfr and the interval type Gmpfi, based 3535 on the MPFR and MPFI libraries respectively. 3536 3537### Geometry Kernels 3538 3539#### 2D and 3D Geometry Kernel 3540 3541- Add new do\_intersect() and intersection() overloads: 3542 - do\_intersect(Bbox\_3, Bbox\_3/Line\_3/Ray\_3/Segment\_3) 3543 - intersection(Triangle\_3, Line\_3/Ray\_3/Segment\_3) 3544 3545### Polygons 3546 3547#### 2D Regularized Boolean Set-Operations 3548 3549- Fixed General\_polygon\_set\_2::arrangement() to return the proper 3550 type of object. 3551 3552### Arrangement 3553 3554#### 2D Arrangements 3555 3556- Fixed passing a (const) traits object to the constructor of 3557 Arrangement\_2. 3558- Introduced Arrangement\_2::fictitious\_face(), which returns the 3559 fictitious face in case of an unbounded arrangement. 3560- Fixed a bug in Bezier-curve handling. 3561- Added (back) iterator, number\_of\_holes(), holes\_begin(), and 3562 holes\_end() to the default DCEL for backward compatibility. 3563- Added (simple) versions of the free overlay() function. It employs 3564 the default overlay-traits, which practically does nothing. 3565 3566### Polyhedron 3567 3568- Fix a compilation errors in demo/Polyhedron/: 3569 - issue with the location of qglobal.h of Qt4 on MacOS X, 3570 - missing texture.cpp, if TAUCS is used, 3571- Fix the location of built plugins of demo/Polyhedron/, when CGAL is 3572 configured with WITH\_demos=ON 3573- Fix a bug in test\_facet function of the incremental builder: the 3574 function did not test if while a new facet makes a vertex manifold, 3575 no other facet incident to that vertex breaks the manifold property. 3576 3577### Triangulations and Delaunay Triangulations 3578 3579#### 2D/3D Regular Triangulations 3580 3581- Weighted\_point now has a constructor from Cartesian coordinates. 3582 3583#### 3D Triangulations 3584 3585- Regular\_triangulation\_3 : semi-static floating-point filters are 3586 now used in its predicates, which can speed up its construction by a 3587 factor of about 3 when 3588 Exact\_predicates\_inexact\_constructions\_kernel is used. 3589- The class Regular\_triangulation\_filtered\_traits\_3 is deprecated, 3590 the class Regular\_triangulation\_euclidean\_traits\_3 must be used 3591 instead. The predicates of that traits will be filtered if the 3592 kernel given as template parameter of that traits is itself a 3593 filtered kernel. 3594- Triangulation\_hierarchy\_3 is now deprecated, and replaced by a 3595 simpler CGAL::Fast\_location policy template parameter of 3596 Delaunay\_triangulation\_3. 3597- The old version of remove() (enabled with 3598 CGAL\_DELAUNAY\_3\_OLD\_REMOVE) has been deleted. 3599 3600#### 3D Periodic Triangulations 3601 3602- New demo: 3D periodic Lloyd algorithm. 3603- New functionality for Voronoi diagrams: dual of an edge and of a 3604 vertex, volume and centroid of the dual of a vertex. 3605- The package can now be used with the 3D Alpha Shapes package to 3606 compute periodic alpha shapes. 3607 3608#### 3D Alpha shapes 3609 3610- The class Weighted\_alpha\_shape\_euclidean\_traits\_3 is 3611 deprecated, the class Regular\_triangulation\_euclidean\_traits\_3 3612 must be used instead. 3613- The package can now be used together with the 3D Periodic 3614 Triangulation package to compute periodic alpha shapes. 3615 3616#### 2D/3D Triangulations, 2D Segment Delaunay Graph, 2D Apollonius Graph, and 3D Periodic Triangulations 3617 3618- The constructor and insert function taking ranges now produce 3619 structures whose iterator orders is now deterministic (same at each 3620 run). 3621 3622### Mesh Generation 3623 3624#### 2D Mesh Generation 3625 3626- The 2D mesh generator can now be used with a constrained Delaunay 3627 triangulation with constraints hierarchy 3628 (Constrained\_triangulation\_plus\_2). 3629- In some cases (refinement of a constrained edge that is on the 3630 convex hull), the 2D mesh generator from CGAL-3.4 and CGAL-3.5 could 3631 create invalid triangulations. This bug is now fixed. 3632 3633#### 3D Mesh Generation 3634 3635- The mesh generator has been enriched with an optimization phase to 3636 provide 3D meshes with well shaped tetrahedra (and in particular no 3637 slivers). The optimization phase involves four different 3638 optimization processes: two global optimization processes (ODT and 3639 Lloyd), a perturber and an exuder. Each of these processes can be 3640 activated or not, and tuned to the users needs and to available 3641 computer resources. 3642 3643### Support library 3644 3645#### CGAL ipelets 3646 3647- Add support for version 7 of Ipe. 3648 3649Release 3.5.1 3650------------- 3651 3652Release date: December 2009 3653 3654This is a bug fix release. 3655 3656### Documentation 3657 3658- Fixes in the documentation (the online documentation of CGAL-3.5 is 3659 now based on CGAL-3.5.1). 3660- Fixes to the bibliographic references. 3661 3662### Windows installer 3663 3664- The Windows installer of CGAL-3.5.1 fixes an issue with downloading 3665 of precompiled binaries of the external library TAUCS. 3666 3667### Bug fixes in the following CGAL packages 3668 3669#### AABB tree 3670 3671- Fix a linker issue in do\_intersect(Bbox\_3,Bbox\_3). 3672- Fix compilation issue in do\_intersect(Bbox\_3,Ray\_3) when using 3673 the parameters in this order. 3674 3675#### 3D Mesh Generation 3676 3677- Fix a bug in initial points construction of a polyhedral surface. 3678 3679Release 3.5 3680----------- 3681 3682Release date: October 2009 3683 3684CGAL releases will now be published about every six months. As a 3685transition release, CGAL-3.5 has been developed during 9 months from the 3686release CGAL-3.4. 3687 3688Version 3.5 differs from version 3.4 in the platforms that are supported 3689and in functionality. There have also been a number of bug fixes for 3690this release. 3691 3692### General 3693 3694- Additional supported platforms: 3695 - GNU g++ 4.4 supported. 3696 - Intel Compiler 11 supported on Linux 3697- Fixed ABI incompatibilities when mixing CGAL and Boost Program 3698 Options on Windows/Visual C++ (the compilation flag 3699 -D\_SECURE\_SCL=0 is not longer use in Debug mode). 3700 3701### Geometry Kernels 3702 3703#### 3D Spherical Geometry Kernel 3704 3705- Add functionalities to manipulate circles, circular arcs and points 3706 that belong to the same sphere. 3707 3708### Polygons 3709 3710#### 2D Regularized Boolean Set-Operations 3711 3712- The polygon validation operations were enhanced and their interface 3713 was improved. They are now offered as free functions and applied 3714 properly. 3715 3716#### 2D Straight Skeleton and Polygon Offsetting 3717 3718- Updated the manual to document the new partial skeletons feature 3719 (already in the code since 3.4) 3720 3721### Arrangements 3722 3723#### 2D Arrangements 3724 3725- The member function is\_at\_infinity() of Arrangement\_2::Vertex was 3726 replaced by the new function is\_at\_open\_boundary(). The former is 3727 deprecated. While still supported in version 3.5, It will not be 3728 supported in future releases. The member functions 3729 boundary\_type\_in\_x() and boundary\_type\_in\_y() were permanently 3730 replaced by the functions parameter\_space\_in\_x() and 3731 parameter\_space\_in\_y(), respectively. The 2 new functions return 3732 an enumeration of a new type, namely Arr\_parameter\_space. 3733- The tags in the geometry traits that indicate the type of boundary 3734 of the embedding surface were replaced by the following new tags: 3735 Arr\_left\_side\_tag Arr\_bottom\_side\_tag Arr\_top\_side\_tag 3736 Arr\_right\_side\_tag In addition, the code was change, and now it 3737 is possible not to indicate the tags at all. Default values are 3738 assumed. This however will produce warning messages, and should be 3739 avoided. 3740- All operations of the geometry traits-class were made 'const'. This 3741 change was reflected in the code of this package and all other 3742 packages that are based on it. Traits classes that maintain state, 3743 should declare the data members that store the state as mutable. 3744 3745#### Envelopes of Surfaces in 3D 3746 3747- A few bugs in the code that computes envelopes were fixed, in 3748 particular in the code that computes the envelopes of planes. 3749 3750### Triangulations and Delaunay Triangulations 3751 3752#### 3D Periodic Triangulations (new package) 3753 3754- This package allows to build and handle triangulations of point sets 3755 in the three dimensional flat torus. Triangulations are built 3756 incrementally and can be modified by insertion or removal of 3757 vertices. They offer point location facilities. 3758 3759### Mesh Generation 3760 3761#### Surface Reconstruction from Point Sets (new package) 3762 3763- This CGAL package implements an implicit surface reconstruction 3764 method: Poisson Surface Reconstruction. The input is an unorganized 3765 point set with oriented normals. 3766 3767#### 3D Mesh Generation (new package) 3768 3769- This package generates 3 dimensional meshes. It computes isotropic 3770 simplicial meshes for domains or multidomains provided that a domain 3771 descriptor, able to answer queries from a few different types on the 3772 domain, is given. In the current version, Mesh\_3 generate meshes 3773 for domain described through implicit functional, 3D images or 3774 polyhedral boundaries. The output is a 3D mesh of the domain volume 3775 and conformal surface meshes for all the boundary and subdividing 3776 surfaces. 3777 3778### Geometry Processing 3779 3780#### Triangulated Surface Mesh Simplification 3781 3782- BREAKING API change in the passing of the visitor object. 3783- Fixed a bug in the link\_condition test 3784- Added a geometric test to avoid folding of facets 3785- Fixed a bug in the handling of overflow in the LindstromTurk 3786 computations 3787- Updated the manual to account for the new visitor interface 3788 3789#### Point Set Processing (new package) 3790 3791- This packages implements a set of algorithms for analysis, 3792 processing, and normal estimation and orientation of point sets. 3793 3794### Spatial Searching and Sorting 3795 3796#### AABB tree (new package) 3797 3798- This package implements a hierarchy of axis-aligned bounding boxes 3799 (a AABB tree) for efficient intersection and distance computations 3800 between 3D queries and sets of input 3D geometric objects. 3801 3802### Support Library 3803 3804#### CGAL\_ipelets (new package): 3805 3806- Object that eases the writing of Ipe's plugins that use CGAL. 3807 Plugins for CGAL main 2D algorithm are provided as demo. 3808 3809Release 3.4 3810----------- 3811 3812Release date: January 2009 3813 3814Version 3.4 differs from version 3.3.1 in the platforms that are 3815supported and in functionality. There have also been a number of bug 3816fixes for this release. 3817 3818### General 3819 3820- GNU g++ 4.3 supported. Support for g++ 3.3 is dropped. 3821- Visual 9 supported. Support for Visual 7 is dropped. 3822- Boost version 1.33 at least is now required. 3823- CGAL now depends on Boost.Threads, which implies to link against a 3824 compiled part of Boost. 3825- The new macro CGAL\_NO\_DEPRECATED\_CODE can be defined to disable 3826 deprecated code, helping users discover if they rely on code that 3827 may be removed in subsequent releases. 3828- Assertion behaviour: It is not possible anymore to set the CONTINUE 3829 mode for assertion failures. Functions that allow to change the 3830 assertion behaviour are now declared in 3831 `<CGAL/assertions_behaviour.h>`. 3832- Qt3 based demos are still there but the documentation has been 3833 removed as the CGAL::Qt\_Widget will be deprecated. 3834- Qt4 based demos use the Qt GraphicsView framework and the 3835 libQGLViewer. 3836 3837### Installation 3838 3839- install\_cgal has been replaced by CMake. 3840 3841### Polynomial (new package) 3842 3843- This package introduces a concept Polynomial\_d, a concept for 3844 multivariate polynomials in d variables. 3845 3846### Modular Arithmetic (new package) 3847 3848- This package provides arithmetic over finite fields. 3849 3850### Number Types 3851 3852- the counter Interval\_nt::number\_of\_failures() has been removed, 3853 replaced by a profiling counter enabled with CGAL\_PROFILE. 3854- Fix of a bug in CORE/Expr.h; as a consequence, the arrangement demo 3855 works properly when handling arrangements of conics, for example, 3856 when defining an arc with 5 points. 3857 3858### 3D Spherical Geometry Kernel (new package) 3859 3860- This package is an extension of the linear CGAL Kernel. It offers 3861 functionalities on spheres, circles, circular arcs and line segments 3862 in the 3D space. 3863 3864### Linear Kernel 3865 3866- We recommend that you use the object\_cast() function instead of 3867 assign() to extract an object from a CGAL::Object, for efficiency 3868 reasons. 3869- The Kernel archetypes provided by the 2D/3D linear kernel have been 3870 removed. 3871- The deprecated linear kernel functors Construct\_supporting\_line\_2 3872 and Construct\_supporting\_line\_3 have been removed. 3873- Ambiant\_dimension and Feature\_dimenison have been added to 3874 retrieve the potentially compile-time dimension of a space or of an 3875 object. 3876- barycenter() functions have been added. 3877- The geometric object Circle\_3 as well as predicates and 3878 constructions have been added to the kernel 3879- The missing intersection/do\_intersect between Line\_3 and Line\_3 3880 has been added as well. 3881 3882### 3D Triangulations 3883 3884- Removed the deprecated functions Cell:mirror\_index() and 3885 Cell::mirror\_vertex(). 3886- Derecursification of two functions that in some cases lead to stack 3887 overflows 3888 3889### 3D Nef Polyhedron 3890 3891- n-ary union/intersection 3892- intersection with halfspace under standard kernel 3893- constructor for polylines 3894 3895### CGAL and the Qt4 GraphicsView (new package) 3896 3897- 2D CGAL Kernel objects and many data structures have can be rendered 3898 in a QGraphicsView 3899 3900### STL Extensions: 3901 3902- The functor adaptors for argument binding and composition (bind\_\*, 3903 compose, compose\_shared, swap\_\*, negate, along with the helper 3904 functions set\_arity\_\* and Arity class and Arity\_tag typedefs) 3905 which were provided by `<CGAL/functional.h>` have been removed. 3906 Please use the better boost::bind mecanism instead. The concept 3907 AdaptableFunctor has been changed accordingly such that only a 3908 nested result\_type is required. 3909- The accessory classes Twotuple, Threetuple, Fourtuple and Sixtuple 3910 are also deprecated (use CGAL::array instead). 3911- CGAL::Triple and CGAL::Quadruple are in the process of being 3912 replaced by boost::tuple. As a first step, we strongly recommend 3913 that you replace the direct access to the data members (.first, 3914 .second, .third, .fourth), by the get<i>() member function; 3915 and replace the make\_triple and make\_quadruple maker functions by 3916 make\_tuple. 3917 This way, in a further release, we will be able to switch to 3918 boost::tuple more easily. 3919- The class CGAL::Uncertain<> has been documented. It is 3920 typically used to report uncertain results for predicates using 3921 interval arithmetic, and other filtering techniques. 3922 3923### 2D Arrangements 3924 3925- Changed the name of the arrangement package from Arrangement\_2 to 3926 Arrangement\_on\_surface\_2 to reflect the potential capabilities of 3927 the package to construct and maintain arrangements induced by curves 3928 embedded on two dimensional surfaces in three space. Most of these 3929 capabilities will become available only in future releases though. 3930- Enhanced the geometry traits concept to handle arrangements embedded 3931 on surfaces. Each geometry-traits class must now define the 3932 'Boundary\_category' tag. 3933- Fixed a bug in Arr\_polyline\_traits\_2.h, where the operator that 3934 compares two curves failed to evaluate the correct result (true) 3935 when the curves are different, but their graphs are identical. 3936- Permanently removed IO/Arr\_postscript\_file\_stream.h and 3937 IO/Polyline\_2\_postscript\_file\_stream.h, as they depend on 3938 obsolete features and LEDA. 3939- Fixed several bugs in the arrangement demo and enhanced it. e.g., 3940 fixed background color change, allowed vertex coloring , enabled 3941 "smart" color selection, etc. 3942- Enhanced the arrangement demo with new features, such as allowing 3943 the abortion of the merge function (de-select), updated the how-to 3944 description, etc. 3945- Replace the functions CGAL::insert\_curve(), CGAL::insert\_curves(), 3946 CGAL::insert\_x\_monotone\_curve(), and 3947 CGAL::insert\_x\_monotone\_curves() with a single overloaded 3948 function CGAL::insert(). The former 4 functions are now deprecated, 3949 and may no longer be supported in future releases. 3950 3951### Envelopes of Surfaces in 3D 3952 3953- Fixed a bug in the computation of the envelope of unbounded planes 3954 caused by multiple removals of vertices at infinity. 3955 3956### 2D Regularized Boolean Set-Operations 3957 3958- Fixed a bug in connect\_holes() that caused failures when connecting 3959 holes touching the outer boundary. 3960- Fixed the concept GeneralPolygonSetTraits\_2. Introduced two new 3961 concepts GpsTraitsGeneralPolygon\_2 and 3962 GpsTraitsGeneralPolygonWithHoles\_2. Fixed the definition of the two 3963 nested required types Polygon\_2 and Polygon\_with\_holes\_2 of the 3964 GeneralPolygonSetTraits\_2 concept. They must model now the two new 3965 concepts above. 3966- Added a default template parameter to 'General\_polygon\_set\_2' to 3967 allow users to pass their specialized DCEL used to instantiate the 3968 underlying arrangement. 3969- Enhanced the BOP demo to use multiple windows. 3970 3971### 2D Minkowski Sums 3972 3973- Fixed a few bugs in the approximate offset function, making it 3974 robust to highly degenerate inputs. 3975- Fixed a bug in the exact Minkowski sum computation when processing 3976 degenerate inputs that induce overlapping of contiguous segments in 3977 the convolution cycles. 3978- Optimized the approximate offset function (reduced time consumption 3979 up to a factor of 2 in some cases). 3980- Added functionality to compute the offset (or to approximate the 3981 offset) of a Polygon\_with\_holes\_2 (and not just of a Polygon\_2). 3982- Added the functionality to compute (or to approximate) the inner 3983 offset of a polygon. 3984 3985Release 3.3.1 3986------------- 3987 3988Release date: August 2007 3989 3990This is a bug fix release. 3991 3992### General 3993 3994- Intel C++ 9 was wrongly recognized as unsupported by install\_cgal. 3995- Added autolink (for Visual C++) for the CGALImageIO and CGALPDB 3996 libraries. 3997- Fixed bug in Memory\_sizer when using more than 4GB of memory 3998 (64bit). 3999 4000### Number Types 4001 4002- Fixed bug in FPU rounding mode macros (affected only the alpha 4003 architecture). 4004- Fixed bug in MP\_Float constructor from double for some particular 4005 values. 4006- Fixed bug in to\_double(Lazy\_exact\_nt) sometimes returning NaN. 4007 4008### Kernel 4009 4010- Fixed forgotten derivation in Circular\_kernel\_2::Has\_on\_2 4011- Added some missing functions in Bbox\_3 compared to Bbox\_2. 4012 4013### Skin Surface Meshing 4014 4015- The new Skin Surface Meshing package had been forgotten in the list 4016 of changes and the release announcement of CGAL 3.3: This package 4017 allows to build a triangular mesh of a skin surface. Skin surfaces 4018 are used for modeling large molecules in biological computing. 4019 4020### Arrangements 4021 4022- Fixed a bug in the Arrangement\_2 package in dual arrangement 4023 representation for Boost graphs when reporting all halfedges of a 4024 face. 4025- Fixed a bug in the Arrangement sweep-line when using a specific 4026 polyline configuration. 4027- Fixed bug in Arrangement\_2 in walk along a line point location for 4028 unbounded curves. 4029- Fixed bug in aggregated insertion to Arrangement\_2. 4030- Fixed bug in Arrangment\_2 class when inserting an unbounded curve 4031 from an existing vertex. 4032- Fixed bug when dealing with a degenerate conic arc in 4033 Arr\_conic\_traits\_2 of the Arrangment package, meaning a line 4034 segment which is part of a degenerate parabola/hyperbola. 4035- Fixed bug in the Bezier traits-class: properly handle line segments. 4036 properly handle comparison near a vertical tangency. 4037 4038### 2D Polygon 4039 4040- Fixed bug in degenerate case of Polygon\_2::is\_convex() for equal 4041 points. 4042 4043### 2D Triangulations 4044 4045- Fixed bug in Regular\_triangulation\_2. 4046 4047### 3D Triangulations 4048 4049- Added a circumcenter() function in the default Cell type parameter 4050 Triangulation\_ds\_cell\_base\_3, so that the .dual() member 4051 function of Delaunay still work as before, without requiring the 4052 explicit use of Triangulation\_cell\_base. 4053- Added missing operator->() to Facet\_circulator. 4054 4055### Interpolation 4056 4057- Fixed bug in Interpolation 3D about the normalization coefficient 4058 initialization. 4059 4060### 3D Boolean Operations on Nef Polyhedra 4061 4062- Fixed bug in construction of Nef\_polyhedron\_3 from off-file. Now, 4063 always the inner volume is selected. 4064- Fixed bug in conversion from Nef\_polyhedron\_3 to Polyhedron\_3. 4065 Polyhedron\_3 was not cleared at the beginning. 4066- Fixed bug in Nef\_polyhedron\_3 in update of indexes for 4067 construction of external structure. 4068 4069### Third Party Libraries Shipped with CGAL 4070 4071- TAUCS supports now 64 bits platforms. 4072- CAUTION: Since version 3.3.1, CGAL is no longer compatible with the 4073 official release of TAUCS (currently 2.2). Make sure to use the 4074 version modified by the CGAL project and available from the download 4075 section of https://www.cgal.org. 4076 4077Release 3.3 4078----------- 4079 4080Release date: May 2007 4081 4082Version 3.3 differs from version 3.2.1 in the platforms that are 4083supported and in functionality. There have also been a number of bug 4084fixes for this release. 4085 4086Additional supported platforms 4087 4088- GNU g++ 4.1 and 4.2 4089- Intel C++ compiler 9 4090- Microsoft Visual C++ compiler 8.0 4091 4092The following platforms are no longer supported: 4093 4094- Intel 8 4095 4096CGAL now supports Visual C++ "Checked iterators" as well as the debug 4097mode of GNU g++'s STL (-D\_GLIBCXX\_DEBUG). 4098 4099CGAL now works around the preprocessor macros 'min' and 'max' defined in 4100`<windows.h>` which were clashing with min/max functions. 4101 4102### Installation 4103 4104- On Windows the libraries built in Developer Studio now have names 4105 which encode the compiler version, the runtime and whether it was 4106 built in release or debug mode. The libraries to link against are 4107 chosen with linker pragmas in header files. 4108- On all platforms but Windows shared and static versions of the 4109 libraries are generated 4110 4111### Manuals 4112 4113- The Package Overview page now also hosts the precompiled demos. 4114 4115### Algebraic Foundations 4116 4117- Algebraic Foundations (new package) 4118 This package defines what algebra means for CGAL, in terms of 4119 concepts, classes and functions. The main features are: (i) explicit 4120 concepts for interoperability of types (ii) separation between 4121 algebraic types (not necessarily embeddable into the reals), and 4122 number types (embeddable into the reals). 4123- Number Types 4124 Fixed\_precision\_nt and Filtered\_exact number types have been 4125 removed. 4126 4127### Kernels 4128 4129- 2D Circular Kernel 4130 Efficiency improved through geometric filtering of predicates, 4131 introduced with the filtered kernel 4132 Filtered\_bbox\_circular\_kernel\_2<.>, and also chosen for 4133 the predefined kernel Exact\_circular\_kernel\_2. 4134- Linear Kernel 4135 Exact\_predicates\_exact\_constructions\_kernel memory and run-time 4136 improvements through usage of lazy geometric constructions instead 4137 of lazy arithmetic. 4138 4139### Data Structures and Algorithms 4140 4141- Surface Mesh Simplification (new package) 4142 This package provides a mesh simplification framework using edge 4143 collapse operations, and provides the Turk/Lindstrom simplification 4144 algorithm. 4145- Skin Surface Meshing (new package) 4146 This package allows to build a triangular mesh of a skin surface. 4147 Skin surfaces are used for modeling large molecules in biological 4148 computing. The surface is defined by a set of balls, representing 4149 the atoms of the molecule, and a shrink factor that determines the 4150 size of the smooth patches gluing the balls together. 4151- Estimation of Local Differential Properties (new package) 4152 This package allows to compute local differential quantities of a 4153 surface from a point sample 4154- Approximation of Ridges and Umbilics on Triangulated Surface Meshes 4155 (new package) 4156 This package enables the approximation of differential features on 4157 triangulated surface meshes. Such curvature related features are 4158 lines: ridges or crests, and points: umbilics. 4159- Envelopes of Curves in 2D (new package) 4160 This package contains two sets of functions that construct the lower 4161 and upper envelope diagram for a given range of bounded or unbounded 4162 curves. 4163- Envelopes of Surfaces in 3D (new package) 4164 This package contains two sets of functions that construct the lower 4165 and upper envelope diagram for a given range of bounded or unbounded 4166 surfaces. The envelope diagram is realized as a 2D arrangement. 4167- Minkowski Sums in 2D (new package) 4168 This package contains functions for computing planar Minkowski sums 4169 of two closed polygons, and for a polygon and a disc (an operation 4170 also known as offsetting or dilating a polygon). The package also 4171 contains an efficient approximation algorithm for the offset 4172 computation, which provides a guaranteed approximation bound while 4173 significantly expediting the running times w.r.t. the exact 4174 computation procedure. 4175- Surface Mesh Parametrization 4176 Added Jacobi and SSOR preconditioners to OpenNL solver, which makes 4177 it much faster and more stable. 4178- 2D Arrangements 4179 - Added support for unbounded curves. 4180 - Added a traits class that supports bounded and unbounded linear 4181 objects, namely lines, rays and line segments. 4182 - Added traits classes that handle circular arcs based on the 4183 circular kernel. 4184 - Added a traits class that supports Bezier curves. 4185 - Enhanced the traits class that supports rational functions to 4186 handle unbounded (as well as bounded) arcs 4187 - Added a free function called decompose() that produces the 4188 symbolic vertical decomposition of a given arrangement, 4189 performing a batched vertical ray-shooting query from all 4190 arrangement vertices. 4191 - Fixed a memory leak in the sweep-line code. 4192 - Fixed a bug in computing the minor axis of non-degenerate 4193 hyperbolas. 4194- Boolean Set Operations 4195 - Added the DCEL as a default template parameter to the 4196 General\_polygon\_set\_2 and Polygon\_set\_2 classes. This 4197 allows users to extend the DCEL of the underlying arrangement. 4198 - Added a function template called connect\_holes() that connects 4199 the holes in a given polygon with holes, turning it into a 4200 sequence of points, where the holes are connceted to the outer 4201 boundary using zero-width passages. 4202 - Added a non-const function member to General\_polygon\_set\_2 4203 that obtains the underlying arrangement. 4204- 2D and 3D Triangulations 4205 - The constructors and insert member functions which take an 4206 iterator range perform spatial sorting in order to speed up the 4207 insertion. 4208- Optimal Distances 4209 - Polytope\_distance\_d: has support for homogeneous points; 4210 bugfix in fast exact version. 4211- Bounding Volumes 4212 - Min\_annulus\_d has support for homogeneous points; bugfix in 4213 fast exact version. 4214 4215### Support Library 4216 4217- CGAL and the Boost Graph Library (BGL) (new package) 4218 This package provides the glue layer for several CGAL data 4219 structures such that they become models of the BGL graph concept. 4220- Spatial Sorting (new package) 4221 This package allows to sort points and other objects along a Hilbert 4222 curve which can improve the performance of algorithms like 4223 triangulations. It is used by the constructors of the triangulation 4224 package which have an iterator range of points as argument. 4225- Linear and Quadratic Programming Solver (new package) 4226 This package contains algorithms for minimizing linear and convex 4227 quadratic functions over polyhedral domains, described by linear 4228 equations and inequalities. 4229 4230Release 3.2.1 4231------------- 4232 4233Release date: July 2006 4234 4235This is a bug fix release 4236 4237### Number Types 4238 4239- Fix MP\_Float constructor which crashed for some values. 4240 4241### Kernel 4242 4243- Rename Bool to avoid a clash with a macro in X11 headers. 4244 4245### Arrangement 4246 4247- Derived the Arr\_segment\_traits\_2 Arrangement\_2 traits class from 4248 the parameterized Kernel. This allows the use of this traits class 4249 in an extended range of applications that require kernel objects and 4250 operations on these objects beyond the ones required by the 4251 Arrangement\_2 class itself. 4252- Fixed a compilation bug in the code that handles overlay of 4253 arrangements instantiated with different DCEL classes. 4254- Fixed a couple of bugs in the implementation of the Trapezoidal RIC 4255 point-location strategy 4256 4257### Triangulation, Alpha Shapes 4258 4259- Qualify calls to filter\_iterator with "CGAL::" to avoid overload 4260 ambiguities with Boost's filter\_iterator. 4261 4262### Surface Mesher 4263 4264- Fixed a bug in iterators of the class template 4265 Surface\_mesh\_complex\_2\_in\_triangulation\_3 4266 4267### Surface Mesh Parametrisation 4268 4269- Updated the precompiled taucs lib 4270 4271### Kinetic Data Structures 4272 4273- Fixed problems caused by old versions of gcc being confused by 4274 operator! and operator int() 4275- Added point removal support to the Active\_objects\_vector 4276 4277Release 3.2 4278----------- 4279 4280Release date: May 2006 4281 4282Version 3.2 differs from version 3.1 in the platforms that are supported 4283and in functionality. There have also been a number of bug fixes for 4284this release. 4285 4286The following platforms are no longer supported: 4287 4288- SunPro CC versions 5.4 and 5.5 on Solaris 4289- SGI Mips Pro 4290 4291For Visual C++ the installation scripts choose the multi-threaded 4292dynamically linked runtime (/MD). Before it was the single-threaded 4293static runtime (/ML). 4294 4295### Installation 4296 4297- The install tool tries to find third party libraries at "standard" 4298 locations. 4299- Installers for Apple, Windows, and rpms. 4300 4301### Manuals 4302 4303- User and Reference manual pages of a package are in the same chapter 4304 4305### Kernels 4306 4307- 2D Circular Kernel (new package) 4308 This package is an extension of the linear CGAL Kernel. It offers 4309 functionalities on circles, circular arcs and line segments in the 4310 plane. 4311 4312### Data Structures and Algorithms 4313 4314- 2D Regularized Boolean Set-Operations (new package) 4315 This package consists of the implementation of Boolean 4316 set-operations on point sets bounded by weakly x-monotone curves in 4317 2-dimensional Euclidean space. In particular, it contains the 4318 implementation of regularized Boolean set-operations, intersection 4319 predicates, and point containment predicates. 4320- 2D Straight Skeleton and Polygon Offsetting (new package) 4321 This package implements an algorithm to construct a halfedge data 4322 structure representing the straight skeleton in the interior of 2D 4323 polygons with holes and an algorithm to construct inward offset 4324 polygons at any offset distance given a straight skeleton. 4325- 2D Voronoi Diagram Adaptor (new package) 4326 This package provides an adaptor that adapts a 2-dimensional 4327 triangulated Delaunay graph to the corresponding Voronoi diagram, 4328 represented as a doubly connected edge list (DCEL) data structure. 4329 The adaptor has the ability to automatically eliminate, in a 4330 consistent manner, degenerate features of the Voronoi diagram, that 4331 are artifacts of the requirement that Delaunay graphs should be 4332 triangulated even in degenerate configurations. Depending on the 4333 type of operations that the underlying Delaunay graph supports, the 4334 adaptor allows for the incremental or dynamic construction of 4335 Voronoi diagrams and can support point location queries. 4336- 3D Surface Mesher (new package) 4337 This package provides functions to generate surface meshes that 4338 interpolate smooth surfaces. The meshing algorithm is based on 4339 Delaunay refinement and provides some guarantees on the resulting 4340 mesh: the user is able to control the size and shape of the mesh 4341 elements and the accuracy of the surface approximation. There is no 4342 restriction on the topology and number of components of input 4343 surfaces. The surface mesher may also be used for non smooth 4344 surfaces but without guarantee. 4345 4346 Currently, implementations are provided for implicit surfaces 4347 described as the zero level set of some function and surfaces 4348 described as a gray level set in a three-dimensional image. 4349 4350- 3D Surface Subdivision Methods (new package) 4351 Subdivision methods recursively refine a control mesh and generate 4352 points approximating the limit surface. This package consists of 4353 four popular subdivision methods and their refinement hosts. 4354 Supported subdivision methods include Catmull-Clark, Loop, Doo-Sabin 4355 and sqrt(3) subdivisions. Their respective refinement hosts are PQQ, 4356 PTQ, DQQ and sqrt(3) refinements. Variations of those methods can be 4357 easily extended by substituting the geometry computation of the 4358 refinement host. 4359- Planar Parameterization of Triangulated Surface Meshes (new 4360 package) 4361 Parameterizing a surface amounts to finding a one-to-one mapping 4362 from a suitable domain to the surface. In this package, we focus on 4363 triangulated surfaces that are homeomorphic to a disk and on 4364 piecewise linear mappings into a planar domain. This package 4365 implements some of the state-of-the-art surface mesh 4366 parameterization methods, such as least squares conformal maps, 4367 discrete conformal map, discrete authalic parameterization, Floater 4368 mean value coordinates or Tutte barycentric mapping. 4369- Principal Component Analysis (new package) 4370 This package provides functions to compute global informations on 4371 the shape of a set of 2D or 3D objects such as points. It provides 4372 the computation of axis-aligned bounding boxes, centroids of point 4373 sets, barycenters of weighted point sets, as well as linear least 4374 squares fitting for point sets in 2D, and point sets as well as 4375 triangle sets in 3D. 4376- 2D Placement of Streamlines (new package) 4377 Visualizing vector fields is important for many application domains. 4378 A good way to do it is to generate streamlines that describe the 4379 flow behaviour. This package implements the "Farthest Point Seeding" 4380 algorithm for placing streamlines in 2D vector fields. It generates 4381 a list of streamlines corresponding to an input flow using a 4382 specified separating distance. The algorithm uses a Delaunay 4383 triangulation to model objects and address different queries, and 4384 relies on choosing the centers of the biggest empty circles to start 4385 the integration of the streamlines. 4386- Kinetic Data Structures (new package) 4387 Kinetic data structures allow combinatorial structures to be 4388 maintained as the primitives move. The package provides 4389 implementations of kinetic data structures for Delaunay 4390 triangulations in two and three dimensions, sorting of points in one 4391 dimension and regular triangulations in three dimensions. The 4392 package supports exact or inexact operations on primitives which 4393 move along polynomial trajectories. 4394- Kinetic Framework (new package) 4395 Kinetic data structures allow combinatorial geometric structures to 4396 be maintained as the primitives move. The package provides a 4397 framework to ease implementing and debugging kinetic data 4398 structures. The package supports exact or inexact operations on 4399 primitives which move along polynomial trajectories. 4400- Smallest Enclosing Ellipsoid (new package) 4401 This algorithm is new in the chapter Geometric Optimisation. 4402- 2D Arrangement (major revision) 4403 This package can be used to construct, maintain, alter, and display 4404 arrangements in the plane. Once an arrangement is constructed, the 4405 package can be used to obtain results of various queries on the 4406 arrangement, such as point location. The package also includes 4407 generic implementations of two algorithmic frameworks, that are, 4408 computing the zone of an arrangement, and line-sweeping the plane, 4409 the arrangements is embedded on. 4410 4411 Arrangements and arrangement components can also be extended to 4412 store additional data. An important extension stores the 4413 construction history of the arrangement, such that it is possible to 4414 obtain the originating curve of an arrangement subcurve. 4415 4416- Geometric Optimisation (major revision) 4417 The underlying QP solver which is the foundation for several 4418 algorithms in the Geometric Optimisation chapter has been completely 4419 rewritten. 4420- 3D Triangulation (new functionality) 4421 Regular\_triangulation\_3 now offers vertex removal. 4422 4423Release 3.1 4424----------- 4425 4426Release date: December 2004 4427 4428Version 3.1 differs from version 3.0 in the platforms that are supported 4429and in functionality. There have also been a number of bug fixes for 4430this release. 4431 4432Additional supported platforms: 4433 4434- MS Visual C++, version 7.3. and 8.0 4435- Intel 8.0 4436- SunPro CC versions 5.4 and 5.5 on Solaris 4437- GNU g++ versions 3.4 on Linux, Solaris, Irix, cygwin, FreeBSD, and 4438 MacOS X 4439- Darwin (MacOS X) and IA64/Linux support. 4440 4441The following platforms are no longer supported: 4442 4443- MS Visual C++, version 7.0 4444 4445The following functionality has been added or changed: 4446 4447 4448### All 4449 4450- The CORE 1.7 library for exact real arithmetic. 4451- Updated GMP to 4.1.3. 4452- Added Mpfr a library for multiple-precision floating-point 4453 computations with exact rounding. 4454- Added Boost 1.32.0 (only include files). 4455 4456### Installation 4457 4458- new option --disable-shared to omit building libCGAL.so. 4459 4460### Manuals 4461 4462- Merged all major manuals in one multi-part manual, which provides 4463 now cross-links between the CGAL Kernel, the CGAL Basic Library, and 4464 the CGAL Support Library HTML manuals. 4465- Improved layout. 4466 4467### Kernels 4468 4469- Improved efficiency of filtered kernels. 4470- More predicates and constructions. 4471 4472### Basic Library 4473 4474- 2D Segment Voronoi Diagram (new package) 4475 A data structure for Voronoi diagrams of segments in the plane under 4476 the Euclidean metric. The Voronoi edges are arcs of straight lines 4477 and parabolas. The algorithm provided in this package is 4478 incremental. 4479- 2D Conforming Triangulations and Meshes (new package) 4480 An implementation of Shewchuk's algorithm to construct conforming 4481 triangulations and 2D meshes. 4482- 3D Boolean Operations on Nef Polyhedra (new package) 4483 A new class (Nef\_polyhedron\_3) representing 3D Nef polyhedra, a 4484 boundary representation for cell-complexes bounded by halfspaces 4485 that supports boolean operations and topological operations in full 4486 generality including unbounded cells, mixed dimensional cells (e.g., 4487 isolated vertices and antennas). Nef polyhedra distinguish between 4488 open and closed sets and can represent non-manifold geometry. 4489- 2D and Surface Function Interpolation (new package) 4490 This package implements different methods for scattered data 4491 interpolation: Given measures of a function on a set of discrete 4492 data points, the task is to interpolate this function on an 4493 arbitrary query point. The package further offers functions for 4494 natural neighbor interpolation. 4495- Planar Nef polyhedra embedded on the sphere (new package) 4496 A new class (Nef\_polyhedron\_S2) designed and supported mainly to 4497 represent sphere neighborhoods around vertices of the three- 4498 dimensional Nef polyhedra. 4499- Box\_intersection\_d (new package) 4500 A new efficient algorithm for finding all intersecting pairs for 4501 large numbers of iso-oriented boxes, i.e., typically these will be 4502 bounding boxes of more complicated geometries. Useful for (self-) 4503 intersection tests of surfaces etc. 4504- 2D Snap Rounding (new package) 4505 Snap Rounding is a well known method for converting 4506 arbitrary-precision arrangements of segments into a fixed-precision 4507 representation. In the study of robust geometric computing, it can 4508 be classified as a finite precision approximation technique. 4509 Iterated Snap Roundingis a modification of Snap Rounding in which 4510 each vertex is at least half-the-width-of-a-pixel away from any 4511 non-incident edge. This package supports both methods. 4512- 3D Triangulations 4513 - Triangulation\_3: added operator==(),removed push\_back() and 4514 copy\_triangulation(). 4515 - Delaunay\_3 : added nearest\_vertex(), move\_point(), 4516 vertices\_in\_conflict(). 4517 - Regular\_3 : added filtered traits class, and 4518 nearest\_power\_vertex(). 4519- Planar\_map and Arrangement\_2 4520 - The interface of the two traits functions that compute the 4521 intersection of two given curves changed. The functions 4522 nearest\_intersection\_to\_right() and 4523 nearest\_intersection\_to\_left() return an object of type 4524 CGAL::Object that represents either an empty intersection, a 4525 point, or an overlapping subcurve. 4526 - Requirements to define two binary tags were added to the traits 4527 concept of the Planar\_map as follows: *Has\_left\_category* - 4528 indicates whether the functions 4529 curves\_compare\_y\_at\_x\_left() and 4530 nearest\_intersection\_to\_left() are implemented in the traits 4531 model. *Has\_reflect\_category* - indicates whether the 4532 functions point\_reflect\_in\_x\_and\_y() and 4533 curve\_reflect\_in\_x\_and\_y() are implemented in the traits 4534 model. They can be used as an alternative to the two function in 4535 the previous item. 4536 - A new constructor of the Segment\_cached\_2 type that represents 4537 a segment in the Arr\_segment\_cached\_traits\_2 traits class 4538 was introduced. The new constructor accepts the segment 4539 endpoints as well as the coefficients of the underlying line. 4540 - A new version of the conic-arc traits, based on CORE version 1.7 4541 was introduced. This new traits class makes use of CORE's 4542 rootOf() operator to compute the intersection points in the 4543 arrangement, making its code much simpler and more elegant than 4544 the previous version. In addition, new constructors for conic 4545 arcs are provided. The new traits class usually performs about 4546 30% faster than the version included in CGAL 3.0 4547 - The traits class that handles continuous piecewise linear 4548 curves, namely Arr\_polyline\_traits\_2, was rewritten. The new 4549 class is parametrized with a traits class that handles segments, 4550 say Segment\_traits. The polyline curve defined within the 4551 Arr\_polyline\_traits\_2 class is implemented as a vector of 4552 segments of type Segment\_traits::Curve\_2. 4553 - A meta traits class, namely Arr\_curve\_data\_traits\_2, that 4554 extends the curve type of the planar-map with arbitrary 4555 additional data was introduced. It should be instantiated with a 4556 regular traits-class and a class that contains all extraneous 4557 data associated with a curve. 4558 - The class that represents the trapezoidal-decomposition point 4559 location strategy was renamed to 4560 Pm\_trapezoid\_ric\_point\_location. 4561 - The Arrangement demo was rewritten. It covers many more 4562 features, has a much better graphical user interface, and comes 4563 with online documentation. 4564 - Few bugs in the sweep-line module related to overlapping 4565 vertical segments were fixed. This module is used by the 4566 aggregate insert method that inserts a collection of curves at 4567 once. 4568- Triangulation\_2 4569 - added a filtered trait class in the regular triangulation 4570 - added split and join operations in the triangulation data 4571 structure class 4572- Alpha\_shapes\_3 4573 - major changes in the implementation of the class 4574 Alpha\_shapes\_3. 4575 - New implementation results in a true GENERAL mode allowing null 4576 and negative alpha-values. It also fixed the edges 4577 classification bug and introduces a classification of vertices. 4578- Min\_ellipse\_2 4579 - made access to approximate double representation public 4580 - fixed bugs in conversion to double representation 4581 - added `is_circle()` method 4582 - minor performance improvements 4583- Min\_sphere\_of\_spheres\_d: 4584 - The models 4585 `Min_sphere_of_spheres_d_traits_2<K,FT,UseSqrt,Algorithm>`, 4586 `Min_sphere_of_spheres_d_traits_3<K,FT,UseSqrt,Algorithm>`, and 4587 `Min_sphere_of_spheres_d_traits_d<K,FT,Dim,UseSqrt,Algorithm>` 4588 of concept `MinSphereOfSpheresTraits` now represent a sphere as 4589 a `std::pair<Point,Radius>` (and not any more as a 4590 `CGAL::Weighted_point<Point,Weight>`) 4591 - Internal code cleanup; in particular, implementation details 4592 don't pollute the namespace CGAL anymore 4593- Polyhedron\_3 4594 - New Tutorial on CGAL Polyhedron for Subdivision Algorithms with 4595 interactive demo viewer in source code available. 4596 - Added example program for efficient self-intersection test. - 4597 Added small helper functions, such as vertex\_degree, 4598 facet\_degree, edge\_flip, and is\_closed. 4599- Apollonius Graph (Voronoi of Circles) 4600 - Reduced memory requirements by approximately a factor of two. 4601 4602Release 3.0.1 4603------------- 4604 4605Release date: February 2004 4606 4607This is a bug-fix release. No new features have been added in 3.0.1. 4608Here is the list of bug-fixes. 4609 4610### Polyhedral Surface 4611 4612- Fixed wrong include files for output support. Added example. 4613 4614### Planar\_map 4615 4616- Fixed the so called "Walk-along-a-line" point-location strategy to 4617 correctly handle a degenerate case. 4618 4619### 2D Triangulation 4620 4621- added missing figure in html doc 4622- in Line\_face\_circulator\_2.h: 4623 Fixed changes made to support handles with a typedef to iterator. 4624 The fix concerns operator== and !=. 4625 4626### Alpha\_shapes\_3 4627 4628- fixed classify member function for edges. 4629 4630### Number types 4631 4632- Lazy\_exact\_nt: 4633 - added the possibility to select the relative precision of 4634 `to_double()` (by default 1e-5). This should fix reports that 4635 some circumcenters computations have poor coordinates, e.g. 4636 nan). 4637 - when exact computation is triggered, the interval is recomputed, 4638 this should speed up some kinds of computations. 4639- `to_interval(Quotient<MP_Float>)`: avoid spurious overflows. 4640 4641### Kernel 4642 4643- missing acknowledgment in the manual and minor clarification of 4644 `intersection()` documentation. 4645 4646Release 3.0 4647----------- 4648 4649Release date: October 2003 4650 4651Version 3.0 differs from version 2.4 in the platforms that are supported 4652and in functionality. There have also been a number of bug fixes for 4653this release. 4654 4655The license has been changed to either the LGPL (GNU Lesser General 4656Public License v2.1) or the QPL (Q Public License v1.0) depending on 4657each package. So CGAL remains free of use for you, if your usage meets 4658the criteria of these licenses, otherwise, a commercial license has to 4659be purchased from GeometryFactory. 4660 4661Additional supported platforms: 4662 4663- MS Visual C++, version 7.1. 4664- SunPro CC versions 5.4 and 5.5 on Solaris 4665- GNU g++ versions 3.2 and 3.3 on Linux, Solaris, Irix, cygwin, and 4666 FreeBSD. 4667- MipsPRO CC 7.30 and 7.40 with both the n32 and n64 ABIs. 4668 4669The following platforms are no longer supported: 4670 4671- MS Visual C++, version 6. 4672- GNU g++ 2.95.2 (2.95.3 is still supported) 4673- Kai C++ and Borland C++, all versions 4674 4675The following functionality has been added or changed: 4676 4677**All** 4678 4679- The CORE library for exact computations is now distributed as part 4680 of CGAL as well. 4681 4682### Kernels 4683 4684- 3 typedefs have been added to ease the choice of a robust and fast 4685 kernel: 4686 - Exact\_predicates\_inexact\_constructions\_kernel 4687 - Exact\_predicates\_exact\_constructions\_kernel 4688 - Exact\_predicates\_exact\_constructions\_kernel\_with\_sqrt 4689- Progress has been made towards the complete adaptability and 4690 extensibility of our kernels. 4691- New faster Triangle\_3 intersection test routines. 4692 *(see Erratum)* 4693- Added a Kernel concept archetype to check that generic algorithms 4694 don't use more functionality than they should. 4695- A few more miscellaneous functions. 4696 4697### Basic Library 4698 4699- 2D Apollonius Graph (new package) 4700 Algorithms for computing the Apollonius graph in two dimensions. The 4701 Apollonius graph is the dual of the Apollonius diagram, also known 4702 as the additively weighted Voronoi diagram. The latter can be 4703 thought of as the Voronoi diagram of a set of circles under the 4704 Euclidean metric, and it is a generalization of the standard Voronoi 4705 diagram for points. The algorithms provided are dynamic. 4706- dD Min Sphere of Spheres (new package) 4707 Algorithms to compute the smallest enclosing sphere of a given set 4708 of spheres in R<sup>d</sup>. The package provides an algorithm with 4709 maximal expected running time *O(2<sup>O(d)</sup> n)* and a fast and 4710 robust heuristic (for dimension less than 30). 4711- Spatial Searching (new package) 4712 Provides exact and approximate distance browsing in a set of points 4713 in *d*-dimensional space using implementations of algorithms 4714 supporting: 4715 - both nearest and furthest neighbor searching 4716 - both exact and approximate searching 4717 - (approximate) range searching 4718 - (approximate) *k*-nearest and *k*-furthest neighbor searching 4719 - (approximate) incremental nearest and incremental furthest 4720 neighbor searching 4721 - query items representing points and spatial objects. 4722- **Kd-tree** 4723 this package is deprecated, its documentation is removed. It is 4724 replaced by the Spatial Searching package. 4725- Largest\_empty\_rectangle\_2 4726 Given a set of points P in the plane, the class 4727 Largest\_empty\_iso\_rectangle\_2 is a data structure that maintains 4728 an iso-rectangle with the largest area among all iso-rectangles that 4729 are inside a given iso-rectangle bounding box, and that do not 4730 contain any point of the point set P. 4731- 2D Triangulation and 3D Triangulation 4732 - The classes Triangulation\_data\_structure\_2 (and 3), which 4733 implements the data structure for 2D triangulation class, now 4734 makes use of CGAL::Compact\_container (see Support Library 4735 section below). 4736 - The triangulation classes use a Rebind mecanism to provide the 4737 full flexibility on Vertex and Face base classes. This means 4738 that it is possible for the user to derive its own Face of 4739 Vertex base class, adding a functionality that makes use of 4740 types defined by the triangulation data structure like 4741 Face\_handle or Vertex\_handle. 4742 - New classes Triangulation\_vertex\_base\_with\_info\_2 (and 3) 4743 and Triangulation\_face\_base\_with\_info\_2 (and 3) to make 4744 easier the customisation of base classes in most cases. 4745- 2D Triangulation 4746 - Regular triangulation provides an easy access to hidden points. 4747 - The Triangulation\_hierarchy\_2, which provide an efficient 4748 location data structure, can now be used with any 2D 4749 triangulation class plugged in (including Regular 4750 triangulations). 4751- 3D Triangulation 4752 - faster vertex removal function in Delaunay\_triangulation\_3. 4753 - Delaunay\_triangulation\_3 is now independent of the order of 4754 insertions of the points (in case of degenerate cosphericity). 4755 - Regular\_triangulation\_3 now hides vertices (and updates 4756 itself) when inserting a coinciding point with greater weight. 4757 This required a new predicate. 4758 - deprecated functions: copy\_triangulation(), push\_back(), 4759 set\_number\_of\_vertices(). 4760 - Triangulation\_3 now gives non-const access to the data 4761 structure. 4762- Interval Skip List (new package) 4763 An interval skip list is a data strucure for finding all intervals 4764 that contain a point, and for stabbing queries, that is for 4765 answering the question whether a given point is contained in an 4766 interval or not. 4767- Planar Maps and Arrangements 4768 The changes concern mainly the traits classes. 4769 1. New traits hierarchy and interface: The set of requirements was 4770 made sound and complete. A couple of requirements were 4771 eliminated, few others were redefined, and some were renamed. A 4772 hierarchy of three traits classes for the Planar\_map\_2, 4773 Planar\_map\_with\_intersections\_2, and Arrangement\_2 types 4774 was established to include only the necessary requirements at 4775 each level. It was determined that for the aggregate insertion- 4776 operation based on a sweep-line algorithm only a subset of the 4777 requirements is needed. Preconditions were added where 4778 appropriate to tighten the requirements further. 4779 4780 The following functions have been renamed: 4781 4782 - point\_is\_same() renamed to point\_equal() 4783 - curve\_is\_same() renamed to curve\_equal() 4784 - curve\_is\_in\_x\_range() renamed to point\_in\_x\_range() 4785 - curve\_compare\_at\_x() renamed to 4786 curves\_compare\_y\_at\_x() Furthermore, a precondition has 4787 been added that the reference point is in the x-range of 4788 both curves. 4789 - curve\_compare\_at\_x\_right() renamed to 4790 curves\_compare\_y\_at\_x\_to\_right(). Furthermore, a 4791 precondition has been added that both curves are equal at 4792 the reference point and defined to its right. 4793 - curve\_compare\_at\_x\_left() renamed to 4794 curves\_compare\_y\_at\_x\_to\_left(). Furthermore, a 4795 precondition has been added that both curves are equal at 4796 the reference point and defined to its right. 4797 - curve\_get\_point\_status() renamed to 4798 curve\_compare\_y\_at\_x(). Furthermore, a precondition has 4799 been added that the point is in the x-range of the curve. 4800 Consequently, the function now returns a Comparison\_result 4801 (instead of a special enum). 4802 - make\_x\_monotone() renamed to curve\_make\_x\_monotone() 4803 See more details below. 4804 - curve\_flip() renamed to curve\_opposite() 4805 4806 The following functions have been removed: 4807 4808 - curve\_is\_between\_cw() 4809 - point\_to\_left() 4810 - point\_to\_right() 4811 - is\_x\_monotone() 4812 - point\_reflect\_in\_x\_and\_y() 4813 - curve\_reflect\_in\_x\_and\_y() 4814 - do\_intersect\_to\_right() 4815 - do\_intersect\_to\_left() 4816 4817 Most functions, are required by the PlanarMapTraits\_2 concept, 4818 except for the make\_x\_monotone(), 4819 nearest\_intersection\_to\_right(), 4820 nearest\_intersection\_to\_left(), curves\_overlap() and 4821 curve\_opposite(). PlanarMapWithIntersectionsTraits\_2 requires 4822 all these functions, except curve\_opposite(), needed only by 4823 the ArrangementTraits\_2 concept. 4824 4825 Furthermore, the two functions curve\_compare\_at\_x\_left() and 4826 nearest\_intersection\_to\_left() can be omitted, if the two 4827 functions point\_reflect\_in\_x() and curve\_reflect\_in\_x() 4828 are implemented. Reflection can be avoided, if the two \_left 4829 functions are supplied. 4830 4831 2. The type X\_curve\_2 of the PlanarMapWithIntersectionsTraits\_2 4832 concept was renamed to X\_monotone\_curve\_2, and the 4833 distinction between this type and the Curve\_2 type was made 4834 firm. The method is\_x\_monotone() of the 4835 PlanarMapWithIntersectionsTraits\_2 concept was removed. The 4836 related method curve\_make\_x\_monotone() is now called for each 4837 input curve of type Curve\_2 when curves are inserted into a 4838 Planar\_map\_with\_intersections\_2 to subdivide the input curve 4839 into x-monotone sub-curves (and in case the curve is already 4840 x-monotone, this function is responsible for casting it to an 4841 x-monotone curve). 4842 3. New and improved traits classes: 4843 4. Conic traits - Arr\_conic\_traits\_2 Support finite segments of 4844 ellipses, hyperbolas and parabolas, as well as line segments. 4845 The traits require an exact real number- type, such as 4846 leda\_real or CORE::Expr. 4847 5. Segment cached traits - Arr\_segment\_cached\_traits\_2 This 4848 class uses an improved representation for segments that helps 4849 avoiding cascaded computations, thus achieving faster running 4850 times. To work properly, an exact rational number-type should be 4851 used. 4852 6. Polyline traits - Arr\_polyline\_traits\_2 The polyline traits 4853 class has been reimplemented to work in a more efficient, 4854 generic manner. The new class replaces the obsolete 4855 Arr\_polyline\_traits class. It is parameterized with a segment 4856 traits class. 4857 7. Hyperbola and segment traits - Arr\_hyper\_segment\_traits\_2 4858 Supports line segments and segments of canonical hyperbolas. 4859 This is the type of curves that arise when projecting segments 4860 in three-space rotationally around a line onto a plane 4861 containing the line. Such projections are often useful in 4862 CAD/CAM problems. 4863 8. Removed old traits class: 4864 - The models of the PlanarMapWithIntersectionsTraits\_2 4865 concept below became obsolete, as the new conic traits, 4866 namely Arr\_conic\_traits\_2, supports the same 4867 functionality and is much more efficient. 4868 - Arr\_circles\_real\_traits 4869 - Arr\_segment\_circle\_traits 4870 - The segment traits class and the new polyline traits class 4871 were reimplemented using standard CGAL-kernel calls. This 4872 essentially eliminated the corresponding leda traits 4873 classes, namely: 4874 - Pm\_leda\_segment\_traits\_2 4875 - Arr\_leda\_segment\_traits\_2 4876 - Arr\_leda\_polyline\_traits 4877 4878 With the use of the Leda\_rat\_kernel new external package 4879 the same functionality can be achieved with less overhead 4880 and more efficiency. 4881 9. Sweep Line 4882 - The Sweep\_line\_2 package was reimplemented. As a 4883 consequence it is much more efficient, its traits is tighter 4884 (namely neither the two \_left nor the reflection functions 4885 are required), and its interface has changed a bit. 4886 1. The following global functions have been removed: 4887 - sweep\_to\_produce\_subcurves\_2() 4888 - sweep\_to\_produce\_points\_2() 4889 - sweep\_to\_construct\_planar\_map\_2() 4890 4891 Instead, the public methods of the Sweep\_line\_2 class 4892 listed below were introduced: 4893 - get\_subcurves() - Given a container of curves, this 4894 function returns a list of curves that are created 4895 by intersecting the input curves. 4896 - get\_intersection\_points() - Given a range of 4897 curves, this function returns a list of points that 4898 are the intersection points of the curves. 4899 - get\_intersecting\_curves() - Given a range of 4900 curves, this function returns an iterator to the 4901 beginning of a range that contains the list of 4902 curves for each intersection point between any two 4903 curves in the specified range. 4904 4905 2. It is possible to construct a planar map with 4906 intersections (or an arrangement) by inserting a range 4907 of curves into an empty map. This will invoke the 4908 sweep-line process to construct the map more 4909 efficiently. 4910 - New interface functions to the 4911 Planar\_map\_with\_intersections\_2 class. The 4912 Planar\_map\_with\_intersections\_2 class maintains a planar 4913 map of input curves that possibly intersect each other and 4914 are not necessarily x-monotone. If an input curve, or a set 4915 of input curves, are known to be x-monotone and pairwise 4916 disjoint, the new functions below can be used to insert them 4917 into the map efficiently. 4918 4919- Polyhedral Surface 4920 - The old design that was deprecated since CGAL 2.3 has been 4921 removed. 4922 - Class `Polyhedron_incremental_builder_3`: 4923 - Renamed local enum `ABSOLUTE` to `ABSOLUTE_INDEXING`, and 4924 `RELATIVE` to `RELATIVE_INDEXING` to avoid conflicts with 4925 similarly named macros of another library. 4926 - Changed member functions `add_vertex()`, `begin_facet()`, 4927 and `end_facet()` to return useful handles. 4928 - Added `test_facet()` to check facets for validity before 4929 adding them. 4930 - Added `vertex( size_t i)` to return `Vertex_handle` for 4931 index `i`. 4932- Halfedge Data Structure 4933 - The old design that was deprecated since CGAL 2.3 has been 4934 removed. 4935 4936### Support Library 4937 4938- New container class Compact\_container, which (roughly) provides the 4939 flexibility of std::list, with the memory compactness of 4940 std::vector. 4941- Geomview\_stream: added a function gv.draw\_triangles(InputIterator 4942 begin, InputIterator end) which draws a set of triangles much more 4943 quickly than one by one. 4944- Number types: 4945 - number types are now required to provide a function: 4946 std::pair<double, double> to\_interval(const NT &). 4947 - number types are now required to provide mixed operators with 4948 "int". 4949 - CLN support removed. 4950 - faster square() for MP\_Float. 4951 - added Gmp\_q. 4952- Qt\_widget: 4953 - New classes: 4954 - Qt\_help\_window: provides a simple way to show some helpful 4955 information about a demo as an HTML page. 4956 - Qt\_widget\_history: provides basic functionality to 4957 manipulate intervals of Qt\_widget class. The current 4958 visible area of Qt\_widget is mapped to an interval. Each 4959 interval could be stored in the Qt\_widget\_history object. 4960 So you can use this object to navigate in history. It is 4961 mostly used by Qt\_widget\_standard\_toolbar. 4962 - Changes: 4963 - Qt\_widget\_standard\_toolbar: is derived from QToolBar 4964 class, so pay attention to modify your code, if you used 4965 this class. Some public methods were introduced to control 4966 the history object that the toolbar use to navigate. 4967 - the icons are now part of libCGALQt. 4968 - Deprecated members of Qt\_widget: 4969 - add\_to\_history(), clear\_history(), back(), forth(): use 4970 forward(), back() and clear\_history() of the 4971 Qt\_widget\_standard\_toolbar instead. 4972 - custom\_redraw(): use redraw\_on\_back() and 4973 redraw\_on\_front() instead. 4974 - Optimizations: the output operators of the following classes 4975 have been optimized: 4976 - CGAL::Segment\_2 (now tests for intersection with the 4977 drawing area) 4978 - CGAL::Triangle\_2 (now tests for intersection with the 4979 drawing area) 4980 - CGAL::Triangulation\_2 (is optimized for faster display on 4981 zooming) 4982 4983### Erratum in the Kernel manual 4984 4985- Intersection test routines 4986 4987 The documentation of CGAL::do\_intersect should mention, for the 3D 4988 case: 4989 Also, in three-dimensional space *Type1* can be 4990 4991 - either *Plane\_3<Kernel>* 4992 - or *Triangle\_3<Kernel>* 4993 4994 and *Type2* any of 4995 4996 - *Plane\_3<Kernel>* 4997 - *Line\_3<Kernel>* 4998 - *Ray\_3<Kernel>* 4999 - *Segment\_3<Kernel>* 5000 - *Triangle\_3<Kernel>* 5001 5002 In the same way, for *Kernel::DoIntersect\_3*: 5003 for all pairs *Type1* and *Type2*, where the type *Type1* is 5004 5005 - either *Kernel::Plane\_3* 5006 - or *Kernel::Triangle\_3* 5007 5008 and *Type2* can be any of the following: 5009 5010 - *Kernel::Plane\_3* 5011 - *Kernel::Line\_3* 5012 - *Kernel::Ray\_3* 5013 - *Kernel::Segment\_3* 5014 - *Kernel::Triangle\_3* 5015 5016 Philippe Guigue (INRIA Sophia-Antipolis) should be mentioned as one 5017 of the authors. 5018 5019Release 2.4 5020----------- 5021 5022Release date: May 2002 5023 5024Version 2.4 differs from version 2.3 in the platforms that are supported 5025and in functionality. There have also been a number of bug fixes for 5026this release. 5027 5028Additional supported platforms: 5029 5030- Microsoft Visual C++, version 7. 5031- SunPro 5.3 (with patch 111685-05) on Solaris 5032- g++ 3.1 on Linux and Solaris 5033 5034The following functionality has been added or changed: 5035 5036 5037### Kernels 5038 5039- Point\_d has been removed from the 2D and 3D kernels. This type is 5040 now available from the d-dimensional kernel only. 5041 5042### Basic Library 5043 5044- 2D Polygon Partitioning 5045 Traits requirements for optimal partitioning have been changed 5046 slightly. 5047 5048- 2D Sweep line 5049 A new package that implements a sweep-line algorithm to compute 5050 arrangements of curves for different families of curves, which are 5051 not necessarily line segments (e.g., it also works for circular 5052 arcs). The resulting output can be the list of vertex points, the 5053 resulting subcurves or a planar map. 5054 5055- Planar Maps and Arrangements 5056 - New quicker insertion functions of Planar\_map\_2 for cases 5057 where more precomputed information is available regarding the 5058 position of the inserted curve in the map. 5059 - New query function for planar maps that determines whether a 5060 given point is within a given face of the planar map. 5061 - New iterator over edges of planar maps in addition to the 5062 existing iterator over halfedges. 5063 - New copy constructor and assignment operator for arrangements. 5064 5065 5066 5067- Polyhedral Surface 5068 - new design introduced with release 2.3 now supported by VC7 5069 compiler 5070 - Extended functionality of Polyhedron\_incremental\_builder: 5071 absolute indexing allows one to add new surfaces to existing 5072 ones. 5073 5074 5075 5076- 2D Triangulation 5077 - There is a new triangulation data structure replacing the two 5078 previous ones. This new data structure is coherent with the 3d 5079 triangulation data structure and offer the advantages of both 5080 previous ones. Backward compatibility is ensured and this change 5081 is transparent for the user of triangulation classes. 5082 - Constrained and Delaunay constrained triangulations are now able 5083 to handle intersecting input constraints. The behavior of 5084 constrained triangulations with repect to intersection of input 5085 constraints can be customized using an intersection tag. 5086 - A new class Constrained\_triangulation\_plus offers a 5087 constrained hierarchy on top of a constrained triangulations. 5088 This additionnal data structure describes the subdivision of the 5089 original constraints into edges of the triangulations. 5090 5091 5092 5093- 3D Triangulation 5094 - Running time improved by a better and more compact management of 5095 memory allocation 5096 - Various improvements and small functionalities added: 5097 - Triangulation\_3<GT,Tds>::triangle() returns a 5098 triangle oriented towards the outside of the cell c for 5099 facet (c,i) 5100 - New function insert(Point, Locate\_type, Cell\_handle, int, 5101 int) which avoids the location step. 5102 - New function to get access to cells in conflict in a 5103 Delaunay insertion : find\_conflicts() and 5104 insert\_in\_hole() 5105 - New function TDS::delete\_cells(begin, end). 5106 - New functions : degree(v), reorient(), 5107 remove\_decrease\_dimension(), remove\_from\_simplex(). 5108 - Changes of interface: 5109 - vertices and cells are the same for the triangulation data 5110 structure and the geometric triangulation 5111 - the triangulation data structure uses Vertex\_handle (resp 5112 Cell\_handle) instead of Vertex\* (resp Cell\*). 5113 - incident\_cells() and incident\_vertices() are templated by 5114 output iterators 5115 - changes in the iterators and circulators interface: 5116 - Iterators and circulators are convertible to handles 5117 automatically, no need to call "->handle()" anymore. 5118 - Vertex\_iterator split into All\_vertices\_iterator and 5119 Finite\_vertices\_iterator (and similar for cells...). 5120 - TDS::Edge/Facet iterators now support operator->. 5121 5122 5123 5124- 2D Search structures 5125 Additional range search operations taking a predicate functor have 5126 been added 5127 5128### Support Library 5129 5130- Qt\_widget 5131 - We have added a new class for visualization of 2D CGAL objects. 5132 It is derived from Trolltech's Qt class QWidget and privdes a 5133 used to scale and pan. 5134 - Some demos were developed for the following packages: 2D Alpha 5135 shapes, 2D Convex Hull, Largest empty 2D rectangle, Maximum 5136 k-gon, Minimum ellipse, Minimum 2D quadrilateral, 2D polygon 5137 partitioning 2D regular and constrained triangulation. 5138 - Tutorials are available to help users get used to Qt\_widget 5139 5140 5141 5142- Timer 5143 Fixed Timer class (for user process time) to have no wrap-around 5144 anymore on Posix-compliant systems. 5145 5146The following functionality is no longer supported: 5147 5148- Planar maps of infinite curves (the so-called planar map 5149 bounding-box). 5150 5151Bugs in the following packages have been fixed: 3D Convex hull, 2D 5152Polygon partition, simple polygon generator 5153 5154Also attempts have been made to assure compatability with the upcoming 5155LEDA release that introduces the leda namespace. 5156 5157### Known problems 5158 5159- 2D Nef Polyhedra contains a memory leak. Memory problems are also 5160 the likely cause of occasional run-time errors on some platforms. 5161- The d-dimensional convex hull computation produces run-time errors 5162 on some platforms because of memory management bugs. 5163- The new Halfedge Data Structure design introduced with release 2.3 5164 does not work on VC6. See the release notes in the manual for more 5165 information. 5166- The following deficiencies relate to planar maps, planar maps of 5167 intersecting curves (pmwx), arrangements and sweep line. 5168 - On KCC, Borland and SunPro we guarantee neither compilation nor 5169 correct execution for all of the packages above. 5170 - On VC6 and VC7 we guarantee neither compilation nor correct 5171 execution of the sweep line package. 5172 - On CC (on Irix 6.5) the trapezoidal decomposition point location 5173 strategy is problematic when used with planar maps, pmwx, or 5174 arrangements (mind that this is the default for planar maps). 5175 - On CC (on Irix 6.5) sweep line with polyline traits does not 5176 compile (mind that the so-called leda polyline traits does 5177 compile). 5178 - On g++ (on Irix 6.5) the segment-circle 5179 (Arr\_segment\_circle\_traits\_2) traits does not compile for 5180 either of the above packages. 5181 5182Release 2.3 5183----------- 5184 5185Release date: August 2001 5186 5187Version 2.3 differs from version 2.2 in the platforms that are supported 5188and in functionality. 5189 5190Additional supported platform: 5191 5192- Gnu g++ 3.0 on Solaris and Linux 5193 5194The following functionality has been added: 5195 5196 5197### Kernels 5198 5199- The 2D and 3D kernels now serve as models of the new kernel concept 5200 described in the recent paper, "An Adaptable and Extensible Geometry 5201 Kernel" by Susan Hert, Micheal Hoffmann, Lutz Kettner, Sylvain Pion, 5202 and Michael Seel to be presented at WAE 2001 (and soon available as 5203 a technical report). This new kernel is completely compatible with 5204 the previous design but is more flexible in that it allows geometric 5205 predicates as well as objects to be easily exchanged and adapted 5206 individually to users' needs. 5207- A new kernel called `Simple_homogeneous` is available. It is 5208 equivalent to `Homogeneous` but without reference-counted objects. 5209- A new kernel called `Filtered_kernel` is available that allows one 5210 to build kernel traits classes that use exact and efficient 5211 predicates. 5212- There are two classes, `Cartesian_converter` and 5213 `Homogeneous_converter` that allows one to convert objects between 5214 different Cartesian and homogeneous kernels, respectively. 5215- A new d-dimensional kernel, `Kernel_d` is available. It provides 5216 diverse kernel objects, predicates and constructions in d dimensions 5217 with two representations based on the kernel families `Cartesean_d` 5218 and `Homogeneous_d` 5219 5220### Basic Library 5221 5222Almost all packages in the basic library have been adapted to the new 5223kernel design to realize the flexibility this design makes possible. In 5224several packages, this means that the traits class requirements have 5225changed to conform to the function objects offered in the kernels so the 5226kernels themselves can be used as traits classes in many instances. 5227- 2D Convex Hull 5228 The traits requirements have changed slightly to bring them in line 5229 with the CGAL kernels. 5230- 3D Convex Hull 5231 - The function `convex_hull_3` now uses a new implementation of 5232 the quickhull algorithm and no longer requires LEDA. 5233 - A new `convex_hull_incremental_3` function based on the new 5234 d-dimensional convex hull class is available for comparison 5235 purposes. 5236 5237 5238- `Convex_hull_d, Delaunay_d` 5239 Two new application classes offering the calculation of 5240 d-dimensional convex hulls and delaunay triangulations 5241 5242- Polygons and Polygon Operations 5243 - The traits class requirements have been changed. 5244 - The simplicity test has a completely new implementation. 5245 - Properties like convexity, simplicity and area can now be cached 5246 by polygons. You need to set a flag to select this behaviour. 5247 5248 5249 5250 5251- Planar Nef Polyhedra 5252 A new class (`Nef_polyhedron_2`) representing planar Nef polyhedra = 5253 rectilinearly bounded points sets that are the result of binary and 5254 topological operations starting from halfplanes. 5255 5256- A new package offering functions to partition planar polygons into 5257 convex and y-monotone pieces is available. 5258 5259- Planar Maps and Arrangements 5260 - A new class `Planar_map_with_intersections_2<Planar_map>` for 5261 planar maps of possibly intersecting, possibly non-x-monotone, 5262 possibly overlapping curves (like `Arrangement_2` but without 5263 the hierarchy tree). 5264 - I/O utilities for planar maps and arrangements for textual and 5265 graphical streams. (It is possible to save and later reload 5266 built planar maps or arrangements.) 5267 - New arrangement traits class for line segments and circular arcs 5268 (`Arr_segment_circle_traits<NT>`). 5269 - New faster traits for polylines specialized for using the LEDA 5270 rational kernel (`Arr_leda_polylines_traits`). The LEDA traits 5271 for segments was also made faster. 5272 - A new point location strategy 5273 (`Pm_simple_point_location<Planar_map>`). 5274 5275 5276 5277- Halfedge Data Structure 5278 5279 The halfedge data structure has been completely revised. The new 5280 design is more in line with the STL naming scheme and it provides a 5281 safe and coherent type system throughout the whole design (no void\* 5282 pointers anymore), which allows for better extendibility. A user can 5283 add new incidences in the mesh easily. The new design also uses 5284 standard allocators with a new template parameter that has a 5285 suitable default. 5286 5287 The old design is still available, but its use is deprecated, see 5288 the manual of deprecated packages for its documentation. Reported 5289 bugs in copying the halfedge data structure (and therefore also 5290 polyhedral surfaces) have been fixed in both designs. Copying a 5291 list-based representation is now based on hash maps instead of 5292 std::map and is therefore considerably faster. 5293 5294- Polyhedral Surface 5295 5296 The polyhedral surface has been rewritten to work with the new 5297 halfedge data structure design. The user level interface of the 5298 `CGAL::Polyhedron_3` class is almost backwards compatible with the 5299 previous class. The exceptions are the template parameter list, 5300 everything that relies on the flexibility of the underlying halfedge 5301 data structure, such as a self-written facet class, and that the 5302 distinction between supported normals and supported planes has been 5303 removed. Only planes are supported. See the manuals for suggestions 5304 how to handle normals instead of planes. 5305 5306 More example programs are provided with polyhedral surfaces, for 5307 example, one about Euler operator and one computing a subdivision 5308 surface given a control mesh as input. 5309 5310 The old design is still available for backwards compatibility and to 5311 support older compiler, such as MSVC++6.0. For the polyhedral 5312 surface, old and new design cannot be used simultaneously (they have 5313 identical include file names and class names). The include files 5314 select automatically the old design for MSVC++6.0 and the new design 5315 otherwise. This automatism can be overwritten by defining 5316 appropriate macros before the include files. The old design is 5317 selected with the `CGAL_USE_POLYHEDRON_DESIGN_ONE` macro. The new 5318 design is selected with the `CGAL_USE_POLYHEDRON_DESIGN_TWO` 5319 macro. 5320 5321- 2D Triangulation 5322 - The geometric traits class requirements have been changed to 5323 conform to the new CGAL kernels. CGAL kernel classes can be used 5324 as traits classes for all 2D triangulations except for regular 5325 triangulations. 5326 - Additionnal functionality: 5327 - dual method for regular triangulations (to build a power 5328 diagram) 5329 - unified names and signatures for various "find\_conflicts()" 5330 member functions in Delaunay and constrained Delaunay 5331 triangulation. 5332 - As an alternative to the simple insert() member function, 5333 insertion of points in those triangulation can be performed 5334 using the combination of find\_conflicts() and star\_hole() 5335 which eventually allows the user to keep track of deleted 5336 faces. 5337 - More demos and examples 5338 5339 5340- 3D Triangulation 5341 - Major improvements 5342 - A new class `Triangulation_hierarchy_3` that allows a faster 5343 point location, and thus construction of the Delaunay 5344 triangulation 5345 - A new method for removing a vertex from a Delaunay 5346 triangulation that solves all degenerate cases 5347 - Running time of the usual location and insertion methods 5348 improved 5349 - A bit more functionality, such as 5350 - New geomview output 5351 - dual methods in Delaunay triangulations to draw the Voronoi 5352 diagram 5353 - More demos and examples 5354 - Changes in interface 5355 - Traits classes requirements have been modified 5356 - The kernel can be used directly as a traits class (except 5357 for regular triangulation) 5358 - insert methods in `Triangulation_data_structure` have a new 5359 interface 5360 5361 5362- A new class (`Alpha_shapes_3`) that computes Alpha shapes of point 5363 sets in 3D is available. 5364 5365- The traits requirements for matrix search and minimum quadrilaterals 5366 have been changed to bring them in line with the CGAL kernels. 5367 5368- Point\_set\_2 5369 - now independent of LEDA; based on the CGAL Delaunay 5370 triangulation 5371 - traits class requirements adapted to new kernel concept. 5372 - function template versions of the provided query operations are 5373 available 5374 5375### Support Library 5376 5377- Number types: 5378 - `Lazy_exact_nt<NT>` is a new number type wrapper to speed up 5379 exact number types. 5380 - `MP_Float` is a new multiprecision floating point number type. 5381 It can do exact additions, subtractions and multiplications over 5382 floating point values. 5383- `In_place_list` has a new third template parameter (with a suitable 5384 default) for an STL-compliant allocator. 5385- `Unique_hash_map` is a new support class. 5386- `Union_find` is a new support class. 5387- `Geomview_stream` : 5388 - Geomview version 1.8.1 is now required. 5389 - no need to have a `~/.geomview` file anymore. 5390 - new output operators for triangulations. 5391 - new output operators for `Ray_2`, `Line_2`, `Ray_3`, `Line_3`, 5392 `Sphere_3`. 5393 - various new manipulators. 5394- Window stream In cooperation with Algorithmic Solutions, GmBH 5395 (distributors of the LEDA library), we can now offer a visualization 5396 package downloadable in binary form that supports visualization on a 5397 ported version of the LEDA window lib. 5398 5399Release 2.2 5400----------- 5401 5402Release date: October 2000 5403 5404Version 2.2 differs from version 2.1 in the platforms that are supported 5405and in functionality. 5406 5407Additional supported platforms: 5408 5409- the KAI compiler (4.0) on Solaris 5.8 5410- Borland C++ (5.5) 5411 5412The following functionality has been added: 5413 5414- There is a new, non-reference-counted kernel, Simple\_cartesian. 5415 Because reference counting is not used, and thus coordinates are 5416 stored within a class, debugging is easier using this kernel. This 5417 kernel can also be faster in some cases than the reference-counted 5418 Cartesian kernel. 5419- New optimisation algorithms 5420 - Min\_annulus\_d - Algorithm for computing the smallest enclosing 5421 annulus of points in arbitrary dimension 5422 - Polytope\_distance\_d - Algorithm for computing the (squared) 5423 distance between two convex polytopes in arbitrary dimension 5424 - Width\_3 - Algorithm for computing the (squared) width of points 5425 sets in three dimensions 5426- 2D Triangulations 5427 - There are now two triangulation data structures available in 5428 CGAL. The new one uses a list to store the faces and allows one 5429 to represent two-dimensional triangulations embedded in three 5430 spaces as well as planar triangulations. 5431 - The triangulation hierarchy which allows fast location query is 5432 now available. 5433- Inifinite objects can now be included in planar maps. 5434- Removal as well as insertions of vertices for 3D Delaunay 5435 triangulations is now possible. 5436- A generator for \`\`random'' simple polygons is now available. 5437- In directory demo/Robustness, programs that demonstrate typical 5438 robustness problems in geometric computing are presented along with 5439 the solutions to these problems that CGAL provides. 5440 5441The following functionality has been removed: 5442 5443- The binary operations on polygons (union, intersection ...) have 5444 been removed. Those operations were not documented in the previous 5445 release (2.1). Arrangements can often be used as a substitute. 5446 5447Release 2.1 5448----------- 5449 5450Release date: January 2000 5451 5452Version 2.1 differs from version 2.0 in the platforms that are supported 5453and in functionality. 5454 5455Supported platforms: 5456 5457- the newest gnu compiler (2.95.2) on Sun, SGI, Linux and Windows. 5458- the Microsoft Visual C++ compiler, version 6. 5459- the mips CC compiler version 7.3 under Irix. 5460 5461Support for the old g++ compiler (2.8) and for mips CC 7.2 has been 5462dropped. 5463 5464The following functionality has been added: 5465- Alpha shapes and weighted alpha shapes in 2D. Alpha shapes are a 5466 generalization of the convex hull of a point set. 5467- Arrangements in 2D. Arrangements are related to and based on planar 5468 maps. The major difference between the two is that curves are 5469 allowed to intersect in the case of arrangements. 5470- Extensions to triangulations in 2D. Constrained triangulations are 5471 now dynamic: they support insertions of new constraint as well as 5472 removal of existing constraints. There are also constrained Delaunay 5473 triangulations. 5474- Triangulations in 3D were added, both Delaunay triangulations and 5475 regular triangulations. 5476- Min\_quadrilateral optimisations have been added. These are 5477 algorithms to compute the minimum enclosing rectangle/parallelogram 5478 (arbitrary orientation) and the minimum enclosing strip of a convex 5479 point set. 5480- 2d Point\_set is a package for 2d range search operations, Delaunay 5481 triangulation, nearest neighbor queries. This package works only if 5482 LEDA is installed. 5483- Support for GeoWin visualization library. This also depends on LEDA. 5484- Support for using the CLN number type together with CGAL. 5485 5486Release 2.0 5487----------- 5488 5489Release date: June 1999 5490 5491The main difference from release 1.2 is the introduction of namespaces 5492-- namespace `std` for code from the standard library and namespace 5493`CGAL` for the CGAL library. 5494 5495Release 1.2 5496----------- 5497 5498Release date: January 1999 5499 5500Additions to release 1.1 include: 5501 5502- topological map 5503- planar map overlay 5504- regular and constrained triangulations 5505 5506Release 1.1 5507----------- 5508 5509Release date: July 1998 5510 5511Additions to release 1.0 include: 5512 5513- 3D intersections 5514- kD points 5515- 3D convex hull 5516- kD smallest enclosing sphere 5517 5518Release 1.0 5519----------- 5520 5521Release date: April 1998 5522 5523Additions to release 0.9 include: 5524 5525- Polyhedral surfaces 5526- Halfedge Data Structure 5527- Planar maps 5528 5529Release 0.9 5530----------- 5531 5532Release date: June 1997 5533 5534Initial (beta) release of the CGAL library. 5535