CGAL 3.0 differs from CGAL 2.4 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
The license has been changed to either the LGPL (GNU Lesser General Public License v2.1) or the QPL (Q Public License v1.0) depending on each package. So CGAL remains free of use for you, if your usage meets the criteria of these licenses, otherwise, a commercial license has to be purchased from GeometryFactory.
- MS Visual C++, version 7.1.
- SunPro CC versions 5.4 and 5.5 on Solaris
- GNU g++ versions 3.2 and 3.3 on Linux, Solaris, Irix, cygwin, and FreeBSD.
- MipsPRO CC 7.30 and 7.40 with both the n32 and n64 ABIs.
The following platforms are no longer supported:
- MS Visual C++, version 6.
- GNU g++ 2.95.2 (2.95.3 is still supported)
- Kai C++ and Borland C++, all versions
- The CORE library for exact computations is now distributed as part of CGAL as well.
Largest_empty_rectangle_2: Given a set of points P in the plane, the class
Largest_empty_iso_rectangle_2is a data structure that maintains an iso-rectangle with the largest area among all iso-rectangles that are inside a given iso-rectangle bounding box, and that do not contain any point of the point set P.
- 3 typedefs have been added to ease the choice of a robust and fast kernel:
- Progress has been made towards the complete adaptability and extensibility of our kernels.
- New faster
Triangle_3intersection test routines.
(see Erratum at the bottom)
- Added a Kernel concept archetype to check that generic algorithms don’t use more functionality than they should.
- A few more miscellaneous functions.
Interval Skip List (new package)
- An interval skip list is a data strucure for finding all intervals that contain a point, and for stabbing queries, that is for answering the question whether a given point is contained in an interval or not.
2D Apollonius Graph (new package)
- Algorithms for computing the Apollonius graph in two dimensions. The Apollonius graph is the dual of the Apollonius diagram, also known as the additively weighted Voronoi diagram. The latter can be thought of as the Voronoi diagram of a set of circles under the Euclidean metric, and it is a generalization of the standard Voronoi diagram for points. The algorithms provided are dynamic.
dD Min Sphere of Spheres (new package)
- Algorithms to compute the smallest
enclosing sphere of a given set of spheres in Rd.
The package provides
an algorithm with maximal expected running time
O(2<sup>O(d)</sup> n)and a fast and robust heuristic (for dimension less than 30).
Spatial Searching (new package)
- Provides exact and approximate distance browsing in a set of points in
d-dimensional space using implementations of algorithms supporting:
- both nearest and furthest neighbor searching
- both exact and approximate searching
- (approximate) range searching
k-furthest neighbor searching
- (approximate) incremental nearest and incremental furthest neighbor searching
- query items representing points and spatial objects.
- This package is deprecated, its documentation is removed. It is replaced by the Spatial Searching package.
2D Triangulation and 3D Triangulation
- The classes Triangulation_data_structure_2 (and 3), which implements the data structure for 2D triangulation class, now makes use of CGAL::Compact_container (see Support Library section below).
- The triangulation classes use a Rebind mecanism to provide the full flexibility on Vertex and Face base classes. This means that it is possible for the user to derive its own Face of Vertex base class, adding a functionality that makes use of types defined by the triangulation data structure like Face_handle or Vertex_handle.
- New classes
Triangulation_vertex_base_with_info_2(and 3) and
Triangulation_face_base_with_info_2(and 3) to make easier the customisation of base classes in most cases.
- Regular triangulation provides an easy access to hidden points.
Triangulation_hierarchy_2, which provides an efficient location data structure, can now be used with any 2D triangulation class plugged in (including regular triangulations).
- Faster vertex removal function in
Delaunay_triangulation_3is now independent of the order of insertions of the points (in case of degenerate cosphericity).
Regular_triangulation_3now hides vertices (and updates itself) when inserting a coinciding point with greater weight. This required a new predicate.
- Deprecated functions:
Triangulation_3now gives non-const access to its data structure.
Planar Maps and Arrangements
The changes concern mainly the traits classes.
- New traits hierarchy and interface:
The set of requirements was made sound and complete. A couple of
requirements were eliminated, few others were redefined, and some
were renamed. A hierarchy of three traits classes for the
Arrangement_2types was established to include only the necessary requirements at each level. It was determined that for the aggregate insertion- operation based on a sweep-line algorithm only a subset of the requirements is needed. Preconditions were added where appropriate to tighten the requirements further.
- The following functions have been renamed:
curves_compare_y_at_x(). Furthermore, a precondition has been added that the reference point is in the x-range of both curves.
curves_compare_y_at_x_to_right(). Furthermore, a precondition has been added that both curves are equal at the reference point and defined to its right.
curves_compare_y_at_x_to_left(). Furthermore, a precondition has been added that both curves are equal at the reference point and defined to its right.
curve_compare_y_at_x(). Furthermore, a precondition has been added that the point is in the x-range of the curve. Consequently, the function now returns a Comparison_result (instead of a special enum).
curve_make_x_monotone(). See more details below.
- The following functions have been removed:
- Most functions, are required by the
PlanarMapTraits_2concept, except for the
PlanarMapWithIntersectionsTraits_2requires all these functions, except
curve_opposite(), needed only by the
ArrangementTraits_2concept. Furthermore, the two functions
nearest_intersection_to_left()can be omitted, if the two functions
curve_reflect_in_x()are implemented. Reflection can be avoided, if the two _left functions are supplied.
- The type X_curve_2 of the PlanarMapWithIntersectionsTraits_2
concept was renamed to X_monotone_curve_2, and the distinction
between this type and the Curve_2 type was made firm. The method
is_x_monotone()of the PlanarMapWithIntersectionsTraits_2 concept was removed. The related method
curve_make_x_monotone()is now called for each input curve of type Curve_2 when curves are inserted into a Planar_map_with_intersections_2 to subdivide the input curve into x-monotone sub-curves (and in case the curve is already x-monotone, this function is responsible for casting it to an x-monotone curve).
- New and improved traits classes:
- Conic traits -
Arr_conic_traits_2Support finite segments of ellipses, hyperbolas and parabolas, as well as line segments. The traits require an exact real number- type, such as leda_real or
- Segment cached traits -
Arr_segment_cached_traits_2This class uses an improved representation for segments that helps avoiding cascaded computations, thus achieving faster running times. To work properly, an exact rational number-type should be used.
- Polyline traits -
Arr_polyline_traits_2The polyline traits class has been reimplemented to work in a more efficient, generic manner. The new class replaces the obsolete Arr_polyline_traits class. It is parameterized with a segment traits class.
- Hyperbola and segment traits -
Arr_hyper_segment_traits_2Supports line segments and segments of canonical hyperbolas. This is the type of curves that arise when projecting segments in three-space rotationally around a line onto a plane containing the line. Such projections are often useful in CAD/CAM problems.
- Conic traits -
- Removed old traits class:
- The models of the
PlanarMapWithIntersectionsTraits_2concept below became obsolete, as the new conic traits, namely
Arr_conic_traits_2, supports the same functionality and is much more efficient.
- The models of the
- The segment traits class and the new polyline traits class were
reimplemented using standard CGAL-kernel calls. This essentially
eliminated the corresponding leda traits classes, namely:
- With the use of the Leda_rat_kernel new external package the same functionality can be achieved with less overhead and more efficiency.
- New interface functions to the
Planar_map_with_intersections_2class. The Planar_map_with_intersections_2 class maintains a planar map of input curves that possibly intersect each other and are not necessarily x-monotone. If an input curve, or a set of input curves, are known to be x-monotone and pairwise disjoint, the new functions below can be used to insert them into the map efficiently.
2D Sweep Line
Sweep_line_2package was reimplemented. As a consequence it is much more efficient, its traits is tighter (namely neither the two _left nor the reflection functions are required), and its interface has changed a bit.
- The following global functions have been removed:
- Instead, the public methods of the Sweep_line_2 class listed below were introduced:
get_subcurves()- Given a container of curves, this function returns a list of curves that are created by intersecting the input curves.
get_intersection_points()- Given a range of curves, this function returns a list of points that are the intersection points of the curves.
get_intersecting_curves()- Given a range of curves, this function returns an iterator to the beginning of a range that contains the list of curves for each intersection point between any two curves in the specified range.
- It is possible to construct a planar map with intersections (or an arrangement) by inserting a range of curves into an empty map. This will invoke the sweep-line process to construct the map more efficiently.
- The old design that was deprecated since CGAL 2.3 has been removed.
- Renamed local enum
RELATIVE_INDEXINGto avoid conflicts with similarly named macros of another library.
- Changed member functions
end_facet()to return useful handles.
test_facet()to check facets for validity before adding them.
vertex( size_t i)to return
Halfedge Data Structure
- The old design that was deprecated since CGAL 2.3 has been removed.
- New container class
Compact_container, which (roughly) provides the flexibility of
std::list, with the memory compactness of std::vector.
- Geomview_stream: added a function gv.draw_triangles(InputIterator begin, InputIterator end) which draws a set of triangles much more quickly than one by one.
- number types are now required to provide a function:
std::pair<double, double> to_interval(const NT&).
- number types are now required to provide mixed operators with “int”.
- CLN support removed.
- added Gmp_q.
- New classes:
Qt_help_window: provides a simple way to show some helpful information about a demo as an HTML page.
Qt_widget_history: provides basic functionality to manipulate intervals of
Qt_widgetclass. The current visible area of
Qt_widgetis mapped to an interval. Each interval could be stored in the
Qt_widget_historyobject. So you can use this object to navigate in history. It is mostly used by
- Qt_widget_standard_toolbar: is derived from QToolBar class, so pay attention to modify your code, if you used this class. Some public methods were introduced to control the history object that the toolbar use to navigate.
- The icons are now part of libCGALQt.
- Deprecated members of Qt_widget:
- The output operators of the following classes have been optimized:
CGAL::Segment_2(now tests for intersection with the drawing area)
CGAL::Triangle_2(now tests for intersection with the drawing area)
CGAL::Triangulation_2(is optimized for faster display on zooming)
Erratum in the Kernel manual
Intersection test routines
- The documentation of CGAL::do_intersect should mention, for the 3D case:
also, in three-dimensional space
Type1can be either
- In the same way, for
Kernel::DoIntersect_3: for all pairs
Type2, where the type
Type2can be any of the following:
- Philippe Guigue (INRIA Sophia-Antipolis) should be mentioned as one of the authors.