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

## CGAL::all_furthest_neighbors_2

### Definition

The function all_furthest_neighbors_2 computes all furthest neighbors for the vertices of a convex polygon P, i.e. for each vertex v of P a vertex fv of P such that the distance between v and fv is maximized.

#include <CGAL/all_furthest_neighbors_2.h>

template < class RandomAccessIterator, class OutputIterator, class Traits >
OutputIterator |
all_furthest_neighbors_2 (
| RandomAccessIterator points_begin, RandomAccessIterator 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 o 1 and returns the past-the-end iterator of this sequence.

Precondition: The points denoted by the non-empty range [points_begin, points_end) form the boundary of a convex polygon P (oriented clock- or counterclockwise).

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 RandomAccessIterator refers to a point type from a Kernel. In this case, the kernel is used as default traits class.

Requirement:

1. If t is specified explicitly, Traits is a model for AllFurthestNeighborsTraits_2.
2. Value type of RandomAccessIterator is Traits::Point_2 or - if t is not specified explicitly - K::Point_2 where K is a model for Kernel.
3. OutputIterator accepts int as value type.

### See Also

AllFurthestNeighborsTraits_2
CGAL::monotone_matrix_search

### Implementation

The implementation uses monotone matrix search[AKM+87]. 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/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>

    typedef double                                    FT;

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

    typedef Kernel::Point_2                           Point;
    typedef std::vector<int>                          Index_cont;
    typedef CGAL::Polygon_2<Kernel>                   Polygon;
    typedef CGAL::Random_points_in_square_2<Point>    Generator;
    typedef CGAL::Ostream_iterator<int,std::ostream>  Oiterator;

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

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

      return 0;
    }

### Footnotes

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

Next: AllFurthestNeighborsTraits_2

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

The CGAL Project . Tue, December 21, 2004 .