#ifndef POINT_IN_VERTICAL_TRAPEZOID_H
#define POINT_IN_VERTICAL_TRAPEZOID_H
// Construct a point located in the interior of the given vertical
// trapezoidal face, lying as far as possible from the face boundary.
template
typename Kernel::Point_2
point_in_vertical_trapezoid(typename Arrangement::Face_const_handle f,
const Arrangement& arr, const Kernel& ker)
{
const typename Arrangement::Traits_2::Is_vertical_2 is_vertical =
arr.traits()->is_vertical_2_object();
const typename Kernel::Construct_midpoint_2 midpoint =
ker.construct_midpoint_2_object();
// Locate the two edges along the face boundary that are not associated
// with vertical segments, such that one lies on the upper boundary of the
// face and the other on its lower boundary. Note that these two edges must
// have opposite directions.
typename Arrangement::Halfedge_const_handle he1, he2;
CGAL::Arr_halfedge_direction direction;
bool found = false;
typename Arrangement::Ccb_halfedge_const_circulator first = f->outer_ccb();
typename Arrangement::Ccb_halfedge_const_circulator circ = first;
do {
if (!is_vertical(circ->curve())) {
// The current edge is not vertical: assign it as either he1 or he2.
if (!found) {
he1 = circ;
direction = he1->direction();
found = true;
continue;
}
if (circ->direction() != direction) {
he2 = circ;
break;
}
}
} while (++circ != first);
// Take the midpoint of the midpoints of he1 and he2.
return midpoint(midpoint(he1->source()->point(), he1->target()->point()),
midpoint(he2->source()->point(), he2->target()->point()));
}
#endif