CGAL::rectangular_p_center_2

Definition

L

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 $$p-radius, writes the at most p center points to o and returns the past-the-end iterator of this sequence.

Precondition

1. The range [f, l) is not empty.
2. 2 $$ p $$ 4.

The geometric types and operations to be used for the computation are specified by the traits class parameter t. This parameter can be omitted if ForwardIterator refers to a point type from the 2D-Kernel. In this case, a default traits class (Rectangular_p_center_default_traits_2<K>) is used.

Requirement

1. Either: (if no traits parameter is given) Value type of ForwardIterator is CGAL::Point_2<K> for some representation class K and FT is equivalent to K::FT,
2. Or: (if a traits parameter is specified) Traits is a model for RectangularPCenterTraits_2.
3. OutputIterator accepts the value type of ForwardIterator as value type.

See Also

Implementation

p {2,3}

(n ·

Example

File: examples/Matrix_search/rectangular_p_center_2.cpp

#include <CGAL/Cartesian.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/rectangular_p_center_2.h>
#include <CGAL/IO/Ostream_iterator.h>
#include <CGAL/algorithm.h>
#include <iostream>
#include <algorithm>
#include <vector>

typedef double                                      FT;

struct Kernel : public CGAL::Cartesian<FT> {};

typedef Kernel::Point_2                             Point;
typedef std::vector<Point>                          Cont;
typedef CGAL::Random_points_in_square_2<Point>      Generator;
typedef CGAL::Ostream_iterator<Point,std::ostream>  OIterator;

int main()
{
  int n = 10;
  int p = 2;
  OIterator cout_ip(std::cout);
  CGAL::set_pretty_mode(std::cout);

  Cont points;
  CGAL::copy_n(Generator(1), n, std::back_inserter(points));
  std::cout << "Generated Point Set:\n";
  std::copy(points.begin(), points.end(), cout_ip);

  FT p_radius;
  std::cout << "\n\n" << p << "-centers:\n";
  CGAL::rectangular_p_center_2(
    points.begin(), points.end(), cout_ip, p_radius, 3);
  std::cout << "\n\n" << p << "-radius = " << p_radius << std::endl;

  return 0;
}
// ----------------------------------------------------------------------------
// ** EOF
// ----------------------------------------------------------------------------