// Copyright (c) 2005,2006,2007,2009,2010,2011 Tel-Aviv University (Israel). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Surface_sweep_2/include/CGAL/Surface_sweep_2_algorithms.h $ // $Id: Surface_sweep_2_algorithms.h 254d60f 2019-10-19T15:23:19+02:00 Sébastien Loriot // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // // Author(s): Baruch Zukerman // Efi Fogel // (based on old version by Tali Zvi) #ifndef CGAL_SURFACE_SWEEP_2_ALGORITHMS_H #define CGAL_SURFACE_SWEEP_2_ALGORITHMS_H #include /*! File * * \file Definition of the surface-sweep related functions. */ #include #include #include #include #include #include #include #include #include #include namespace CGAL { namespace Ss2 = Surface_sweep_2; template struct Default_arr_traits {}; template struct Default_arr_traits > { typedef CGAL::Arr_segment_traits_2 Traits; }; template struct Default_arr_traits > { typedef CGAL::Arr_segment_traits_2 Traits; }; template struct Default_arr_traits > { typedef CGAL::Arr_polyline_traits_2 Traits; }; template struct Default_arr_traits > { typedef CGAL::Arr_conic_traits_2 Traits; }; template class Arr_rational_function_traits_2; namespace Arr_rational_arc{ template class Rational_arc_d_1; } template struct Default_arr_traits > { typedef CGAL::Arr_rational_function_traits_2 Traits; }; template struct Default_arr_traits > { typedef CGAL::Arr_circle_segment_traits_2 Traits; }; template struct Default_arr_traits > { typedef CGAL::Arr_linear_traits_2 Traits; }; /*! Compute all intersection points induced by a range of input curves. * The intersections are calculated using the surface-sweep algorithm. * \param begin An input iterator for the first curve in the range. * \param end A input past-the-end iterator for the range. * \param points Output: An output iterator for the intersection points * induced by the input curves. * \param report_endpoints If (true), the end points of the curves are also * reported as intersection points. * \pre The value-type of CurveInputIterator is Traits::Curve_2, and the * value-type of OutputIterator is Traits::Point_2. */ template OutputIterator compute_intersection_points(CurveInputIterator curves_begin, CurveInputIterator curves_end, OutputIterator points, bool report_endpoints, Traits &tr) { // Define the surface-sweep types: typedef Ss2::Intersection_points_visitor Visitor; typedef Ss2::Surface_sweep_2 Surface_sweep; // Perform the sweep and obtain the intersection points. Visitor visitor(points, report_endpoints); Surface_sweep surface_sweep(&tr, &visitor); visitor.sweep(curves_begin, curves_end); return visitor.output_iterator(); } template OutputIterator compute_intersection_points(CurveInputIterator curves_begin, CurveInputIterator curves_end, OutputIterator points, bool report_endpoints = false) { typedef typename std::iterator_traits::value_type Curve; typename Default_arr_traits::Traits traits; return compute_intersection_points(curves_begin, curves_end, points, report_endpoints, traits); } /*! Compute all x-monotone subcurves that are disjoint in their interiors * induced by a range of input curves. * The subcurves are calculated using the surface-sweep algorithm. * \param begin An input iterator for the first curve in the range. * \param end A input past-the-end iterator for the range. * \param points Output: An output iterator for the subcurve. * \param mult_overlaps If (true), the overlapping subcurve will be reported * multiple times. * \pre The value-type of CurveInputIterator is Traits::Curve_2, and the * value-type of OutputIterator is Traits::X_monotone_curve_2. */ template OutputIterator compute_subcurves(CurveInputIterator curves_begin, CurveInputIterator curves_end, OutputIterator subcurves, bool mult_overlaps, Traits& tr) { // Define the surface-sweep types: typedef Ss2::Subcurves_visitor Visitor; typedef Ss2::Surface_sweep_2 Surface_sweep; // Perform the sweep and obtain the subcurves. Visitor visitor(subcurves, mult_overlaps); Surface_sweep surface_sweep(&tr, &visitor); visitor.sweep(curves_begin, curves_end); return visitor.output_iterator(); } template OutputIterator compute_subcurves(CurveInputIterator curves_begin, CurveInputIterator curves_end, OutputIterator subcurves, bool mult_overlaps = false) { typedef typename std::iterator_traits::value_type Curve; typename Default_arr_traits::Traits m_traits; return compute_subcurves(curves_begin, curves_end, subcurves, mult_overlaps, m_traits); } /*! Determine if there occurs an intersection between any pair of curves in * a given range. * \param begin An input iterator for the first curve in the range. * \param end A input past-the-end iterator for the range. * \return (true) if any pair of curves intersect; (false) otherwise. */ template bool do_curves_intersect(CurveInputIterator curves_begin, CurveInputIterator curves_end, Traits& tr) { // Define the surface-sweep types: typedef Ss2::Do_interior_intersect_visitor Visitor; typedef Ss2::Surface_sweep_2 Surface_sweep; // Perform the sweep and obtain the subcurves. Visitor visitor; Surface_sweep surface_sweep(&tr, &visitor); visitor.sweep(curves_begin, curves_end); return visitor.found_intersection(); } template bool do_curves_intersect(CurveInputIterator curves_begin, CurveInputIterator curves_end) { typedef typename std::iterator_traits::value_type Curve; typename Default_arr_traits::Traits m_traits; return do_curves_intersect(curves_begin, curves_end, m_traits); } } // namespace CGAL #endif