1
// Copyright (c) 2007-09 INRIA Sophia-Antipolis (France).
2
// All rights reserved.
4
// This file is part of CGAL (www.cgal.org).
5
// You can redistribute it and/or modify it under the terms of the GNU
6
// General Public License as published by the Free Software Foundation,
7
// either version 3 of the License, or (at your option) any later version.
9
// Licensees holding a valid commercial license may use this file in
10
// accordance with the commercial license agreement provided with the software.
12
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
13
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18
// Author(s) : Pierre Alliez, Marc Pouget and Laurent Saboret
20
#ifndef CGAL_JET_SMOOTH_POINT_SET_H
21
#define CGAL_JET_SMOOTH_POINT_SET_H
23
#include <CGAL/trace.h>
24
#include <CGAL/Search_traits_3.h>
25
#include <CGAL/Orthogonal_k_neighbor_search.h>
26
#include <CGAL/Monge_via_jet_fitting.h>
27
#include <CGAL/property_map.h>
28
#include <CGAL/point_set_processing_assertions.h>
36
// ----------------------------------------------------------------------------
38
// ----------------------------------------------------------------------------
41
/// \cond SKIP_IN_MANUAL
43
/// Smoothes one point position using jet fitting on the k
44
/// nearest neighbors and reprojection onto the jet.
48
/// @tparam Kernel Geometric traits class.
49
/// @tparam Tree KD-tree.
51
/// @return computed point
52
template <typename Kernel,
54
typename Kernel::Point_3
56
const typename Kernel::Point_3& query, ///< 3D point to project
57
Tree& tree, ///< KD-tree
58
const unsigned int k, ///< number of neighbors.
59
const unsigned int degree_fitting,
60
const unsigned int degree_monge)
62
// basic geometric types
63
typedef typename Kernel::Point_3 Point;
65
// types for K nearest neighbors search
66
typedef typename CGAL::Search_traits_3<Kernel> Tree_traits;
67
typedef typename CGAL::Orthogonal_k_neighbor_search<Tree_traits> Neighbor_search;
68
typedef typename Neighbor_search::iterator Search_iterator;
70
// types for jet fitting
71
typedef typename CGAL::Monge_via_jet_fitting<Kernel> Monge_jet_fitting;
72
typedef typename Monge_jet_fitting::Monge_form Monge_form;
74
// Gather set of (k+1) neighboring points.
75
// Performs k + 1 queries (if unique the query point is
76
// output first). Search may be aborted if k is greater
77
// than number of input points.
78
std::vector<Point> points; points.reserve(k+1);
79
Neighbor_search search(tree,query,k+1);
80
Search_iterator search_iterator = search.begin();
84
if(search_iterator == search.end())
85
break; // premature ending
86
points.push_back(search_iterator->first);
89
CGAL_point_set_processing_precondition(points.size() >= 1);
91
// performs jet fitting
92
Monge_jet_fitting monge_fit;
93
Monge_form monge_form = monge_fit(points.begin(), points.end(),
94
degree_fitting, degree_monge);
96
// output projection of query point onto the jet
97
return monge_form.origin();
102
} /* namespace internal */
105
// ----------------------------------------------------------------------------
107
// ----------------------------------------------------------------------------
109
/// \ingroup PkgPointSetProcessing
110
/// Smoothes the `[first, beyond)` range of points using jet fitting on the k
111
/// nearest neighbors and reprojection onto the jet.
112
/// As this method relocates the points, it
113
/// should not be called on containers sorted w.r.t. point locations.
117
/// @tparam InputIterator iterator over input points.
118
/// @tparam PointPMap is a model of `ReadWritePropertyMap` with a value_type = Point_3<Kernel>.
119
/// It can be omitted if InputIterator value_type is convertible to Point_3<Kernel>.
120
/// @tparam Kernel Geometric traits class.
121
/// It can be omitted and deduced automatically from PointPMap value_type.
123
// This variant requires all parameters.
124
template <typename InputIterator,
129
jet_smooth_point_set(
130
InputIterator first, ///< iterator over the first input point.
131
InputIterator beyond, ///< past-the-end iterator over the input points.
132
PointPMap point_pmap, ///< property map: value_type of InputIterator -> Point_3.
133
unsigned int k, ///< number of neighbors.
134
const Kernel& /*kernel*/, ///< geometric traits.
135
unsigned int degree_fitting = 2, ///< fitting degree
136
unsigned int degree_monge = 2) ///< Monge degree
138
// basic geometric types
139
typedef typename Kernel::Point_3 Point;
141
// types for K nearest neighbors search structure
142
typedef typename CGAL::Search_traits_3<Kernel> Tree_traits;
143
typedef typename CGAL::Orthogonal_k_neighbor_search<Tree_traits> Neighbor_search;
144
typedef typename Neighbor_search::Tree Tree;
146
// precondition: at least one element in the container.
147
// to fix: should have at least three distinct points
148
// but this is costly to check
149
CGAL_point_set_processing_precondition(first != beyond);
151
// precondition: at least 2 nearest neighbors
152
CGAL_point_set_processing_precondition(k >= 2);
156
// Instanciate a KD-tree search.
157
// Note: We have to convert each input iterator to Point_3.
158
std::vector<Point> kd_tree_points;
159
for(it = first; it != beyond; it++)
161
#ifdef CGAL_USE_PROPERTY_MAPS_API_V1
162
Point point = get(point_pmap, it);
164
Point point = get(point_pmap, *it);
166
kd_tree_points.push_back(point);
168
Tree tree(kd_tree_points.begin(), kd_tree_points.end());
170
// Iterates over input points and mutates them.
171
// Implementation note: the cast to Point& allows to modify only the point's position.
172
for(it = first; it != beyond; it++)
174
#ifdef CGAL_USE_PROPERTY_MAPS_API_V1
175
const Point& p = get(point_pmap, it);
177
internal::jet_smooth_point<Kernel>(p,tree,k,degree_fitting,degree_monge) );
179
const Point& p = get(point_pmap, *it);
180
put(point_pmap, *it ,
181
internal::jet_smooth_point<Kernel>(p,tree,k,degree_fitting,degree_monge) );
186
/// @cond SKIP_IN_MANUAL
187
// This variant deduces the kernel from the point property map.
188
template <typename InputIterator,
192
jet_smooth_point_set(
193
InputIterator first, ///< iterator over the first input point
194
InputIterator beyond, ///< past-the-end iterator
195
PointPMap point_pmap, ///< property map: value_type of InputIterator -> Point_3
196
unsigned int k, ///< number of neighbors.
197
const unsigned int degree_fitting = 2,
198
const unsigned int degree_monge = 2)
200
typedef typename boost::property_traits<PointPMap>::value_type Point;
201
typedef typename Kernel_traits<Point>::Kernel Kernel;
202
jet_smooth_point_set(
207
degree_fitting,degree_monge);
211
/// @cond SKIP_IN_MANUAL
212
// This variant creates a default point property map = Identity_property_map.
213
template <typename InputIterator
216
jet_smooth_point_set(
217
InputIterator first, ///< iterator over the first input point
218
InputIterator beyond, ///< past-the-end iterator
219
unsigned int k, ///< number of neighbors.
220
const unsigned int degree_fitting = 2,
221
const unsigned int degree_monge = 2)
223
jet_smooth_point_set(
225
#ifdef CGAL_USE_PROPERTY_MAPS_API_V1
226
make_dereference_property_map(first),
228
make_identity_property_map(
229
typename std::iterator_traits<InputIterator>::value_type()),
232
degree_fitting,degree_monge);
239
#endif // CGAL_JET_SMOOTH_POINT_SET_H