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

126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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

105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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

407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
    {
        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

59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
 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

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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

443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
// 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

214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
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

574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
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

236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
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

1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
// 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

1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
// 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();