summaryrefslogtreecommitdiff
path: root/boost/polygon/polygon_set_data.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/polygon/polygon_set_data.hpp')
-rw-r--r--boost/polygon/polygon_set_data.hpp175
1 files changed, 89 insertions, 86 deletions
diff --git a/boost/polygon/polygon_set_data.hpp b/boost/polygon/polygon_set_data.hpp
index bbddacf241..3c761d34f8 100644
--- a/boost/polygon/polygon_set_data.hpp
+++ b/boost/polygon/polygon_set_data.hpp
@@ -1,6 +1,6 @@
/*
Copyright 2008 Intel Corporation
-
+
Use, modification and distribution are subject to the Boost Software License,
Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt).
@@ -11,7 +11,6 @@
#include "polygon_45_set_concept.hpp"
#include "polygon_traits.hpp"
#include "detail/polygon_arbitrary_formation.hpp"
-#include <iostream>
namespace boost { namespace polygon {
@@ -22,7 +21,7 @@ namespace boost { namespace polygon {
template <typename T>
static inline T round_down(double val) {
T rounded_val = (T)(val);
- if(val < (double)rounded_val)
+ if(val < (double)rounded_val)
--rounded_val;
return rounded_val;
}
@@ -57,11 +56,11 @@ namespace boost { namespace polygon {
}
// copy constructor
- inline polygon_set_data(const polygon_set_data& that) :
+ inline polygon_set_data(const polygon_set_data& that) :
data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_), is_45_(that.is_45_) {}
// copy constructor
- template <typename ltype, typename rtype, int op_type>
+ template <typename ltype, typename rtype, int op_type>
inline polygon_set_data(const polygon_set_view<ltype, rtype, op_type>& that);
// destructor
@@ -150,10 +149,10 @@ namespace boost { namespace polygon {
insert(polygon_object, is_hole, polygon_concept()); }
template <typename polygon_with_holes_type>
- inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
+ inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
polygon_with_holes_concept ) {
insert(polygon_with_holes_object, is_hole, polygon_concept());
- for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr =
+ for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr =
begin_holes(polygon_with_holes_object);
itr != end_holes(polygon_with_holes_object); ++itr) {
insert(*itr, !is_hole, polygon_concept());
@@ -161,12 +160,12 @@ namespace boost { namespace polygon {
}
template <typename polygon_with_holes_type>
- inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
+ inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
polygon_45_with_holes_concept ) {
insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); }
template <typename polygon_with_holes_type>
- inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
+ inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
polygon_90_with_holes_concept ) {
insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); }
@@ -198,36 +197,34 @@ namespace boost { namespace polygon {
template <class iT>
inline void insert_vertex_sequence(iT begin_vertex, iT end_vertex, direction_1d winding, bool is_hole) {
- bool first_iteration = true;
- point_type first_point;
- point_type previous_point;
- point_type current_point;
- direction_1d winding_dir = winding;
- int multiplier = winding_dir == COUNTERCLOCKWISE ? 1 : -1;
- if(is_hole) multiplier *= -1;
- for( ; begin_vertex != end_vertex; ++begin_vertex) {
- assign(current_point, *begin_vertex);
- if(first_iteration) {
- first_iteration = false;
- first_point = previous_point = current_point;
- } else {
- if(previous_point != current_point) {
- element_type elem(edge_type(previous_point, current_point),
- ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
- insert_clean(elem);
- }
- }
- previous_point = current_point;
+ if (begin_vertex == end_vertex) {
+ // No edges to insert.
+ return;
}
- current_point = first_point;
- if(!first_iteration) {
- if(previous_point != current_point) {
- element_type elem(edge_type(previous_point, current_point),
- ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
+ // Current edge endpoints.
+ iT vertex0 = begin_vertex;
+ iT vertex1 = begin_vertex;
+ if (++vertex1 == end_vertex) {
+ // No edges to insert.
+ return;
+ }
+ int wmultiplier = (winding == COUNTERCLOCKWISE) ? 1 : -1;
+ dirty_ = true;
+ unsorted_ = true;
+ while (vertex0 != end_vertex) {
+ point_type p0, p1;
+ assign(p0, *vertex0);
+ assign(p1, *vertex1);
+ if (p0 != p1) {
+ int hmultiplier = (p0.get(HORIZONTAL) == p1.get(HORIZONTAL)) ? -1 : 1;
+ element_type elem(edge_type(p0, p1), hmultiplier * wmultiplier);
insert_clean(elem);
}
- dirty_ = true;
- unsorted_ = true;
+ ++vertex0;
+ ++vertex1;
+ if (vertex1 == end_vertex) {
+ vertex1 = begin_vertex;
+ }
}
}
@@ -248,7 +245,7 @@ namespace boost { namespace polygon {
data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
}
- gtlsort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(container, data.begin(), data.end());
//std::cout << "DONE FORMING POLYGONS\n";
}
@@ -270,14 +267,10 @@ namespace boost { namespace polygon {
}
}
- // equivalence operator
- inline bool operator==(const polygon_set_data& p) const {
- clean();
- p.clean();
- return data_ == p.data_;
- }
+ // equivalence operator
+ inline bool operator==(const polygon_set_data& p) const;
- // inequivalence operator
+ // inequivalence operator
inline bool operator!=(const polygon_set_data& p) const {
return !((*this) == p);
}
@@ -321,7 +314,7 @@ namespace boost { namespace polygon {
void sort() const{
if(unsorted_) {
- gtlsort(data_.begin(), data_.end());
+ polygon_sort(data_.begin(), data_.end());
unsorted_ = false;
}
}
@@ -329,13 +322,14 @@ namespace boost { namespace polygon {
template <typename input_iterator_type>
void set(input_iterator_type input_begin, input_iterator_type input_end) {
clear();
+ reserve(std::distance(input_begin,input_end));
insert(input_begin, input_end);
dirty_ = true;
unsorted_ = true;
}
void set(const value_type& value) {
- data_ = value;
+ data_ = value;
dirty_ = true;
unsorted_ = true;
}
@@ -362,7 +356,7 @@ namespace boost { namespace polygon {
resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0);
template <typename transform_type>
- inline polygon_set_data&
+ inline polygon_set_data&
transform(const transform_type& tr) {
std::vector<polygon_with_holes_data<T> > polys;
get(polys);
@@ -376,7 +370,7 @@ namespace boost { namespace polygon {
return *this;
}
- inline polygon_set_data&
+ inline polygon_set_data&
scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
::boost::polygon::scale_up((*itr).first.first, factor);
@@ -384,31 +378,41 @@ namespace boost { namespace polygon {
}
return *this;
}
-
- inline polygon_set_data&
+
+ inline polygon_set_data&
scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
+ bool vb = (*itr).first.first.x() == (*itr).first.second.x();
::boost::polygon::scale_down((*itr).first.first, factor);
::boost::polygon::scale_down((*itr).first.second, factor);
+ bool va = (*itr).first.first.x() == (*itr).first.second.x();
+ if(!vb && va) {
+ (*itr).second *= -1;
+ }
}
unsorted_ = true;
dirty_ = true;
return *this;
}
-
+
template <typename scaling_type>
- inline polygon_set_data& scale(polygon_set_data& polygon_set,
+ inline polygon_set_data& scale(polygon_set_data& polygon_set,
const scaling_type& scaling) {
for(typename value_type::iterator itr = begin(); itr != end(); ++itr) {
+ bool vb = (*itr).first.first.x() == (*itr).first.second.x();
::boost::polygon::scale((*itr).first.first, scaling);
::boost::polygon::scale((*itr).first.second, scaling);
+ bool va = (*itr).first.first.x() == (*itr).first.second.x();
+ if(!vb && va) {
+ (*itr).second *= -1;
+ }
}
unsorted_ = true;
dirty_ = true;
return *this;
}
- static inline void compute_offset_edge(point_data<long double>& pt1, point_data<long double>& pt2,
+ static inline void compute_offset_edge(point_data<long double>& pt1, point_data<long double>& pt2,
const point_data<long double>& prev_pt,
const point_data<long double>& current_pt,
long double distance, int multiplier) {
@@ -439,17 +443,17 @@ namespace boost { namespace polygon {
he2.second.y((long double)(next_pt.y()));
compute_offset_edge(he1.first, he1.second, prev_pt, current_pt, distance, multiplier);
compute_offset_edge(he2.first, he2.second, current_pt, next_pt, distance, multiplier);
- typename scanline_base<long double>::compute_intersection_pack pack;
+ typedef scanline_base<long double>::compute_intersection_pack pack;
point_data<long double> rpt;
point_data<long double> bisectorpt((he1.second.x()+he2.first.x())/2,
(he1.second.y()+he2.first.y())/2);
point_data<long double> orig_pt((long double)pt.x(), (long double)pt.y());
if(euclidean_distance(bisectorpt, orig_pt) < distance/2) {
- if(!pack.compute_lazy_intersection(rpt, he1, he2, true, false)) {
+ if(!pack::compute_lazy_intersection(rpt, he1, he2, true, false)) {
rpt = he1.second; //colinear offset edges use shared point
}
} else {
- if(!pack.compute_lazy_intersection(rpt, he1, std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), true, false)) {
+ if(!pack::compute_lazy_intersection(rpt, he1, std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), true, false)) {
rpt = he1.second; //colinear offset edges use shared point
}
}
@@ -565,8 +569,8 @@ namespace boost { namespace polygon {
}
template <typename geometry_type>
- inline polygon_set_data&
- insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
+ inline polygon_set_data&
+ insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
polygon_with_holes_concept tag) {
insert_with_resize_dispatch(poly, resizing, corner_fill_arc, num_circle_segments, hole, polygon_concept());
for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr =
@@ -578,14 +582,14 @@ namespace boost { namespace polygon {
}
template <typename geometry_type>
- inline polygon_set_data&
- insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
+ inline polygon_set_data&
+ insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
polygon_concept tag) {
if (resizing==0)
return *this;
-
+
// one dimensional used to store CCW/CW flag
//direction_1d wdir = winding(poly);
// LOW==CLOCKWISE just faster to type
@@ -630,25 +634,25 @@ namespace boost { namespace polygon {
point_data<coordinate_type> normal2( third->y()-second->y(), second->x()-third->x());
double direction = normal1.x()*normal2.y()- normal2.x()*normal1.y();
bool convex = direction>0;
-
+
bool treat_as_concave = !convex;
if(sizing_sign)
treat_as_concave = convex;
point_data<double> v;
assign(v, normal1);
double s2 = (v.x()*v.x()+v.y()*v.y());
- double s = sqrt(s2)/resizing;
+ double s = std::sqrt(s2)/resizing;
v = point_data<double>(v.x()/s,v.y()/s);
point_data<T> curr_prev;
if (prev_concave)
//TODO missing round_down()
curr_prev = point_data<T>(first->x()+v.x(),first->y()+v.y());
- else
+ else
curr_prev = prev_point;
// around concave corners - insert rectangle
// if previous corner is concave it's point info may be ignored
- if ( treat_as_concave) {
+ if ( treat_as_concave) {
std::vector<point_data<T> > pts;
pts.push_back(point_data<T>(second->x()+v.x(),second->y()+v.y()));
@@ -669,13 +673,13 @@ namespace boost { namespace polygon {
direction_1d winding;
winding = convex?COUNTERCLOCKWISE:CLOCKWISE;
if (make_resizing_vertex_list(pts, curr_prev, prev_concave, *first, *second, *third, resizing
- , num_circle_segments, corner_fill_arc))
+ , num_circle_segments, corner_fill_arc))
{
if (first_pts.size()) {
for (int i=0; i<pts.size(); i++) {
sizingSet.insert_vertex_sequence(pts[i].begin(),pts[i].end(),winding,false);
}
-
+
} else {
first_pts = pts[0];
first_wdir = resize_wdir;
@@ -684,7 +688,7 @@ namespace boost { namespace polygon {
}
}
prev_point = curr_prev;
-
+
} else {
treat_as_concave = true;
}
@@ -707,7 +711,7 @@ namespace boost { namespace polygon {
first_pts[first_pts.size()-1]=prev_point;
}
sizingSet.insert_vertex_sequence(first_pts.begin(),first_pts.end(),first_wdir,false);
-
+
polygon_set_data<coordinate_type> tmp;
//insert original shape
@@ -721,7 +725,7 @@ namespace boost { namespace polygon {
inline polygon_set_data&
- interact(const polygon_set_data& that);
+ interact(const polygon_set_data& that);
inline bool downcast(polygon_45_set_data<coordinate_type>& result) const {
if(!is_45_) return false;
@@ -790,7 +794,7 @@ namespace boost { namespace polygon {
data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
}
- gtlsort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(container, data.begin(), data.end());
}
};
@@ -810,17 +814,17 @@ namespace boost { namespace polygon {
// }
template <typename T>
- inline int make_resizing_vertex_list(std::vector<std::vector<point_data< T> > >& return_points,
+ inline int make_resizing_vertex_list(std::vector<std::vector<point_data< T> > >& return_points,
point_data<T>& curr_prev, bool ignore_prev_point,
point_data< T> start, point_data<T> middle, point_data< T> end,
double sizing_distance, unsigned int num_circle_segments, bool corner_fill_arc) {
// handle the case of adding an intersection point
point_data<double> dn1( middle.y()-start.y(), start.x()-middle.x());
- double size = sizing_distance/sqrt( dn1.x()*dn1.x()+dn1.y()*dn1.y());
+ double size = sizing_distance/std::sqrt( dn1.x()*dn1.x()+dn1.y()*dn1.y());
dn1 = point_data<double>( dn1.x()*size, dn1.y()* size);
point_data<double> dn2( end.y()-middle.y(), middle.x()-end.x());
- size = sizing_distance/sqrt( dn2.x()*dn2.x()+dn2.y()*dn2.y());
+ size = sizing_distance/std::sqrt( dn2.x()*dn2.x()+dn2.y()*dn2.y());
dn2 = point_data<double>( dn2.x()*size, dn2.y()* size);
point_data<double> start_offset((start.x()+dn1.x()),(start.y()+dn1.y()));
point_data<double> mid1_offset((middle.x()+dn1.x()),(middle.y()+dn1.y()));
@@ -843,7 +847,7 @@ namespace boost { namespace polygon {
int num = make_arc(return_points[return_points.size()-1],mid1_offset,mid2_offset,dmid,sizing_distance,num_circle_segments);
curr_prev = round_down<T>(mid2_offset);
return num;
-
+
}
std::pair<point_data<double>,point_data<double> > he1(start_offset,mid1_offset);
@@ -881,21 +885,21 @@ namespace boost { namespace polygon {
// returnPoints will start with the first point after start
// returnPoints vector may be empty
template <typename T>
- inline int make_arc(std::vector<point_data< T> >& return_points,
+ inline int make_arc(std::vector<point_data< T> >& return_points,
point_data< double> start, point_data< double> end,
point_data< double> center, double r, unsigned int num_circle_segments) {
const double our_pi=3.1415926535897932384626433832795028841971;
- // derive start and end angles
+ // derive start and end angles
double ps = atan2(start.y()-center.y(), start.x()-center.x());
double pe = atan2(end.y()-center.y(), end.x()-center.x());
- if (ps < 0.0)
+ if (ps < 0.0)
ps += 2.0 * our_pi;
- if (pe <= 0.0)
+ if (pe <= 0.0)
pe += 2.0 * our_pi;
- if (ps >= 2.0 * our_pi)
+ if (ps >= 2.0 * our_pi)
ps -= 2.0 * our_pi;
- while (pe <= ps)
+ while (pe <= ps)
pe += 2.0 * our_pi;
double delta_angle = (2.0 * our_pi) / (double)num_circle_segments;
if ( start==end) // full circle?
@@ -941,12 +945,12 @@ namespace boost { namespace polygon {
inline connectivity_extraction() : ce_(), nodeCount_(0) {}
inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_),
nodeCount_(that.nodeCount_) {}
- inline connectivity_extraction& operator=(const connectivity_extraction& that) {
- ce_ = that.ce_;
+ inline connectivity_extraction& operator=(const connectivity_extraction& that) {
+ ce_ = that.ce_;
nodeCount_ = that.nodeCount_; {}
return *this;
}
-
+
//insert a polygon set graph node, the value returned is the id of the graph node
inline unsigned int insert(const polygon_set_data<coordinate_type>& ps) {
ps.clean();
@@ -959,7 +963,7 @@ namespace boost { namespace polygon {
ps.insert(geoObj);
return insert(ps);
}
-
+
//extract connectivity and store the edges in the graph
//graph must be indexable by graph node id and the indexed value must be a std::set of
//graph node id
@@ -997,4 +1001,3 @@ namespace boost { namespace polygon {
#include "polygon_set_concept.hpp"
#include "detail/minkowski.hpp"
#endif
-
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-24 07:27:51 +0000