1 // Copyright (c) 2006,2007,2009,2010,2011 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/Arrangement_on_surface_2/include/CGAL/Arr_geometry_traits/de_Casteljau_2.h $
7 // $Id: de_Casteljau_2.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Ron Wein <wein@post.tau.ac.il>
12 // Iddo Hanniel <iddoh@cs.technion.ac.il>
13
14 #ifndef CGAL_DE_CASTELJAU_2_H
15 #define CGAL_DE_CASTELJAU_2_H
16
17 #include <CGAL/license/Arrangement_on_surface_2.h>
18
19
20 /*! \file
21 * Template functions for performing generic operations based on the
22 * de Casteljau algorithm.
23 */
24
25 #include <vector>
26
27 namespace CGAL {
28
29 /*!
30 * Bisect the control polygon of a given Bezier curve into the left and right
31 * control polygons.
32 * \param ctrl_pts_begin The beginning iterator of the control points of the
33 * curve.
34 * \param ctrl_pts_end The past-the-end iterator of the control points.
35 * \param left_ctrl_pts (out) The control points of the left polygon.
36 * \param right_ctrl_pts (out) The control points of the right polygon.
37 * Note: Typically you should call this function as follows:
38 * bisect_control_polygon_2(ctrl_pts.begin(), ctrl_pts.end(),
39 * std::back_inserter(left_pts),
40 * std::front_inserter(right_pts));
41 */
42 template <class InputIterator,
43 class OutputIterLeft, class OutputIterRight>
44 void
bisect_control_polygon_2(InputIterator ctrl_pts_begin,InputIterator ctrl_pts_end,OutputIterLeft left_ctrl_pts,OutputIterRight right_ctrl_pts)45 bisect_control_polygon_2(InputIterator ctrl_pts_begin,
46 InputIterator ctrl_pts_end,
47 OutputIterLeft left_ctrl_pts,
48 OutputIterRight right_ctrl_pts)
49 {
50 typedef typename InputIterator::value_type _Point_2;
51 typedef typename Kernel_traits<_Point_2>::Kernel _Kernel;
52 typedef typename _Kernel::Construct_midpoint_2 _Construct_midpoint_2;
53
54 // Grab a local copy of the control points.
55 const unsigned int n_pts = static_cast<unsigned int>(std::distance(ctrl_pts_begin, ctrl_pts_end));
56 CGAL_precondition(n_pts != 0);
57
58 std::vector<_Point_2> vec(n_pts);
59 InputIterator iter;
60 unsigned int i;
61
62 for (iter = ctrl_pts_begin, i = 0; iter != ctrl_pts_end; ++iter, ++i)
63 vec[i] = *iter;
64
65 // The first control point goes to the (front of) the right subcurve,
66 // while the last control point goes to the (back of) the left subcurve.
67 _Kernel ker;
68 _Construct_midpoint_2 midpoint = ker.construct_midpoint_2_object();
69 unsigned int last_index = n_pts - 1;
70
71 *left_ctrl_pts = vec[0];
72 ++left_ctrl_pts;
73
74 *right_ctrl_pts = vec[last_index];
75 ++right_ctrl_pts;
76
77 while (last_index > 0)
78 {
79 // Construct (m - 1) control points from the m point we currently have,
80 // where the new i'th point is the midpoint between p[i] and p[i + 1].
81 for (i = 0; i < last_index; ++i)
82 vec[i] = midpoint(vec[i], vec[i + 1]);
83
84 --last_index;
85
86 // The first control points goes to the (front of) the right subcurve,
87 // while the last control point goes to the (back of) the left subcurve.
88 *left_ctrl_pts = vec[0];
89 ++left_ctrl_pts;
90
91 *right_ctrl_pts = vec[last_index];
92 ++right_ctrl_pts;
93 }
94
95 return;
96 }
97
98 /*!
99 * Evaluate a point on a parametric Bezier curve B(t) using de Casteljau's
100 * algorithm.
101 * \param ctrl_pts_begin The beginning iterator of the control points of the
102 * curve.
103 * \param ctrl_pts_end The past-the-end iterator of the control points.
104 * \param t0 The parameter value at the requested point.
105 * \return The point B(t0).
106 */
107 template <class InputIterator>
point_on_Bezier_curve_2(InputIterator ctrl_pts_begin,InputIterator ctrl_pts_end,const typename Kernel_traits<typename InputIterator::value_type>::Kernel::FT & t0)108 typename InputIterator::value_type point_on_Bezier_curve_2
109 (InputIterator ctrl_pts_begin,
110 InputIterator ctrl_pts_end,
111 const typename Kernel_traits<typename InputIterator::value_type>::Kernel::FT&
112 t0)
113 {
114 typedef typename InputIterator::value_type _Point_2;
115 typedef typename Kernel_traits<_Point_2>::Kernel _Kernel;
116 typedef typename _Kernel::FT _NT;
117
118 // Grab a local copy of the control points.
119 const unsigned int n_pts = static_cast<unsigned int>(std::distance(ctrl_pts_begin, ctrl_pts_end));
120 CGAL_precondition(n_pts != 0);
121
122 std::vector<_Point_2> vec(n_pts);
123 InputIterator iter;
124 unsigned int i;
125
126 for (iter = ctrl_pts_begin, i = 0; iter != ctrl_pts_end; ++iter, ++i)
127 vec[i] = *iter;
128
129 // The first control point goes to the (front of) the right subcurve,
130 // while the last control point goes to the (back of) the left subcurve.
131 const _NT comp_t0 = _NT(1) - t0;
132 unsigned int last_index = n_pts - 1;
133
134 while (last_index > 0)
135 {
136 // Construct (m - 1) control points from the m point we currently have,
137 // where the new i'th point is given by: (1 - t0)*p[i] + t0*p[i + 1].
138 for (i = 0; i < last_index; ++i)
139 {
140 vec[i] = _Point_2(comp_t0*vec[i].x() + t0*vec[i + 1].x(),
141 comp_t0*vec[i].y() + t0*vec[i + 1].y());
142 }
143
144 --last_index;
145 }
146
147 // Our auxiliary vector now contains just a single entry, and this entry
148 // is the curve value at t0.
149 return (vec[0]);
150 }
151
152 /*!
153 * Evaluate a point on a parametric Bezier curve B(t) using de Casteljau's
154 * algorithm, and also bisect the control polygon of B at this point.
155 * \param ctrl_pts_begin The beginning iterator of the control points of the
156 * curve.
157 * \param ctrl_pts_end The past-the-end iterator of the control points.
158 * \param t0 The parameter value at the requested point.
159 * \param left_ctrl_pts (out) The control points of the left polygon.
160 * \param right_ctrl_pts (out) The control points of the right polygon.
161 * \return The point B(t0).
162 */
163 template <class InputIterator,
164 class OutputIterLeft, class OutputIterRight>
de_Casteljau_2(InputIterator ctrl_pts_begin,InputIterator ctrl_pts_end,const typename Kernel_traits<typename InputIterator::value_type>::Kernel::FT & t0,OutputIterLeft left_ctrl_pts,OutputIterRight right_ctrl_pts)165 typename InputIterator::value_type de_Casteljau_2
166 (InputIterator ctrl_pts_begin, InputIterator ctrl_pts_end,
167 const typename Kernel_traits<typename InputIterator::value_type>::Kernel::FT&
168 t0,
169 OutputIterLeft left_ctrl_pts, OutputIterRight right_ctrl_pts)
170 {
171 typedef typename InputIterator::value_type _Point_2;
172 typedef typename Kernel_traits<_Point_2>::Kernel _Kernel;
173 typedef typename _Kernel::FT _NT;
174
175 // Grab a local copy of the control points.
176 const unsigned int n_pts = static_cast<unsigned int>(std::distance(ctrl_pts_begin, ctrl_pts_end));
177 CGAL_precondition(n_pts != 0);
178
179 std::vector<_Point_2> vec(n_pts);
180 InputIterator iter;
181 unsigned int i;
182
183 for (iter = ctrl_pts_begin, i = 0; iter != ctrl_pts_end; ++iter, ++i)
184 vec[i] = *iter;
185
186 // The first control point goes to the (front of) the right subcurve,
187 // while the last control point goes to the (back of) the left subcurve.
188 const _NT comp_t0 = _NT(1) - t0;
189 unsigned int last_index = n_pts - 1;
190
191 *left_ctrl_pts = vec[0];
192 ++left_ctrl_pts;
193
194 *right_ctrl_pts = vec[last_index];
195 ++right_ctrl_pts;
196
197 while (last_index > 0)
198 {
199 // Construct (m - 1) control points from the m point we currently have,
200 // where the new i'th point is given by: (1 - t0)*p[i] + t0*p[i + 1].
201 for (i = 0; i < last_index; ++i)
202 {
203 vec[i] = _Point_2(comp_t0*vec[i].x() + t0*vec[i + 1].x(),
204 comp_t0*vec[i].y() + t0*vec[i + 1].y());
205 }
206 --last_index;
207
208 // The first control points goes to the (front of) the right subcurve,
209 // while the last control point goes to the (back of) the left subcurve.
210 *left_ctrl_pts = vec[0];
211 ++left_ctrl_pts;
212
213 *right_ctrl_pts = vec[last_index];
214 ++right_ctrl_pts;
215 }
216
217 // Our auxiliary vector now contains just a single entry, and this entry
218 // is the curve value at t0.
219 return (vec[0]);
220 }
221
222 } //namespace CGAL
223
224 #endif
225