1 // Copyright (c) 2006 Tel-Aviv University (Israel).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Envelope_2/include/CGAL/envelope_2.h $
7 // $Id: envelope_2.h a46398d 2020-08-25T13:43:49+02:00 Ahmed Essam
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 // Author(s) : Ron Wein <wein@post.tau.ac.il>
11
12 #ifndef CGAL_ENVELOPE_2_H
13 #define CGAL_ENVELOPE_2_H
14
15 #include <CGAL/license/Envelope_2.h>
16
17
18 /*! \file
19 * Global functions for computing lower and upper envelopes of curves in the
20 * plane.
21 */
22
23 #include <CGAL/Envelope_2/Env_divide_and_conquer_2.h>
24
25 namespace CGAL {
26
27 /*!
28 * Compute the lower envelope of a range of curves.
29 * \param begin An iterator for the first curve.
30 * \param end A past-the-end iterator for the curves.
31 * \param diag Output: The minimization diagram.
32 * \pre The value-type of the iterator is Traits::Curve_2.
33 */
34 template <class InputIterator, class EnvelopeDiagram>
lower_envelope_2(InputIterator begin,InputIterator end,EnvelopeDiagram & diag)35 void lower_envelope_2 (InputIterator begin, InputIterator end,
36 EnvelopeDiagram& diag)
37 {
38 typedef typename EnvelopeDiagram::Traits_2 Traits_2;
39 typedef Envelope_divide_and_conquer_2<Traits_2, EnvelopeDiagram> Envelope_2;
40
41 Envelope_2 env;
42
43 env.insert_curves (begin, end,
44 true, // Lower envelope.
45 diag);
46
47 return;
48 }
49
50 /*!
51 * Compute the upper envelope of a range of curves.
52 * \param begin An iterator for the first curve.
53 * \param end A past-the-end iterator for the curves.
54 * \param diag Output: The maximization diagram.
55 * \pre The value-type of the iterator is Traits::Curve_2.
56 */
57 template <class InputIterator, class EnvelopeDiagram>
upper_envelope_2(InputIterator begin,InputIterator end,EnvelopeDiagram & diag)58 void upper_envelope_2 (InputIterator begin, InputIterator end,
59 EnvelopeDiagram& diag)
60 {
61 typedef typename EnvelopeDiagram::Traits_2 Traits_2;
62 typedef Envelope_divide_and_conquer_2<Traits_2, EnvelopeDiagram> Envelope_2;
63
64 Envelope_2 env;
65
66 env.insert_curves (begin, end,
67 false, // Upper envelope.
68 diag);
69
70 return;
71 }
72
73 /*!
74 * Compute the lower envelope of a range of x-monotone curves.
75 * \param begin An iterator for the first x-monotone curve.
76 * \param end A past-the-end iterator for the x-monotone curves.
77 * \param diag Output: The minimization diagram.
78 * \pre The value-type of the iterator is Traits::X_monotone_curve_2.
79 */
80 template <class InputIterator, class EnvelopeDiagram>
lower_envelope_x_monotone_2(InputIterator begin,InputIterator end,EnvelopeDiagram & diag)81 void lower_envelope_x_monotone_2 (InputIterator begin, InputIterator end,
82 EnvelopeDiagram& diag)
83 {
84 typedef typename EnvelopeDiagram::Traits_2 Traits_2;
85 typedef Envelope_divide_and_conquer_2<Traits_2, EnvelopeDiagram> Envelope_2;
86
87 Envelope_2 env;
88
89 env.insert_x_monotone_curves (begin, end,
90 true, // Lower envelope.
91 diag);
92
93 return;
94 }
95
96 /*!
97 * Compute the lower envelope of a range of x-monotone curves.
98 * \param begin An iterator for the first x-monotone curve.
99 * \param end A past-the-end iterator for the x-monotone curves.
100 * \param diag Output: The minimization diagram.
101 * \param traits The arrangement traits responsible for the x-monotone curves.
102 * \pre The value-type of the iterator is Traits::X_monotone_curve_2.
103 */
104 template <class InputIterator, class EnvelopeDiagram, class Traits>
lower_envelope_x_monotone_2(InputIterator begin,InputIterator end,EnvelopeDiagram & diag,const Traits & traits)105 void lower_envelope_x_monotone_2 (InputIterator begin, InputIterator end,
106 EnvelopeDiagram& diag, const Traits& traits)
107 {
108 typedef typename EnvelopeDiagram::Traits_2 Traits_2;
109 typedef Envelope_divide_and_conquer_2<Traits_2, EnvelopeDiagram> Envelope_2;
110
111 Envelope_2 env{&traits};
112
113 env.insert_x_monotone_curves (begin, end,
114 true, // Lower envelope.
115 diag);
116
117 return;
118 }
119
120 /*!
121 * Compute the upper envelope of a range of x-monotone curves.
122 * \param begin An iterator for the first x-monotone curve.
123 * \param end A past-the-end iterator for the x-monotone curves.
124 * \param diag Output: The maximization diagram.
125 * \pre The value-type of the iterator is Traits::X_monotone_curve_2.
126 */
127 template <class InputIterator, class EnvelopeDiagram>
upper_envelope_x_monotone_2(InputIterator begin,InputIterator end,EnvelopeDiagram & diag)128 void upper_envelope_x_monotone_2 (InputIterator begin, InputIterator end,
129 EnvelopeDiagram& diag)
130 {
131 typedef typename EnvelopeDiagram::Traits_2 Traits_2;
132 typedef Envelope_divide_and_conquer_2<Traits_2, EnvelopeDiagram> Envelope_2;
133
134 Envelope_2 env;
135
136 env.insert_x_monotone_curves (begin, end,
137 false, // Upper envelope.
138 diag);
139
140 return;
141 }
142
143 /*!
144 * Compute the upper envelope of a range of x-monotone curves.
145 * \param begin An iterator for the first x-monotone curve.
146 * \param end A past-the-end iterator for the x-monotone curves.
147 * \param diag Output: The maximization diagram.
148 * \param traits The arrangement traits responsible for the x-monotone curves.
149 * \pre The value-type of the iterator is Traits::X_monotone_curve_2.
150 */
151 template <class InputIterator, class EnvelopeDiagram, class Traits>
upper_envelope_x_monotone_2(InputIterator begin,InputIterator end,EnvelopeDiagram & diag,const Traits & traits)152 void upper_envelope_x_monotone_2 (InputIterator begin, InputIterator end,
153 EnvelopeDiagram& diag, const Traits& traits)
154 {
155 typedef typename EnvelopeDiagram::Traits_2 Traits_2;
156 typedef Envelope_divide_and_conquer_2<Traits_2, EnvelopeDiagram> Envelope_2;
157
158 Envelope_2 env{&traits};
159
160 env.insert_x_monotone_curves (begin, end,
161 false, // Upper envelope.
162 diag);
163
164 return;
165 }
166
167 } //namespace CGAL
168
169 #endif
170