const& points) { typedef typename geometry::coordinate_type::type coordinate_type; typedef typename std::vector

::const_iterator iterator_type; coordinate_type x = 0; coordinate_type y = 0; iterator_type end = points.end(); for ( iterator_type it = points.begin() ; it != end ; ++it) { x += geometry::get<0>(*it); y += geometry::get<1>(*it); } signed_size_type const count = points.size(); geometry::set<0>(point, x / count); geometry::set<1>(point, y / count); } template inline void replace_extremes_for_self_tangencies(Extremes& extremes, Intruders& intruders, CoordinateType const& max_intruder) { // This function handles self-tangencies. // Self-tangencies use, as usual, the major part of code... // ___ e // /|\ \ . // / | \ \ . // / | \ \ . // / | \ \ . // / /\ | \ \ . // i2 i1 // The picture above shows the extreme (outside, "e") and two intruders ("i1","i2") // Assume that "i1" is self-tangent with the extreme, in one point at the top // Now the "penultimate" value is searched, this is is the top of i2 // Then everything including and below (this is "i2" here) is removed // Then the base of "i1" and of "e" is adapted to this penultimate value // It then looks like: // b ___ e // /|\ \ . // / | \ \ . // / | \ \ . // / | \ \ . // a c i1 // Then intruders (here "i1" but there may be more) are sorted from left to right // Finally points "a","b" and "c" (in this order) are selected as a new triangle. // This triangle will have a centroid which is inside (assumed that intruders left segment // is not equal to extremes left segment, but that polygon would be invalid) // Find highest non-self tangent intrusion, if any CoordinateType penultimate_value; specific_coordinate_first pu_compare(max_intruder); if (max_value(intruders, penultimate_value, pu_compare)) { // Throw away all intrusions <= this value, and of the kept one set this as base. select_below predicate(penultimate_value); intruders.erase ( std::remove_if(boost::begin(intruders), boost::end(intruders), predicate), boost::end(intruders) ); adapt_base fe_predicate(penultimate_value); // Sort from left to right (or bottom to top if Dimension=0) std::for_each(boost::begin(intruders), boost::end(intruders), fe_predicate); // Also adapt base of extremes detail::extreme_points::move_along_vector(extremes, penultimate_value); } // Then sort in 1-Dim. Take first to calc centroid. std::sort(boost::begin(intruders), boost::end(intruders), min_of_intruder<1 - Dimension, CoordinateType>()); Extremes triangle; triangle.reserve(3); // Make a triangle of first two points of extremes (the ramp, from left to right), and last point of first intruder (which goes from right to left) std::copy(extremes.begin(), extremes.begin() + 2, std::back_inserter(triangle)); triangle.push_back(intruders.front().back()); // (alternatively we could use the last two points of extremes, and first point of last intruder...): //// ALTERNATIVE: std::copy(extremes.rbegin(), extremes.rbegin() + 2, std::back_inserter(triangle)); //// ALTERNATIVE: triangle.push_back(intruders.back().front()); // Now replace extremes with this smaller subset, a triangle, such that centroid calculation will result in a point inside extremes = triangle; } template inline bool calculate_point_on_surface(Geometry const& geometry, Point& point, SideStrategy const& strategy) { typedef typename geometry::point_type::type point_type; typedef typename geometry::coordinate_type::type coordinate_type; std::vector extremes; typedef std::vector > intruders_type; intruders_type intruders; geometry::extreme_points(geometry, extremes, intruders, strategy); if (extremes.size() < 3) { return false; } // If there are intruders, find the max. if (! intruders.empty()) { coordinate_type max_intruder; detail::extreme_points::compare compare; if (max_value(intruders, max_intruder, compare)) { coordinate_type max_extreme = geometry::get(*std::max_element(extremes.begin(), extremes.end(), detail::extreme_points::compare())); if (max_extreme > max_intruder) { detail::extreme_points::move_along_vector(extremes, max_intruder); } else { replace_extremes_for_self_tangencies(extremes, intruders, max_intruder); } } } // Now calculate the average/centroid of the (possibly adapted) extremes calculate_average(point, extremes); return true; } }} // namespace detail::point_on_surface #endif // DOXYGEN_NO_DETAIL /*! \brief Assigns a Point guaranteed to lie on the surface of the Geometry \tparam Geometry geometry type. This also defines the type of the output point \param geometry Geometry to take point from \param point Point to assign \param strategy side strategy */ template inline void point_on_surface(Geometry const& geometry, Point & point, SideStrategy const& strategy) { concepts::check(); concepts::check(); // First try in Y-direction (which should always succeed for valid polygons) if (! detail::point_on_surface::calculate_point_on_surface<1>(geometry, point, strategy)) { // For invalid polygons, we might try X-direction detail::point_on_surface::calculate_point_on_surface<0>(geometry, point, strategy); } } /*! \brief Assigns a Point guaranteed to lie on the surface of the Geometry \tparam Geometry geometry type. This also defines the type of the output point \param geometry Geometry to take point from \param point Point to assign */ template inline void point_on_surface(Geometry const& geometry, Point & point) { typedef typename strategy::side::services::default_strategy < typename cs_tag::type >::type strategy_type; point_on_surface(geometry, point, strategy_type()); } /*! \brief Returns point guaranteed to lie on the surface of the Geometry \tparam Geometry geometry type. This also defines the type of the output point \param geometry Geometry to take point from \param strategy side strategy \return The Point guaranteed to lie on the surface of the Geometry */ template inline typename geometry::point_type::type return_point_on_surface(Geometry const& geometry, SideStrategy const& strategy) { typename geometry::point_type::type result; geometry::point_on_surface(geometry, result, strategy); return result; } /*! \brief Returns point guaranteed to lie on the surface of the Geometry \tparam Geometry geometry type. This also defines the type of the output point \param geometry Geometry to take point from \return The Point guaranteed to lie on the surface of the Geometry */ template inline typename geometry::point_type::type return_point_on_surface(Geometry const& geometry) { typename geometry::point_type::type result; geometry::point_on_surface(geometry, result); return result; } }} // namespace boost::geometry #endif // BOOST_GEOMETRY_ALGORITHMS_POINT_ON_SURFACE_HPP