Navigation: Up, Table of Contents, Bibliography, Index, Title Page

All Furthest Neighbors

This section describes a function to compute all furthest neighbors for the vertices of a convex polygon $P$, i.e. for each vertex $v$ of $P$ a vertex $f_v$ of $P$ such that the distance between $v$ and $f_v$ is maximized.

#include <CGAL/all_furthest_neighbors_2.h>

template < class RandomAccessIC, class OutputIterator, class Traits >
OutputIterator
all_furthest_neighbors (
RandomAccessIC points_begin,
RandomAccessIC points_end,
OutputIterator o,
Traits t = Default_traits)

computes all furthest neighbors for the vertices of the convex polygon described by the range [points_begin, points_end), writes their indices (relative to points_begin) to o1 and returns the past-the-end iterator of this sequence.

Precondition

  1. If t is specified explicitly, Traits satisfies the requirements stated in section reference,
  2. Value type of RandomAccessIC is Traits::Point_2 or - if t is not specified explicitly - Point_2<R> for some representation class R,
  3. OutputIterator accepts int as value type and
  4. the points denoted by the non-empty range [points_begin, points_end) form the boundary of a convex polygon P (oriented clock- or counterclockwise).

Implementation

The implementation uses monotone matrix search[AKM+87] (see also section reference). Its runtime complexity is linear in the number of vertices of P.

Example

The following code generates a random convex polygon p with ten vertices, computes all furthest neighbors and writes the sequence of their indices (relative to points_begin) to cout (e.g. a sequence of 4788911224 means the furthest neighbor of points_begin[0] is points_begin[4], the furthest neighbor of points_begin[1] is points_begin[7] etc.). 

#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_convex_set_2.h>
#include <CGAL/all_furthest_neighbors_2.h>
#include <CGAL/IO/Ostream_iterator.h>
#include <iostream>
#include <vector>

using namespace std;
using CGAL::random_convex_set_2;
using CGAL::all_furthest_neighbors;

typedef double                                   FT;
typedef CGAL::Cartesian< FT >                    R;
typedef CGAL::Point_2< R >                       Point;
typedef CGAL::Polygon_traits_2< R >              P_traits;
typedef vector< Point >                          Point_cont;
typedef CGAL::Polygon_2< P_traits, Point_cont >  Polygon;
typedef CGAL::Creator_uniform_2< FT, Point >     Creator;
typedef CGAL::Random_points_in_square_2< Point, Creator >
  Point_generator;
typedef CGAL::Ostream_iterator< int, ostream >   Oiterator;

int
main()
{
  // generate random convex polygon:
  Polygon p;
  random_convex_set_2( 10, back_inserter( p), Point_generator( 1));

  // compute all furthest neighbors:
  all_furthest_neighbors(
    p.vertices_begin(),
    p.vertices_end(),
    Oiterator( cout));
  cout << endl;

  return 0;
}

Footnotes

 1  i.e. the furthest neighbor of points_begin[i] is points_begin[i-th number written to o]

Next: Class declaration of Afn_traits
Navigation: Up, Table of Contents, Bibliography, Index, Title Page
The GALIA project. Jan 18, 2000.