Boost-Geometry-Utils

 view release on metacpan or  search on metacpan

src/boost/geometry/strategies/agnostic/point_in_poly_oriented_winding.hpp  view on Meta::CPAN

    template <size_t D>
    static inline int check_segment(Point const& point,
                PointOfSegment const& seg1, PointOfSegment const& seg2,
                counter& state)
    {
        calculation_type const p = get<D>(point);
        calculation_type const s1 = get<D>(seg1);
        calculation_type const s2 = get<D>(seg2);


        // Check if one of segment endpoints is at same level of point
        bool eq1 = math::equals(s1, p);
        bool eq2 = math::equals(s2, p);

        if (eq1 && eq2)
        {
            // Both equal p -> segment is horizontal (or vertical for D=0)
            // The only thing which has to be done is check if point is ON segment
            return check_touch<1 - D>(point, seg1, seg2, state);
        }

src/boost/geometry/strategies/agnostic/point_in_poly_winding.hpp  view on Meta::CPAN

    template <size_t D>
    static inline int check_segment(Point const& point,
                PointOfSegment const& seg1, PointOfSegment const& seg2,
                counter& state)
    {
        calculation_type const p = get<D>(point);
        calculation_type const s1 = get<D>(seg1);
        calculation_type const s2 = get<D>(seg2);

        // Check if one of segment endpoints is at same level of point
        bool eq1 = math::equals(s1, p);
        bool eq2 = math::equals(s2, p);

        if (eq1 && eq2)
        {
            // Both equal p -> segment is horizontal (or vertical for D=0)
            // The only thing which has to be done is check if point is ON segment
            return check_touch<1 - D>(point, seg1, seg2,state);
        }

src/boost/geometry/strategies/cartesian/cart_intersect.hpp  view on Meta::CPAN

        {
            if (verify_disjoint<0>(a, b) || verify_disjoint<1>(a, b))
            {
                return true;
            }
        }
        return false;
    }


    // If r is one, or zero, segments should meet and their endpoints.
    // Robustness issue: check if this is really the case.
    // It turns out to be no problem, see buffer test #rt_s1 (and there are many cases generated)
    // It generates an "ends in the middle" situation which is correct.
    template <typename T, typename R>
    static inline void robustness_handle_meeting(segment_type1 const& a, segment_type2 const& b,
                side_info& sides,
                T const& dx_a, T const& dy_a, T const& wx, T const& wy,
                T const& d, R const& r)
    {
        return;

src/boost/polygon/detail/voronoi_structures.hpp  view on Meta::CPAN

 private:
  coordinate_type x_;
  coordinate_type y_;
};

// Site event type.
// Occurs when the sweepline sweeps over one of the initial sites:
//   1) point site
//   2) start-point of the segment site
//   3) endpoint of the segment site
// Implicit segment direction is defined: the start-point of
// the segment compares less than its endpoint.
// Each input segment is divided onto two site events:
//   1) One going from the start-point to the endpoint
//      (is_inverse() = false)
//   2) Another going from the endpoint to the start-point
//      (is_inverse() = true)
// In beach line data structure segment sites of the first
// type precede sites of the second type for the same segment.
// Members:
//   point0_ - point site or segment's start-point
//   point1_ - segment's endpoint if site is a segment
//   sorted_index_ - the last bit encodes information if the site is inverse;
//     the other bits encode site event index among the sorted site events
//   initial_index_ - site index among the initial input set
// Note: for all sites is_inverse_ flag is equal to false by default.
template <typename T>
class site_event {
 public:
  typedef T coordinate_type;
  typedef point_2d<T> point_type;

src/boost/polygon/voronoi.hpp  view on Meta::CPAN

#define BOOST_POLYGON_VORONOI

#include "isotropy.hpp"
#include "point_concept.hpp"
#include "segment_concept.hpp"

#include "voronoi_builder.hpp"
#include "voronoi_diagram.hpp"

// Public methods to compute Voronoi diagram.
// Coordinates of the points and of the endpoints of the segments should belong
// to the 32-bit signed integer range [-2^31, 2^31-1]. To use wider input
// coordinate range voronoi_builder configuration via coordinate type traits is
// is required.
// Complexity - O(N*logN), memory usage - O(N), N - number of input objects.
namespace boost {
namespace polygon {

template <typename Point, typename VB>
typename enable_if<
  typename gtl_if<

src/boost/polygon/voronoi_builder.hpp  view on Meta::CPAN

#include "detail/voronoi_ctypes.hpp"
#include "detail/voronoi_predicates.hpp"
#include "detail/voronoi_structures.hpp"

#include "voronoi_geometry_type.hpp"

namespace boost {
namespace polygon {
// GENERAL INFO:
// The sweepline algorithm implementation to compute Voronoi diagram of
// points and non-intersecting segments (except endpoints).
// Complexity - O(N*logN), memory usage - O(N), where N is the total number
// of input geometries. Input geometries should have integer coordinate type.
//
// IMPLEMENTATION DETAILS:
// Each input point creates one site event. Each input segment creates three
// site events: two for its endpoints and one for the segment itself (this is
// made to simplify output construction). All the site events are constructed
// and sorted at the algorithm initialization step. Priority queue is used to
// dynamically hold circle events. At each step of the algorithm execution the
// leftmost event is retrieved by comparing the current site event and the
// topmost element from the circle event queue. STL map (red-black tree)
// container was chosen to hold state of the beach line. The keys of the map
// correspond to the neighboring sites that form a bisector and values map to
// the corresponding Voronoi edges in the output data structure.
template <typename T,
          typename CTT = detail::voronoi_ctype_traits<T>,

src/boost/polygon/voronoi_builder.hpp  view on Meta::CPAN

    // Update the output.
    std::pair<edge_type*, edge_type*> edges =
        output->_insert_new_edge(site_arc2, site_event);
    position = beach_line_.insert(position,
        typename beach_line_type::value_type(
            new_right_node, value_type(edges.second)));

    if (site_event.is_segment()) {
      // Update the beach line with temporary bisector, that will
      // disappear after processing site event corresponding to the
      // second endpoint of the segment site.
      key_type new_node(site_event, site_event);
      new_node.right_site().inverse();
      position = beach_line_.insert(position,
          typename beach_line_type::value_type(new_node, value_type(NULL)));

      // Update the data structure that holds temporary bisectors.
      end_points_.push(std::make_pair(site_event.point1(), position));
    }

    position = beach_line_.insert(position,

src/boost/polygon/voronoi_diagram.hpp  view on Meta::CPAN

  bool is_linear() const {
    return (color_ & BIT_IS_LINEAR) ? true : false;
  }

  // Returns true if the edge is curved (parabolic arc).
  // Returns false if the edge is linear (segment, ray, line).
  bool is_curved() const {
    return (color_ & BIT_IS_LINEAR) ? false : true;
  }

  // Returns false if edge goes through the endpoint of the segment.
  // Returns true else.
  bool is_primary() const {
    return (color_ & BIT_IS_PRIMARY) ? true : false;
  }

  // Returns true if edge goes through the endpoint of the segment.
  // Returns false else.
  bool is_secondary() const {
    return (color_ & BIT_IS_PRIMARY) ? false : true;
  }

  color_type color() const { return color_ >> BITS_SHIFT; }
  void color(color_type color) const {
    color_ &= BITS_MASK;
    color_ |= color << BITS_SHIFT;
  }

src/boost/polygon/voronoi_diagram.hpp  view on Meta::CPAN

  template <typename SEvent>
  bool is_linear_edge(const SEvent& site1, const SEvent& site2) const {
    if (!is_primary_edge(site1, site2)) {
      return true;
    }
    return !(site1.is_segment() ^ site2.is_segment());
  }

  // Remove degenerate edge.
  void remove_edge(edge_type* edge) {
    // Update the endpoints of the incident edges to the second vertex.
    vertex_type* vertex = edge->vertex0();
    edge_type* updated_edge = edge->twin()->rot_next();
    while (updated_edge != edge->twin()) {
      updated_edge->vertex0(vertex);
      updated_edge = updated_edge->rot_next();
    }

    edge_type* edge1 = edge;
    edge_type* edge2 = edge->twin();

src/medial_axis.hpp  view on Meta::CPAN

  bool is_linear() const {
    return (color_ & BIT_IS_LINEAR) ? true : false;
  }

  // Returns true if the edge is curved (parabolic arc).
  // Returns false if the edge is linear (segment, ray, line).
  bool is_curved() const {
    return (color_ & BIT_IS_LINEAR) ? false : true;
  }

  // Returns false if edge goes through the endpoint of the segment.
  // Returns true else.
  bool is_primary() const {
    return (color_ & BIT_IS_PRIMARY) ? true : false;
  }

  // Returns true if edge goes through the endpoint of the segment.
  // Returns false else.
  bool is_secondary() const {
    return (color_ & BIT_IS_PRIMARY) ? false : true;
  }

  color_type color() const { return color_ >> BITS_SHIFT; }
  void color(color_type color) const {
    color_ &= BITS_MASK;
    color_ |= color << BITS_SHIFT;
  }

src/medial_axis.hpp  view on Meta::CPAN

        // if next edge is within polygon
        if (edge->next()->color() == 0 || edge->next()->color() == 2) {
          if (edge->next()->is_primary()) { 
            // go to next edge within same cell 
            edge = edge->next();
          } else { 
            // skip over a non-primary edge to the primary edge that follows it
            edge_type* prev = edge;
            edge = edge->next()->twin()->next();
            // get foot from non-primary endpoint and
            // mirror foot info from the non-primary to the twin
            if (prev->twin()->vertex0() && prev->twin()->vertex1() && prev->next()->vertex1()) {
              // The reflect about line case is simple:
              double x = prev->next()->vertex1()->x();
              double y = prev->next()->vertex1()->y();
              
              if (!edge->foot()) {
                edge->foot(x, y);
              }
              

src/medial_axis.hpp  view on Meta::CPAN

    // but these do fill in/transfer some missing feet.
    // After revising the foot-finding (trying to do it all in the sweepline
    // event processing), see if these are still needed.
    if (edge->foot() && !edge->next()->foot()) {
      edge->next()->foot(edge->foot()->x(), edge->foot()->y());
    }
    if (edge->twin()->foot() && !edge->twin()->next()->foot()) {
      edge->twin()->next()->foot(edge->twin()->foot()->x(), edge->twin()->foot()->y());
    }

    // Update the endpoints of the incident edges to the second vertex.
    vertex_type* vertex = edge->vertex0();
    edge_type* updated_edge = edge->twin()->rot_next();
    while (updated_edge != edge->twin()) {
      updated_edge->vertex0(vertex);
      updated_edge = updated_edge->rot_next();
    }
    
    edge_type* edge1 = edge;
    edge_type* edge2 = edge->twin();