1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
// 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/v6.1.1/Surface_sweep_2/include/CGAL/Surface_sweep_2_algorithms.h $
// $Id: include/CGAL/Surface_sweep_2_algorithms.h 08b27d3db14 $
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
//
//
// Author(s): Baruch Zukerman <baruchzu@post.tau.ac.il>
// Efi Fogel <efif@post.tau.ac.il>
// (based on old version by Tali Zvi)
#ifndef CGAL_SURFACE_SWEEP_2_ALGORITHMS_H
#define CGAL_SURFACE_SWEEP_2_ALGORITHMS_H
#include <CGAL/license/Surface_sweep_2.h>
/*! File
*
* \file Definition of the surface-sweep related functions.
*/
#include <CGAL/Surface_sweep_2.h>
#include <CGAL/Surface_sweep_2/Intersection_points_visitor.h>
#include <CGAL/Surface_sweep_2/Subcurves_visitor.h>
#include <CGAL/Surface_sweep_2/Do_interior_intersect_visitor.h>
#include <CGAL/Segment_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arr_polyline_traits_2.h>
#include <CGAL/Arr_conic_traits_2.h>
#include <CGAL/Arr_circle_segment_traits_2.h>
#include <CGAL/Arr_linear_traits_2.h>
#include <CGAL/Arr_polyline_traits_2.h>
namespace CGAL {
namespace Ss2 = Surface_sweep_2;
template <typename Curve>
struct Default_arr_traits
{};
template <typename Kernel>
struct Default_arr_traits<CGAL::Segment_2<Kernel> >
{
typedef CGAL::Arr_segment_traits_2<Kernel> Traits;
};
template <typename Kernel>
struct Default_arr_traits<CGAL::Arr_segment_2<Kernel> >
{
typedef CGAL::Arr_segment_traits_2<Kernel> Traits;
};
template <typename Kernel>
struct Default_arr_traits<CGAL::internal::Polycurve_2<
CGAL::Arr_segment_2<Kernel>,
typename Kernel::Point_2>>
{
using Subtraits = CGAL::Arr_segment_traits_2<Kernel>;
typedef CGAL::Arr_polyline_traits_2<Subtraits> Traits;
};
template <typename Rat_kernel_, class Alg_kernel_, class Nt_traits_>
struct Default_arr_traits<CGAL::Conic_arc_2<Rat_kernel_, Alg_kernel_,
Nt_traits_> >
{
typedef CGAL::Arr_conic_traits_2<Rat_kernel_, Alg_kernel_, Nt_traits_>
Traits;
};
template <typename AlgebraicKernel_d_1>
class Arr_rational_function_traits_2;
namespace Arr_rational_arc{
template <typename Algebraic_kernel_>
class Rational_arc_d_1;
}
template <typename Algebraic_kernel_>
struct Default_arr_traits<CGAL::Arr_rational_arc::
Rational_arc_d_1<Algebraic_kernel_> >
{
typedef CGAL::Arr_rational_function_traits_2<Algebraic_kernel_> Traits;
};
template <typename Kernel_, bool Filter_>
struct Default_arr_traits<CGAL::_Circle_segment_2<Kernel_, Filter_> >
{
typedef CGAL::Arr_circle_segment_traits_2<Kernel_, Filter_> Traits;
};
template <typename Kernel>
struct Default_arr_traits<CGAL::Arr_linear_object_2<Kernel> >
{
typedef CGAL::Arr_linear_traits_2<Kernel> 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 <typename CurveInputIterator, typename OutputIterator, typename Traits>
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<Traits, OutputIterator>
Visitor;
typedef Ss2::Surface_sweep_2<Visitor> 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 <typename CurveInputIterator, typename OutputIterator>
OutputIterator compute_intersection_points(CurveInputIterator curves_begin,
CurveInputIterator curves_end,
OutputIterator points,
bool report_endpoints = false)
{
typedef typename std::iterator_traits<CurveInputIterator>::value_type Curve;
typename Default_arr_traits<Curve>::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 <typename CurveInputIterator, typename OutputIterator, typename Traits>
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<Traits, OutputIterator> Visitor;
typedef Ss2::Surface_sweep_2<Visitor> 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 <typename CurveInputIterator, typename OutputIterator>
OutputIterator compute_subcurves(CurveInputIterator curves_begin,
CurveInputIterator curves_end,
OutputIterator subcurves,
bool mult_overlaps = false)
{
typedef typename std::iterator_traits<CurveInputIterator>::value_type Curve;
typename Default_arr_traits<Curve>::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 <typename CurveInputIterator, typename Traits>
bool do_curves_intersect(CurveInputIterator curves_begin,
CurveInputIterator curves_end, Traits& tr)
{
// Define the surface-sweep types:
typedef Ss2::Do_interior_intersect_visitor<Traits> Visitor;
typedef Ss2::Surface_sweep_2<Visitor> 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 <typename CurveInputIterator>
bool do_curves_intersect(CurveInputIterator curves_begin,
CurveInputIterator curves_end)
{
typedef typename std::iterator_traits<CurveInputIterator>::value_type Curve;
typename Default_arr_traits<Curve>::Traits m_traits;
return do_curves_intersect(curves_begin, curves_end, m_traits);
}
} // namespace CGAL
#endif
|
