More formally the problem can be defined as follows.
Given a finite set of points, compute a point set with such that the p-radius of ,
is minimized. We can interpret as the best approximation (with respect to the given metric) for with at most p points.
#include <CGAL/rectangular_p_center_2.h>
| ||||||
|
|
computes rectilinear p-centers for the point set described by the range [f, l), sets r to the corresponding -radius, writes the at most p center points to o and returns the past-the-end iterator of this sequence.
On compilers not supporting member function templates, the parameter ForwardIterator is fixed to vector<Point_2>::iterator and OutputIterator is fixed to back_insert_iterator<vector<Point_2>> where Point_2 is Traits::Point_2.
#include <CGAL/Cartesian.h> #include <CGAL/Point_2.h> #include <CGAL/point_generators_2.h> #include <CGAL/rectangular_p_center_2.h> #include <CGAL/copy_n.h> #include <CGAL/IO/Ostream_iterator.h> #include <iostream.h> #include <vector.h> typedef double FT; typedef CGAL_Cartesian< FT > R; typedef CGAL_Point_2< R > Point_2; typedef vector< Point_2 > Cont; typedef CGAL_Random_points_in_square_2< Point_2, CGAL_Creator_uniform_2< FT, Point_2 > > Point_generator; typedef CGAL_Ostream_iterator< Point_2, ostream > Ostream_iterator_point; int main() { int number_of_points( 10); int p( 2); Ostream_iterator_point cout_ip( cout); CGAL_set_pretty_mode( cout); Cont points; CGAL_copy_n( Point_generator( 1), number_of_points, back_inserter( points)); cout << "Generated Point Set:" << endl; copy( points.begin(), points.end(), cout_ip); Cont centers; FT p_radius; CGAL_rectangular_p_center_2( points.begin(), points.end(), back_inserter( centers), p_radius, p); cout << "\n\n" << p << "-centers:" << endl; copy( centers.begin(), centers.end(), cout_ip); cout << "\n\n" << p << "-radius = " << p_radius << endl; }