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
|
// Copyright (c) 2005 Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.2-branch/Arrangement_2/include/CGAL/Sweep_line_2_algorithms.h $
// $Id: Sweep_line_2_algorithms.h 28567 2006-02-16 14:30:13Z lsaboret $
//
//
// Author(s) : Baruch Zukerman <baruchzu@post.tau.ac.il>
// (based on old version by Tali Zvi)
#ifndef CGAL_SWEEP_LINE_2_ALGORITHMS_H
#define CGAL_SWEEP_LINE_2_ALGORITHMS_H
/*!
* \file Definition of the sweep-line related functions.
*/
#include <CGAL/Sweep_line_2.h>
#include <CGAL/Sweep_line_2/Sweep_line_2_visitors.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_rational_arc_traits_2.h>
#include <CGAL/Arr_circle_segment_traits_2.h>
CGAL_BEGIN_NAMESPACE
template <class Curve>
struct Default_arr_traits
{};
template <class Kernel>
struct Default_arr_traits<CGAL::Segment_2<Kernel> >
{
typedef CGAL::Arr_segment_traits_2<Kernel> Traits;
};
template <class Kernel>
struct Default_arr_traits<CGAL::Arr_segment_2<Kernel> >
{
typedef CGAL::Arr_segment_traits_2<Kernel> Traits;
};
template <class SegTraits>
struct Default_arr_traits<CGAL::_Polyline_2<SegTraits> >
{
typedef CGAL::Arr_polyline_traits_2<SegTraits> Traits;
};
template <class 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 <class Alg_kernel_, class Nt_traits_>
struct Default_arr_traits<CGAL::_Rational_arc_2<Alg_kernel_, Nt_traits_> >
{
typedef CGAL::Arr_rational_arc_traits_2<Alg_kernel_, Nt_traits_> Traits;
};
template <class Kernel_, bool Filter_>
struct Default_arr_traits<CGAL::_Circle_segment_2<Kernel_, Filter_> >
{
typedef CGAL::Arr_circle_segment_traits_2<Kernel_, Filter_> Traits;
};
/*!
* Compute all intersection points induced by a range of input curves.
* The intersections are calculated using the sweep-line 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 <class CurveInputIterator, class OutputIterator, class Traits>
OutputIterator get_intersection_points (CurveInputIterator curves_begin,
CurveInputIterator curves_end,
OutputIterator points,
bool report_endpoints,
Traits &tr)
{
// Define the sweep-line types:
typedef Sweep_line_points_visitor<Traits,OutputIterator> Visitor;
typedef Sweep_line_2< Traits,
Sweep_line_points_visitor<Traits,
OutputIterator> >
Sweep_line;
// Perform the sweep and obtain the intersection points.
Visitor visitor (points, report_endpoints);
Sweep_line sweep_line (&tr, &visitor);
visitor.sweep(curves_begin, curves_end);
return (visitor.get_output_iterator());
}
template <class CurveInputIterator, class OutputIterator>
OutputIterator get_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 tr;
return (get_intersection_points(curves_begin,
curves_end,
points,
report_endpoints,
tr));
}
/*!
* Compute all x-monotone subcurves that are disjoint in their interiors
* induced by a range of input curves.
* The subcurves are calculated using the sweep-line 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 <class CurveInputIterator, class OutputIterator, class Traits>
OutputIterator get_subcurves (CurveInputIterator curves_begin,
CurveInputIterator curves_end,
OutputIterator subcurves,
bool mult_overlaps,
Traits &tr)
{
// Define the sweep-line types:
typedef Sweep_line_subcurves_visitor<Traits, OutputIterator> Visitor;
typedef Sweep_line_2<Traits,
Sweep_line_subcurves_visitor<Traits,
OutputIterator> >
Sweep_line;
// Perform the sweep and obtain the subcurves.
Visitor visitor (subcurves, mult_overlaps);
Sweep_line sweep_line (&tr, &visitor);
visitor.sweep(curves_begin, curves_end);
return (visitor.get_output_iterator());
}
template <class CurveInputIterator, class OutputIterator>
OutputIterator get_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 tr;
return (get_subcurves(curves_begin,
curves_end,
subcurves,
mult_overlaps,
tr));
}
/*!
* 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 <class CurveInputIterator, class Traits>
bool do_curves_intersect (CurveInputIterator curves_begin,
CurveInputIterator curves_end,
Traits &tr)
{
// Define the sweep-line types:
typedef Sweep_line_do_curves_x_visitor<Traits> Visitor;
typedef Sweep_line_2<Traits,
Sweep_line_do_curves_x_visitor<Traits> >
Sweep_line ;
// Perform the sweep and obtain the subcurves.
Visitor visitor;
Sweep_line sweep_line (&tr, &visitor);
visitor.sweep(curves_begin, curves_end);
return (visitor.found_x());
}
template <class 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 tr;
return (do_curves_intersect(curves_begin, curves_end, tr));
}
CGAL_END_NAMESPACE
#endif
|
