## CGAL::ch_melkman

### Definition

The function ch_melkman computes the counterclockwise sequence of extreme points of a sequence of points that forms a simple polyline or polygon.

#include <CGAL/ch_melkman.h>

template <class InputIterator, class OutputIterator>

OutputIterator

ch_melkman ( | InputIterator first, InputIterator last, OutputIterator result, Traits ch_traits = Default_traits)

|  | generates the counterclockwise sequence of extreme points of the points in the range [first, beyond). The resulting sequence is placed starting at position result, and the past-the-end iterator for the resulting sequence is returned. Precondition: The source range [first,beyond) corresponds to a simple polyline. [first,beyond) does not contain result

.

The default traits class Default_traits is the kernel in which the type InputIterator::value_type is defined.

### Requirements

1. InputIterator::value_type and OutputIterator::value_type are equivalent to Traits::Point_2.
2. Traits contains the following subset of types from the concept ConvexHullTraits_2 and their corresponding member functions that return instances of these types:
   - Traits::Point_2,
   - Traits::Equal_2,
   - Traits::Less_xy_2,
   - Traits::Left_turn_2.

### See Also

CGAL::ch_akl_toussaint
CGAL::ch_bykat
CGAL::ch_eddy
CGAL::ch_graham_andrew
CGAL::ch_jarvis
CGAL::ch_melkman
CGAL::convex_hull_2

### Implementation

It uses an implementation of Melkman's algorithm [Mel87]. Running time of this is linear.