summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/sort_by_side.hpp')
-rw-r--r--boost/geometry/algorithms/detail/overlay/sort_by_side.hpp160
1 files changed, 112 insertions, 48 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp
index bbba623eee..5ad2e41b12 100644
--- a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp
+++ b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp
@@ -2,6 +2,11 @@
// Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
+// This file was modified by Oracle on 2017.
+// Modifications copyright (c) 2017 Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
+
// Use, modification and distribution is 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)
@@ -10,11 +15,14 @@
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
#include <algorithm>
+#include <map>
#include <vector>
+#include <boost/geometry/algorithms/num_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
#include <boost/geometry/algorithms/detail/direction_code.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-#include <boost/geometry/strategies/side.hpp>
namespace boost { namespace geometry
{
@@ -37,7 +45,6 @@ struct ranked_point
, count_left(0)
, count_right(0)
, operation(operation_none)
- , only_turn_on_ring(false)
{}
template <typename Op>
@@ -53,7 +60,6 @@ struct ranked_point
, count_right(0)
, operation(op.operation)
, seg_id(op.seg_id)
- , only_turn_on_ring(op.enriched.only_turn_on_ring)
{}
Point point;
@@ -66,7 +72,6 @@ struct ranked_point
std::size_t count_right;
operation_type operation;
segment_identifier seg_id;
- bool only_turn_on_ring;
};
struct less_by_turn_index
@@ -105,17 +110,13 @@ struct less_false
}
};
-template <typename Point, typename LessOnSame, typename Compare>
+template <typename Point, typename SideStrategy, typename LessOnSame, typename Compare>
struct less_by_side
{
- typedef typename strategy::side::services::default_strategy
- <
- typename cs_tag<Point>::type
- >::type side;
-
- less_by_side(const Point& p1, const Point& p2)
+ less_by_side(const Point& p1, const Point& p2, SideStrategy const& strategy)
: m_p1(p1)
, m_p2(p2)
+ , m_strategy(strategy)
{}
template <typename T>
@@ -124,8 +125,8 @@ struct less_by_side
LessOnSame on_same;
Compare compare;
- int const side_first = side::apply(m_p1, m_p2, first.point);
- int const side_second = side::apply(m_p1, m_p2, second.point);
+ int const side_first = m_strategy.apply(m_p1, m_p2, first.point);
+ int const side_second = m_strategy.apply(m_p1, m_p2, second.point);
if (side_first == 0 && side_second == 0)
{
@@ -165,7 +166,7 @@ struct less_by_side
// They are both left, both right, and/or both collinear (with each other and/or with p1,p2)
// Check mutual side
- int const side_second_wrt_first = side::apply(m_p2, first.point, second.point);
+ int const side_second_wrt_first = m_strategy.apply(m_p2, first.point, second.point);
if (side_second_wrt_first == 0)
{
@@ -183,10 +184,19 @@ struct less_by_side
private :
Point m_p1, m_p2;
+ SideStrategy const& m_strategy;
};
// Sorts vectors in counter clockwise order (by default)
-template <bool Reverse1, bool Reverse2, typename Point, typename Compare>
+template
+<
+ bool Reverse1,
+ bool Reverse2,
+ overlay_type OverlayType,
+ typename Point,
+ typename SideStrategy,
+ typename Compare
+>
struct side_sorter
{
typedef ranked_point<Point> rp;
@@ -215,13 +225,14 @@ private :
};
public :
- inline void set_origin(Point const& origin)
- {
- m_origin = origin;
- }
+ side_sorter(SideStrategy const& strategy)
+ : m_origin_count(0)
+ , m_origin_segment_distance(0)
+ , m_strategy(strategy)
+ {}
template <typename Operation, typename Geometry1, typename Geometry2>
- void add(Operation const& op, signed_size_type turn_index, signed_size_type op_index,
+ Point add(Operation const& op, signed_size_type turn_index, signed_size_type op_index,
Geometry1 const& geometry1,
Geometry2 const& geometry2,
bool is_origin)
@@ -233,11 +244,63 @@ public :
m_ranked_points.push_back(rp(point1, turn_index, op_index, dir_from, op));
m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op));
-
if (is_origin)
{
m_origin = point1;
+ m_origin_count++;
}
+ return point1;
+ }
+
+ template <typename Operation, typename Geometry1, typename Geometry2>
+ void add(Operation const& op, signed_size_type turn_index, signed_size_type op_index,
+ segment_identifier const& departure_seg_id,
+ Geometry1 const& geometry1,
+ Geometry2 const& geometry2,
+ bool check_origin)
+ {
+ Point const point1 = add(op, turn_index, op_index, geometry1, geometry2, false);
+
+ if (check_origin)
+ {
+ bool const is_origin
+ = op.seg_id.source_index == departure_seg_id.source_index
+ && op.seg_id.ring_index == departure_seg_id.ring_index
+ && op.seg_id.multi_index == departure_seg_id.multi_index;
+
+ if (is_origin)
+ {
+ int const segment_distance = calculate_segment_distance(op, departure_seg_id, geometry1, geometry2);
+ if (m_origin_count == 0 ||
+ segment_distance < m_origin_segment_distance)
+ {
+ m_origin = point1;
+ m_origin_segment_distance = segment_distance;
+ }
+ m_origin_count++;
+ }
+ }
+ }
+
+ template <typename Operation, typename Geometry1, typename Geometry2>
+ static int calculate_segment_distance(Operation const& op,
+ segment_identifier const& departure_seg_id,
+ Geometry1 const& geometry1,
+ Geometry2 const& geometry2)
+ {
+ if (op.seg_id.segment_index >= departure_seg_id.segment_index)
+ {
+ return op.seg_id.segment_index - departure_seg_id.segment_index;
+ }
+ // Take wrap into account
+ // Suppose ring_count=10 (10 points, 9 segments), dep.seg_id=7, op.seg_id=2, then distance=10-9+2
+ // Generic function (is this used somewhere else too?)
+ ring_identifier const rid(op.seg_id.source_index, op.seg_id.multi_index, op.seg_id.ring_index);
+ int const segment_count
+ (op.seg_id.source_index == 0
+ ? geometry::num_points(detail::overlay::get_ring<typename geometry::tag<Geometry1>::type>::apply(rid, geometry1))
+ : geometry::num_points(detail::overlay::get_ring<typename geometry::tag<Geometry2>::type>::apply(rid, geometry2)));
+ return ((segment_count - 1) - departure_seg_id.segment_index) + op.seg_id.segment_index;
}
void apply(Point const& turn_point)
@@ -249,8 +312,8 @@ public :
// to give colinear points
// Sort by side and assign rank
- less_by_side<Point, less_by_index, Compare> less_unique(m_origin, turn_point);
- less_by_side<Point, less_false, Compare> less_non_unique(m_origin, turn_point);
+ less_by_side<Point, SideStrategy, less_by_index, Compare> less_unique(m_origin, turn_point, m_strategy);
+ less_by_side<Point, SideStrategy, less_false, Compare> less_non_unique(m_origin, turn_point, m_strategy);
std::sort(m_ranked_points.begin(), m_ranked_points.end(), less_unique);
@@ -269,7 +332,7 @@ public :
}
template <signed_size_type segment_identifier::*Member, typename Map>
- void find_open_generic(Map& handled)
+ void find_open_generic(Map& handled, bool check)
{
for (std::size_t i = 0; i < m_ranked_points.size(); i++)
{
@@ -280,6 +343,11 @@ public :
}
signed_size_type const& index = ranked.seg_id.*Member;
+ if (check && (index < 0 || index > 1))
+ {
+ // Should not occur
+ continue;
+ }
if (! handled[index])
{
find_polygons_for_source<Member>(index, i);
@@ -290,36 +358,23 @@ public :
void find_open()
{
- // TODO: we might pass Buffer as overlay_type, instead on the fly below
- bool one_source = true;
- for (std::size_t i = 0; i < m_ranked_points.size(); i++)
- {
- const rp& ranked = m_ranked_points[i];
- signed_size_type const& src = ranked.seg_id.source_index;
- if (src != 0)
- {
- one_source = false;
- break;
- }
- }
-
- if (one_source)
+ if (OverlayType == overlay_buffer)
{
- // by multi index
+ // For buffers, use piece index
std::map<signed_size_type, bool> handled;
find_open_generic
<
&segment_identifier::piece_index
- >(handled);
+ >(handled, false);
}
else
{
- // by source (there should only source 0,1) TODO assert this
+ // For other operations, by source (there should only source 0,1)
bool handled[2] = {false, false};
find_open_generic
<
&segment_identifier::source_index
- >(handled);
+ >(handled, true);
}
}
@@ -361,11 +416,19 @@ public :
}
}
+ bool has_origin() const
+ {
+ return m_origin_count > 0;
+ }
+
//private :
typedef std::vector<rp> container_type;
container_type m_ranked_points;
Point m_origin;
+ std::size_t m_origin_count;
+ int m_origin_segment_distance;
+ SideStrategy m_strategy;
private :
@@ -439,9 +502,10 @@ private :
void find_polygons_for_source(signed_size_type the_index,
std::size_t start_index)
{
- int state = 1; // 'closed', because start_index is "from", arrives at the turn
- std::size_t last_from_rank = m_ranked_points[start_index].rank;
- std::size_t previous_rank = m_ranked_points[start_index].rank;
+ bool in_polygon = true; // Because start_index is "from", arrives at the turn
+ rp const& start_rp = m_ranked_points[start_index];
+ std::size_t last_from_rank = start_rp.rank;
+ std::size_t previous_rank = start_rp.rank;
for (std::size_t index = move<Member>(the_index, start_index);
;
@@ -449,7 +513,7 @@ private :
{
rp& ranked = m_ranked_points[index];
- if (ranked.rank != previous_rank && state == 0)
+ if (ranked.rank != previous_rank && ! in_polygon)
{
assign_ranks(last_from_rank, previous_rank - 1, 1);
assign_ranks(last_from_rank + 1, previous_rank, 2);
@@ -463,11 +527,11 @@ private :
if (ranked.direction == dir_from)
{
last_from_rank = ranked.rank;
- state++;
+ in_polygon = true;
}
else if (ranked.direction == dir_to)
{
- state--;
+ in_polygon = false;
}
previous_rank = ranked.rank;