Subject: [Boost-commit] svn:boost r61544 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/algorithms/detail/overlay boost/geometry/algorithms/overlay boost/geometry/multi boost/geometry/multi/algorithms boost/geometry/multi/algorithms/detail/overlay boost/geometry/multi/algorithms/overlay libs/geometry/test/algorithms libs/geometry/test/algorithms/overlay libs/geometry/test/algorithms/overlay/robustness libs/geometry/test/multi/algorithms libs/geometry/test/multi/algorithms/overlay
From: barend.gehrels_at_[hidden]
Date: 2010-04-24 12:58:03
Author: barendgehrels
Date: 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
New Revision: 61544
URL: http://svn.boost.org/trac/boost/changeset/61544
Log:
Move overlay -> detail/overlay phase 2, moving files and adapting includes
Added:
sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/clip_linestring.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/msm_state.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/msm_state.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/segment_identifier.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp
sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/assemble.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segments.hpp
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/self_turn_points.hpp
- copied, changed from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/self_turn_points.hpp
Removed:
sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/clip_linestring.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/msm_state.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/segment_identifier.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp
sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp
sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp
sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp
sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segments.hpp
sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp
sandbox/geometry/boost/geometry/multi/algorithms/overlay/self_turn_points.hpp
Text files modified:
sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp | 12 ++++++------
sandbox/geometry/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp | 6 +++---
sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp | 6 +++---
sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp | 6 +++---
sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp | 8 ++++----
sandbox/geometry/boost/geometry/algorithms/detail/overlay/msm_state.hpp | 6 +++---
sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp | 7 +++----
sandbox/geometry/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp | 6 +++---
sandbox/geometry/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp | 8 ++++----
sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/stream_info.hpp | 6 +++---
sandbox/geometry/boost/geometry/algorithms/detail/overlay/traversal_info.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp | 8 ++++----
sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/visit_info.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/disjoint.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/dissolve.hpp | 10 +++++-----
sandbox/geometry/boost/geometry/algorithms/intersection.hpp | 4 ++--
sandbox/geometry/boost/geometry/algorithms/intersects.hpp | 2 +-
sandbox/geometry/boost/geometry/algorithms/union.hpp | 2 +-
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/assemble.hpp | 15 ++++++++-------
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp | 8 ++++----
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp | 8 ++++----
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp | 9 ++++-----
sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/self_turn_points.hpp | 11 +++++------
sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp | 2 +-
sandbox/geometry/boost/geometry/multi/algorithms/union.hpp | 2 +-
sandbox/geometry/boost/geometry/multi/multi.hpp | 4 ++--
sandbox/geometry/libs/geometry/test/algorithms/difference.cpp | 22 +++++++++++-----------
sandbox/geometry/libs/geometry/test/algorithms/overlay/enrich_intersection_points.cpp | 6 +++---
sandbox/geometry/libs/geometry/test/algorithms/overlay/get_turns.cpp | 2 +-
sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_pies.cpp | 6 +-----
sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_stars.cpp | 8 ++++++++
sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/random_ellipses_stars.cpp | 12 +-----------
sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/recursive_boxes.cpp | 11 ++++-------
sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/test_overlay_p_q.hpp | 8 ++++++++
sandbox/geometry/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp | 4 ++--
sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse.cpp | 14 +++++++-------
sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse_gmp.cpp | 6 +++---
sandbox/geometry/libs/geometry/test/algorithms/test_overlay.hpp | 2 +-
sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp | 2 +-
sandbox/geometry/libs/geometry/test/multi/algorithms/multi_union.cpp | 2 +-
sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp | 8 ++++----
45 files changed, 140 insertions(+), 143 deletions(-)
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/assemble.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,8 +5,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
#include <deque>
@@ -24,9 +24,9 @@
#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/algorithms/overlay/enrich_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/traverse.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
#include <boost/geometry/algorithms/convert.hpp>
@@ -837,4 +837,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/clip_linestring.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/clip_linestring.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -6,8 +6,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_CLIP_LINESTRING_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_CLIP_LINESTRING_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP
#include <boost/range.hpp>
@@ -237,4 +237,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_CLIP_LINESTRING_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -6,8 +6,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENT_POINT_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENT_POINT_HPP
#include <boost/range.hpp>
@@ -272,4 +272,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENT_POINT_HPP
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/copy_segments.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -6,8 +6,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
#include <vector>
@@ -223,4 +223,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -24,7 +24,7 @@
#include <boost/geometry/algorithms/disjoint.hpp>
#include <boost/geometry/algorithms/detail/disjoint.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/intersection.hpp>
#include <boost/geometry/algorithms/union.hpp>
#include <boost/geometry/algorithms/reverse.hpp>
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -25,7 +25,7 @@
#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
-#include <boost/geometry/algorithms/overlay/copy_segment_point.hpp>
+#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_relative_order.hpp>
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turns.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,8 +5,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_TURNS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_TURNS_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
#include <cstddef>
@@ -42,7 +42,7 @@
#include <boost/geometry/algorithms/detail/disjoint.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
-#include <boost/geometry/algorithms/overlay/segment_identifier.hpp>
+#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
#include <boost/geometry/algorithms/detail/sections/get_full_section.hpp>
@@ -884,4 +884,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_TURNS_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/msm_state.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/msm_state.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/msm_state.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/msm_state.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -6,8 +6,8 @@
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_MSM_STATE_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_MSM_STATE_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_MSM_STATE_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_MSM_STATE_HPP
@@ -183,4 +183,4 @@
#endif
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_MSM_STATE_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_MSM_STATE_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/ring_properties.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,8 +5,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALG_DET_OV_RING_PROPERTIES_HPP
-#define BOOST_GEOMETRY_ALG_DET_OV_RING_PROPERTIES_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RING_PROPERTIES_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RING_PROPERTIES_HPP
#include <boost/geometry/algorithms/area.hpp>
@@ -224,8 +224,7 @@
};
-
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALG_DET_OV_RING_PROPERTIES_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RING_PROPERTIES_HPP
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/segment_identifier.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/segment_identifier.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -6,8 +6,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SEGMENT_IDENTIFIER_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SEGMENT_IDENTIFIER_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SEGMENT_IDENTIFIER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SEGMENT_IDENTIFIER_HPP
#if defined(BOOST_GEOMETRY_DEBUG_OVERLAY)
@@ -89,4 +89,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SEGMENT_IDENTIFIER_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SEGMENT_IDENTIFIER_HPP
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,8 +5,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
#include <cstddef>
@@ -19,7 +19,7 @@
#include <boost/geometry/geometries/concepts/check.hpp>
#include <boost/geometry/algorithms/detail/disjoint.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
namespace boost { namespace geometry
@@ -211,4 +211,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -16,7 +16,7 @@
#include <boost/range.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/core/point_type.hpp>
#include <boost/geometry/core/ring_type.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/stream_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/stream_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/stream_info.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,8 +5,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TURN_INFO_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TURN_INFO_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_STREAM_INFO_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_STREAM_INFO_HPP
#include <string>
@@ -71,4 +71,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TURN_INFO_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_STREAM_INFO_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/traversal_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/traversal_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/traversal_info.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -12,7 +12,7 @@
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/visit_info.hpp>
-#include <boost/geometry/algorithms/overlay/segment_identifier.hpp>
+#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
namespace boost { namespace geometry
Copied: sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp (from r61534, /sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/traverse.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,8 +5,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_TRAVERSE_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_TRAVERSE_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
#include <cstddef>
@@ -14,7 +14,7 @@
#include <boost/range.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-#include <boost/geometry/algorithms/overlay/copy_segments.hpp>
+#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/coordinate_dimension.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
@@ -408,4 +408,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_TRAVERSE_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -11,7 +11,7 @@
#include <boost/array.hpp>
-#include <boost/geometry/algorithms/overlay/segment_identifier.hpp>
+#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
namespace boost { namespace geometry
{
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/visit_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/visit_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/visit_info.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -10,7 +10,7 @@
#ifdef BOOST_GEOMETRY_USE_MSM
-# include <boost/geometry/algorithms/overlay/msm_state.hpp>
+# include <boost/geometry/algorithms/detail/overlay/msm_state.hpp>
#endif
Modified: sandbox/geometry/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/disjoint.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/disjoint.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -42,7 +42,7 @@
#include <boost/geometry/algorithms/detail/disjoint.hpp>
#include <boost/geometry/algorithms/detail/point_on_border.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/dissolve.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/dissolve.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/dissolve.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -14,8 +14,8 @@
#include <boost/range.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/algorithms/overlay/self_turn_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
@@ -24,9 +24,9 @@
#include <boost/geometry/algorithms/detail/point_on_border.hpp>
-#include <boost/geometry/algorithms/overlay/enrich_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/traverse.hpp>
-#include <boost/geometry/algorithms/overlay/assemble.hpp>
+#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
+#include <boost/geometry/algorithms/detail/overlay/assemble.hpp>
#include <boost/geometry/algorithms/convert.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/intersection.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/intersection.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/intersection.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -18,8 +18,8 @@
#include <boost/geometry/core/reverse_dispatch.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/algorithms/overlay/clip_linestring.hpp>
-#include <boost/geometry/algorithms/overlay/assemble.hpp>
+#include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp>
+#include <boost/geometry/algorithms/detail/overlay/assemble.hpp>
Modified: sandbox/geometry/boost/geometry/algorithms/intersects.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/intersects.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/intersects.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -35,7 +35,7 @@
#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/algorithms/overlay/self_turn_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
#include <boost/geometry/algorithms/disjoint.hpp>
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/assemble.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,840 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
-
-
-#include <deque>
-#include <map>
-#include <vector>
-
-#include <boost/range.hpp>
-
-
-#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
-#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
-#include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
-
-#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
-
-
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/algorithms/overlay/enrich_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/traverse.hpp>
-
-
-#include <boost/geometry/algorithms/convert.hpp>
-#include <boost/geometry/algorithms/combine.hpp>
-#include <boost/geometry/algorithms/envelope.hpp>
-#include <boost/geometry/algorithms/num_points.hpp>
-#include <boost/geometry/algorithms/within.hpp>
-
-#include <boost/geometry/algorithms/detail/point_on_border.hpp>
-
-#include <boost/geometry/iterators/range_type.hpp>
-
-#include <boost/geometry/strategies/intersection.hpp>
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-# include <boost/geometry/util/write_dsv.hpp>
-#endif
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template<typename Tag>
-struct get_ring
-{};
-
-template<>
-struct get_ring<ring_tag>
-{
- template<typename Ring>
- static inline Ring const& apply(ring_identifier const& , Ring const& ring)
- {
- return ring;
- }
-};
-
-
-template<>
-struct get_ring<void>
-{
- template<typename Container>
- static inline typename boost::range_value<Container>::type const&
- apply(ring_identifier const& id, Container const& container)
- {
- return container[id.multi_index];
- }
-};
-
-
-template<>
-struct get_ring<box_tag>
-{
- template<typename Box>
- static inline Box const& apply(ring_identifier const& ,
- Box const& box)
- {
- return box;
- }
-};
-
-
-template<>
-struct get_ring<polygon_tag>
-{
- template<typename Polygon>
- static inline typename ring_type<Polygon>::type const& apply(
- ring_identifier const& id,
- Polygon const& polygon)
- {
- BOOST_ASSERT
- (
- id.ring_index >= -1
- && id.ring_index < boost::size(interior_rings(polygon))
- );
- return id.ring_index < 0
- ? exterior_ring(polygon)
- : interior_rings(polygon)[id.ring_index];
- }
-};
-
-
-
-
-template<typename Tag>
-struct convert_ring
-{};
-
-template<>
-struct convert_ring<ring_tag>
-{
- template<typename Destination, typename Source>
- static inline void apply(Destination& destination, Source const& source,
- bool append = false)
- {
- if (! append)
- {
- geometry::convert(source, destination);
- }
- }
-};
-
-
-
-
-template<>
-struct convert_ring<polygon_tag>
-{
- template<typename Destination, typename Source>
- static inline void apply(Destination& destination, Source const& source,
- bool append = false)
- {
- if (! append)
- {
- geometry::convert(source, exterior_ring(destination));
- }
- else
- {
- interior_rings(destination).resize(
- interior_rings(destination).size() + 1);
- geometry::convert(source, interior_rings(destination).back());
- }
- }
-};
-
-
-
-template <typename Tag, typename Geometry>
-struct add_to_containment
-{};
-
-template <typename Ring>
-struct add_to_containment<ring_tag, Ring>
-{
- template <typename ContainmentContainer, typename Map>
- static inline void apply(ContainmentContainer& container,
- ring_identifier const& id, Ring const& ring, Map const& map,
- bool dissolve)
- {
- typedef typename range_value<ContainmentContainer>::type prop;
- bool found = map.find(id) != map.end();
- if (! dissolve || ! found)
- {
- // For dissolve, do not add intersected rings
- container.push_back(prop(id, ring, found));
- }
- }
-};
-
-template <typename Box>
-struct add_to_containment<box_tag, Box>
-{
- template <typename ContainmentContainer, typename Map>
- static inline void apply(ContainmentContainer& container,
- ring_identifier const& id, Box const& box, Map const& map,
- bool dissolve)
- {
- typedef typename range_value<ContainmentContainer>::type prop;
- bool found = map.find(id) != map.end();
- if (! dissolve || ! found)
- {
- container.push_back(prop(id, box, found));
- }
- }
-};
-
-
-template <typename Polygon>
-struct add_to_containment<polygon_tag, Polygon>
-{
- template <typename ContainmentContainer, typename Map>
- static inline void apply(ContainmentContainer& container,
- ring_identifier const& id, Polygon const& polygon, Map const& map,
- bool dissolve)
- {
- // Add exterior ring and interior rings
- ring_identifier copy = id;
-
- typedef add_to_containment
- <
- ring_tag,
- typename ring_type<Polygon>::type
- > policy;
-
- policy::apply(container, copy, exterior_ring(polygon), map, dissolve);
- copy.ring_index = 0;
- for (typename boost::range_iterator
- <
- typename interior_type<Polygon>::type const
- >::type it = boost::begin(interior_rings(polygon));
- it != boost::end(interior_rings(polygon));
- ++it, ++copy.ring_index)
- {
- policy::apply(container, copy, *it, map, dissolve);
- }
- }
-};
-
-
-
-template <typename TurnPoints, typename Map>
-inline void map_turns(Map& map, TurnPoints const& turn_points)
-{
- typedef typename boost::range_value<TurnPoints>::type turn_point_type;
- typedef typename turn_point_type::container_type container_type;
-
- int index = 0;
- for (typename boost::range_iterator<TurnPoints const>::type
- it = boost::begin(turn_points);
- it != boost::end(turn_points);
- ++it, ++index)
- {
- if (! it->ignore)
- {
- int op_index = 0;
- for (typename boost::range_iterator<container_type const>::type
- op_it = boost::begin(it->operations);
- op_it != boost::end(it->operations);
- ++op_it, ++op_index)
- {
- ring_identifier ring_id
- (
- op_it->seg_id.source_index,
- op_it->seg_id.multi_index,
- op_it->seg_id.ring_index
- );
- map[ring_id]++;
- }
- }
- }
-}
-
-
-template
-<
- typename Container,
- typename Geometry1,
- typename Geometry2,
- typename RingCollection,
- typename Box
->
-struct enrich_containment
-{
-
- typedef typename boost::range_value<Container>::type item_type;
- typedef typename geometry::tag<Geometry1>::type tag1;
- typedef typename geometry::tag<Geometry2>::type tag2;
- typedef void tag3; // For the ring-container
-
-
- static inline void assign(item_type& larger, item_type& smaller, int direction, bool dissolve)
- {
- typedef typename geometry::coordinate_type
- <
- Geometry1
- >::type coordinate_type;
-
- if (larger.signum != 0 && smaller.signum != 0)
- {
- if (larger.signum == 1)
- {
- smaller.push(larger, direction, dissolve);
- }
- else if (larger.signum == -1)
- {
- smaller.pop(/*from*/larger);
- }
- }
- }
-
-
- // Creates a selection of pointers within the specified box
- template <typename Collection>
- static inline void select_by_box(Collection& selection,
- Collection const& collection,
- Box const& box)
- {
- for (typename boost::range_iterator<Collection const>::type
- it = boost::begin(collection);
- it != boost::end(collection);
- ++it)
- {
- if (! geometry::detail::disjoint::disjoint_box_box(box, (*it)->box))
- {
- selection.push_back(*it);
- }
- }
- }
-
- static inline bool contains(item_type const& item1, item_type const& item2,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- RingCollection const& collection)
- {
- if (item1.ring_id.source_index == 0)
- {
- return geometry::within(item2.point,
- get_ring<tag1>::apply(item1.ring_id, geometry1));
- }
- else if (item1.ring_id.source_index == 1)
- {
- return geometry::within(item2.point,
- get_ring<tag2>::apply(item1.ring_id, geometry2));
- }
- else if (item1.ring_id.source_index == 2)
- {
- return geometry::within(item2.point,
- get_ring<tag3>::apply(item1.ring_id, collection));
- }
- return false;
- }
-
- template <typename Selection, typename Map>
- static inline void enrich(Selection& selection, Map& map,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- RingCollection const& collection,
- int direction, bool dissolve)
- {
- typedef typename boost::range_iterator<Selection>::type iterator;
-
- for (iterator it1 = boost::begin(selection);
- it1 != boost::end(selection);
- ++it1)
- {
-//std::cout << ".";
- item_type& item1 = **it1;
- iterator it2 = it1;
- for (it2++; it2 != boost::end(selection); ++it2)
- {
- std::pair<item_type*, item_type*> p
- = std::make_pair(*it1, *it2);
- bool processed = map[p];
- if (! processed)
- {
- map[p] = true;
-
- item_type& item2 = **it2;
- if (geometry::within(item2.point, item1.box)
- && abs(item2.area) < abs(item1.area)
- && contains(item1, item2, geometry1, geometry2,
- collection)
- )
- {
- assign(item1, item2, direction, dissolve);
- }
- }
- }
- }
- }
-
- /***
- template <int Dimension, typename Selection, typename Map>
- static inline void divide_and_conquer(Selection& selection, Map& map,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- RingCollection const& collection,
- int direction, bool dissolve, Box const& box,
- std::size_t iteration = 0, std::size_t previous_count = 0)
- {
- std::size_t n = boost::size(selection);
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "spatial divide n="
-<< n
-<< " previous=" << previous_count
-<< " iteration=" << iteration
-<< " box: " << geometry::dsv(box) << std::endl;
-#endif
-
- if (iteration > 3)
- {
- enrich(selection, map, geometry1, geometry2, collection, direction, dissolve);
- return;
- }
-
- // Divide the complete box in two (alternating) halves
- Box lower = box, upper = box;
- typedef typename geometry::coordinate_type<Box>::type coordinate_type;
- coordinate_type two = 2.0;
- coordinate_type mid
- = (geometry::get<min_corner, Dimension>(box)
- + geometry::get<max_corner, Dimension>(box)) / two;
-
- geometry::set<max_corner, Dimension>(lower, mid);
- geometry::set<min_corner, Dimension>(upper, mid);
-
- // select
- std::vector<item_type*> lower_sel, upper_sel;
- select_by_box(lower_sel, selection, lower);
- select_by_box(upper_sel, selection, upper);
-
- divide_and_conquer<1 - Dimension>(lower_sel, map, geometry1, geometry2,
- collection, direction, dissolve, lower, iteration + 1, n);
- divide_and_conquer<1 - Dimension>(upper_sel, map, geometry1, geometry2,
- collection, direction, dissolve, upper, iteration + 1, n);
- }
- ***/
-
- static inline void enrich(Container& container,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- RingCollection const& collection,
- int direction, bool dissolve)
- {
- typedef typename boost::range_iterator<Container>::type iterator;
-
- int n = 0;
-
- for (iterator it1 = boost::begin(container);
- it1 != boost::end(container);
- ++it1)
- {
- item_type& item1 = *it1;
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << item1.ring_id << " area: " << item1.area << std::endl;
-#endif
- iterator it2 = it1;
- for (it2++; it2 != boost::end(container); ++it2)
- {
- item_type& item2 = *it2;
- if (geometry::within(item2.point, item1.box)
- && std::abs(item2.area) < std::abs(item1.area)
- && contains(item1, item2, geometry1, geometry2, collection)
- )
- {
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << " -> contains " << item2.ring_id;
-#endif
- n++;
- assign(item1, item2, direction, dissolve);
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << std::endl;
-#endif
- }
- }
- }
- //std::cout << "Enriched: " << n << std::endl;
- }
-
-
-
- static inline void apply(Container& container,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- RingCollection const& collection,
- int direction, bool dissolve, Box const& )
- {
- if (boost::size(container) == 0)
- {
- return;
- }
- enrich(container, geometry1, geometry2, collection, direction, dissolve);
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
- for (typename boost::range_iterator<Container const>::type
- it = boost::begin(container);
- it != boost::end(container);
- ++it)
- {
- std::cout << *it << std::endl;
- }
-#endif
-
- /***
- return;
-
- // Method using divide and conquer (does NOT work corretly!)
-
- std::vector<item_type*> selection;
- selection.reserve(boost::size(container));
- for (typename boost::range_iterator<Container>::type
- it = boost::begin(container);
- it != boost::end(container);
- ++it)
- {
- selection.push_back(&(*it));
- }
-
- std::map<std::pair<item_type*, item_type*>, bool> map;
- divide_and_conquer<1>(selection, map, geometry1, geometry2, collection,
- direction, dissolve, box);
- ***/
- }
-};
-
-
-template
-<
- typename GeometryOut,
- typename Container,
- typename Geometry1,
- typename Geometry2,
- typename RingCollection,
- typename OutputIterator
->
-inline OutputIterator add_all_rings(Container& container,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- RingCollection const& collection,
- int direction, bool dissolve,
- OutputIterator out)
-{
- typedef typename boost::range_iterator<Container>::type iterator;
- typedef typename geometry::tag<GeometryOut>::type tag_out;
- typedef typename geometry::tag<Geometry1>::type tag1;
- typedef typename geometry::tag<Geometry2>::type tag2;
- typedef void tag3; // For the ring-container
-
-
- bool result_filled = false;
- GeometryOut result;
- ring_identifier previous_id;
- previous_id.source_index = -1;
-
- for (iterator it = boost::begin(container);
- it != boost::end(container);
- ++it)
- {
- if (it->positive())
- {
- if (result_filled)
- {
- *out++ = result;
- previous_id.source_index = -1;
- result_filled = false;
- }
-
- // If it is an outer ring, it is included if there are no parents
- // (union) or if there are parents (intersection)
- if (it->included(direction, dissolve))
- {
- geometry::clear(result);
- previous_id = it->ring_id;
- result_filled = true;
- if (it->ring_id.source_index == 0)
- {
- convert_ring<tag_out>::apply(result,
- get_ring<tag1>::apply(it->ring_id, geometry1));
- }
- else if (it->ring_id.source_index == 1)
- {
- convert_ring<tag_out>::apply(result,
- get_ring<tag2>::apply(it->ring_id, geometry2));
- }
- else if (it->ring_id.source_index == 2)
- {
- convert_ring<tag_out>::apply(result,
- get_ring<tag3>::apply(it->ring_id, collection));
- }
- }
- }
- else
- {
- // If it is an interior ring, it is included if
- // it's parent-id matches the id of the outputted exterior ring
- if (result_filled
- && it->id() == previous_id
- && it->included(direction, dissolve))
- {
- if (it->ring_id.source_index == 0)
- {
- convert_ring<tag_out>::apply(result,
- get_ring<tag1>::apply(it->ring_id,
- geometry1), true);
- }
- else if (it->ring_id.source_index == 1)
- {
- convert_ring<tag_out>::apply(result,
- get_ring<tag2>::apply(it->ring_id,
- geometry2), true);
- }
- else if (it->ring_id.source_index == 2)
- {
- convert_ring<tag_out>::apply(result,
- get_ring<tag3>::apply(it->ring_id,
- collection), true);
- }
- }
- }
- }
- if (result_filled)
- {
- *out++ = result;
- }
- return out;
-}
-
-
-template
-<
- typename GeometryOut,
- typename Rings, typename Map,
- typename Geometry1, typename Geometry2,
- typename OutputIterator
->
-inline OutputIterator assemble(Rings const& rings, Map const& map,
- Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- int direction, bool dissolve, bool splitted,
- OutputIterator out)
-{
- typedef typename geometry::tag<Geometry1>::type tag1;
- typedef typename geometry::tag<Geometry2>::type tag2;
- typedef typename geometry::tag<GeometryOut>::type tag_out;
-
- typedef typename geometry::point_type<GeometryOut>::type point_type;
- typedef typename boost::range_value<Rings>::type ring_type;
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble" << std::endl;
-#endif
-
- typedef std::vector
- <
- ring_properties<point_type>
- > ring_properties_container_type;
- ring_properties_container_type ring_properties_container;
-
- if (! splitted)
- {
- add_to_containment
- <
- tag1,
- Geometry1
- >::apply(ring_properties_container,
- ring_identifier(0, -1,-1), geometry1,
- map, dissolve);
- }
- if (! dissolve)
- {
- add_to_containment
- <
- tag2,
- Geometry2
- >::apply(ring_properties_container,
- ring_identifier(1, -1,-1), geometry2,
- map, dissolve);
- }
-
- // Add all produced rings using source index 2
- {
- ring_identifier id(2, 0, -1);
- for (typename std::vector<ring_type>::const_iterator
- it = boost::begin(rings);
- it != boost::end(rings);
- ++it, ++id.multi_index)
- {
- ring_properties_container.push_back(
- ring_properties<point_type>(id, *it, false, true));
- }
- }
-
- bool only_positive = true;
- {
- int pos=0, neg=0;
- for (typename ring_properties_container_type::const_iterator
- it = boost::begin(ring_properties_container);
- it != boost::end(ring_properties_container);
- ++it)
- {
- if (it->positive())
- {
- pos++;
- }
- else
- {
- neg++;
- only_positive = false;
- }
- }
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
- std::cout << "assemble, pos=" << pos << " neg=" << neg << std::endl;
-#endif
- }
-
- //if (! only_positive)
- {
- typedef geometry::box<point_type> box_type;
- box_type total = geometry::make_envelope<box_type>(geometry1);
- geometry::combine(total,
- geometry::make_envelope<box_type>(geometry2));
-
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.properties sort "
- << boost::size(ring_properties_container) << std::endl;
-#endif
- std::sort(boost::begin(ring_properties_container),
- boost::end(ring_properties_container));
-
-
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.enrich containment" << std::endl;
-#endif
- enrich_containment
- <
- ring_properties_container_type,
- Geometry1,
- Geometry2,
- std::vector<ring_type>,
- geometry::box<point_type>
- >::apply(ring_properties_container,
- geometry1, geometry2, rings, direction, dissolve, total);
-
- // Sort container on parent-id
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.properties sort on parent-id "
- << boost::size(ring_properties_container) << std::endl;
-#endif
- std::sort(boost::begin(ring_properties_container),
- boost::end(ring_properties_container),
- sort_on_id_or_parent_id
- <
- ring_properties<point_type>
- >());
- }
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "assemble.add rings" << std::endl;
-#endif
- return add_all_rings<GeometryOut>(ring_properties_container,
- geometry1, geometry2, rings, direction, dissolve, out);
-}
-
-
-template
-<
- typename Geometry1, typename Geometry2,
- typename OutputIterator, typename GeometryOut,
- int Direction,
- typename Strategy
->
-struct overlay
-{
- static inline OutputIterator apply(
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- OutputIterator out,
- Strategy const& )
- {
- if (geometry::num_points(geometry1) == 0 && geometry::num_points(geometry2) == 0)
- {
- return out;
- }
-
- typedef typename geometry::point_type<GeometryOut>::type point_type;
- typedef detail::overlay::traversal_turn_info<point_type> turn_info;
- typedef std::deque<turn_info> container_type;
-
- // "Use" rangetype for ringtype:
- // for polygon, it is the type of the exterior ring.
- // for ring, it is the ring itself. That is what is
- // for multi-polygon, it is also the type of the ring.
- typedef typename geometry::range_type<GeometryOut>::type ring_type;
-
- // If one input is empty, output the other one for a union.
- // For an intersection, the intersection is empty.
- if (geometry::num_points(geometry1) == 0
- || geometry::num_points(geometry2) == 0)
- {
- if (Direction == 1)
- {
- std::map<ring_identifier, int> map;
- std::vector<ring_type> rings;
- return assemble<GeometryOut>(rings, map,
- geometry1, geometry2, Direction, false, false, out);
- }
- return out;
- }
-
- container_type turn_points;
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "get turns" << std::endl;
-#endif
- detail::get_turns::no_interrupt_policy policy;
- boost::geometry::get_turns
- <
- detail::overlay::calculate_distance_policy
- >(geometry1, geometry2, turn_points, policy);
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "enrich" << std::endl;
-#endif
- typename Strategy::side_strategy_type side_strategy;
- geometry::enrich_intersection_points(turn_points, geometry1, geometry2,
- side_strategy);
-
-#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
-std::cout << "traverse" << std::endl;
-#endif
- std::vector<ring_type> rings;
- geometry::traverse(geometry1, geometry2,
- Direction == -1
- ? boost::geometry::detail::overlay::operation_intersection
- : boost::geometry::detail::overlay::operation_union
- ,
- turn_points, rings);
-
- std::map<ring_identifier, int> map;
- map_turns(map, turn_points);
- return assemble<GeometryOut>(rings, map,
- geometry1, geometry2, Direction, false, false, out);
- }
-};
-
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/clip_linestring.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/clip_linestring.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,240 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_CLIP_LINESTRING_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_CLIP_LINESTRING_HPP
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/algorithms/append.hpp>
-#include <boost/geometry/algorithms/clear.hpp>
-#include <boost/geometry/util/copy.hpp>
-#include <boost/geometry/util/select_coordinate_type.hpp>
-#include <boost/geometry/geometries/segment.hpp>
-
-namespace boost { namespace geometry
-{
-
-namespace strategy { namespace intersection
-{
-
-/*!
- \brief Strategy: line clipping algorithm after Liang Barsky
- \ingroup overlay
- \details The Liang-Barsky line clipping algorithm clips a line with a clipping box.
- It is slightly adapted in the sense that it returns which points are clipped
- \tparam B input box type of clipping box
- \tparam P input/output point-type of segments to be clipped
- \note The algorithm is currently only implemented for 2D Cartesian points
- \note Though it is implemented in namespace strategy, and theoretically another
- strategy could be used, it is not (yet) updated to the general strategy concepts,
- and not (yet) splitted into a file in folder strategies
- \author Barend Gehrels, and the following recourses
- - A tutorial: http://www.skytopia.com/project/articles/compsci/clipping.html
- - a German applet (link broken): http://ls7-www.cs.uni-dortmund.de/students/projectgroups/acit/lineclip.shtml
-*/
-template<typename Box, typename Point>
-class liang_barsky
-{
-private:
- typedef geometry::segment<Point> segment_type;
-
- template <typename T>
- inline bool check_edge(T const& p, T const& q, T& t1, T& t2) const
- {
- bool visible = true;
-
- if(p < 0)
- {
- T const r = q / p;
- if (r > t2)
- visible = false;
- else if (r > t1)
- t1 = r;
- }
- else if(p > 0)
- {
- T const r = q / p;
- if (r < t1)
- visible = false;
- else if (r < t2)
- t2 = r;
- }
- else
- {
- if (q < 0)
- visible = false;
- }
-
- return visible;
- }
-
-public:
-
- inline bool clip_segment(Box const& b, segment_type& s, bool& sp1_clipped, bool& sp2_clipped) const
- {
- typedef typename select_coordinate_type<Box, Point>::type coordinate_type;
-
- coordinate_type t1 = 0;
- coordinate_type t2 = 1;
-
- coordinate_type const dx = get<1, 0>(s) - get<0, 0>(s);
- coordinate_type const dy = get<1, 1>(s) - get<0, 1>(s);
-
- coordinate_type const p1 = -dx;
- coordinate_type const p2 = dx;
- coordinate_type const p3 = -dy;
- coordinate_type const p4 = dy;
-
- coordinate_type const q1 = get<0, 0>(s) - get<min_corner, 0>(b);
- coordinate_type const q2 = get<max_corner, 0>(b) - get<0, 0>(s);
- coordinate_type const q3 = get<0, 1>(s) - get<min_corner, 1>(b);
- coordinate_type const q4 = get<max_corner, 1>(b) - get<0, 1>(s);
-
- if (check_edge(p1, q1, t1, t2) // left
- && check_edge(p2, q2, t1, t2) // right
- && check_edge(p3, q3, t1, t2) // bottom
- && check_edge(p4, q4, t1, t2)) // top
- {
- sp1_clipped = t1 > 0;
- sp2_clipped = t2 < 1;
-
- if (sp2_clipped)
- {
- set<1, 0>(s, get<0, 0>(s) + t2 * dx);
- set<1, 1>(s, get<0, 1>(s) + t2 * dy);
- }
-
- if(sp1_clipped)
- {
- set<0, 0>(s, get<0, 0>(s) + t1 * dx);
- set<0, 1>(s, get<0, 1>(s) + t1 * dy);
- }
-
- return true;
- }
-
- return false;
- }
-
- template<typename Linestring, typename OutputIterator>
- inline void apply(Linestring& line_out, OutputIterator out) const
- {
- if (!boost::empty(line_out))
- {
- *out = line_out;
- ++out;
- geometry::clear(line_out);
- }
- }
-};
-
-
-}} // namespace strategy::intersection
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace intersection
-{
-
-/*!
- \brief Clips a linestring with a box
- \details A linestring is intersected (clipped) by the specified box
- and the resulting linestring, or pieces of linestrings, are sent to the specified output operator.
- \tparam OutputLinestring type of the output linestrings
- \tparam OutputIterator an output iterator which outputs linestrings
- \tparam Linestring linestring-type, for example a vector of points, matching the output-iterator type,
- the points should also match the input-iterator type
- \tparam Box box type
- \tparam Strategy strategy, a clipping strategy which should implement the methods "clip_segment" and "apply"
-*/
-template
-<
- typename OutputLinestring,
- typename OutputIterator,
- typename Linestring,
- typename Box,
- typename Strategy
->
-OutputIterator clip_linestring_with_box(Box const& b, Linestring const& linestring,
- OutputIterator out, Strategy const& strategy)
-{
- if (boost::begin(linestring) == boost::end(linestring))
- {
- return out;
- }
-
- typedef typename point_type<OutputLinestring>::type point_type;
-
- OutputLinestring line_out;
-
- typedef typename boost::range_iterator<Linestring const>::type iterator_type;
- iterator_type vertex = boost::begin(linestring);
- for(iterator_type previous = vertex++;
- vertex != boost::end(linestring);
- previous = vertex++)
- {
- point_type p1, p2;
- copy_coordinates(*previous, p1);
- copy_coordinates(*vertex, p2);
-
- // Clip the segment. Five situations:
- // 1. Segment is invisible, finish line if any (shouldn't occur)
- // 2. Segment is completely visible. Add (p1)-p2 to line
- // 3. Point 1 is invisible (clipped), point 2 is visible. Start new line from p1-p2...
- // 4. Point 1 is visible, point 2 is invisible (clipped). End the line with ...p2
- // 5. Point 1 and point 2 are both invisible (clipped). Start/finish an independant line p1-p2
- //
- // This results in:
- // a. if p1 is clipped, start new line
- // b. if segment is partly or completely visible, add the segment
- // c. if p2 is clipped, end the line
-
- bool c1 = false;
- bool c2 = false;
- segment<point_type> s(p1, p2);
-
- if (!strategy.clip_segment(b, s, c1, c2))
- {
- strategy.apply(line_out, out);
- }
- else
- {
- // a. If necessary, finish the line and add a start a new one
- if (c1)
- {
- strategy.apply(line_out, out);
- }
-
- // b. Add p1 only if it is the first point, then add p2
- if (boost::empty(line_out))
- {
- geometry::append(line_out, p1);
- }
- geometry::append(line_out, p2);
-
- // c. If c2 is clipped, finish the line
- if (c2)
- {
- strategy.apply(line_out, out);
- }
- }
-
- }
-
- // Add last part
- strategy.apply(line_out, out);
- return out;
-}
-
-}} // namespace detail::intersection
-#endif // DOXYGEN_NO_DETAIL
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_CLIP_LINESTRING_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/copy_segment_point.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,275 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
-
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/core/ring_type.hpp>
-#include <boost/geometry/core/exterior_ring.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-
-#include <boost/geometry/geometries/concepts/check.hpp>
-
-#include <boost/geometry/iterators/ever_circling_iterator.hpp>
-
-#include <boost/geometry/iterators/range_type.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace copy_segments
-{
-
-
-template <typename Range, typename SegmentIdentifier, typename PointOut>
-struct copy_segment_point_range
-{
- static inline bool apply(Range const& range,
- SegmentIdentifier const& seg_id, bool second,
- PointOut& point)
- {
- int index = seg_id.segment_index;
- if (second)
- {
- index++;
- if (index >= boost::size(range))
- {
- index = 0;
- }
- }
-
- // Exception?
- if (index >= boost::size(range))
- {
- return false;
- }
-
- geometry::copy_coordinates(range[index], point);
- return true;
- }
-};
-
-
-template <typename Polygon, typename SegmentIdentifier, typename PointOut>
-struct copy_segment_point_polygon
-{
- static inline bool apply(Polygon const& polygon,
- SegmentIdentifier const& seg_id, bool second,
- PointOut& point)
- {
- // Call ring-version with the right ring
- return copy_segment_point_range
- <
- typename geometry::ring_type<Polygon>::type,
- SegmentIdentifier,
- PointOut
- >::apply
- (
- seg_id.ring_index < 0
- ? geometry::exterior_ring(polygon)
- : geometry::interior_rings(polygon)[seg_id.ring_index],
- seg_id, second,
- point
- );
- }
-};
-
-
-template <typename Box, typename SegmentIdentifier, typename PointOut>
-struct copy_segment_point_box
-{
- static inline bool apply(Box const& box,
- SegmentIdentifier const& seg_id, bool second,
- PointOut& point)
- {
- int index = seg_id.segment_index;
- if (second)
- {
- index++;
- }
-
- PointOut ll, lr, ul, ur;
- assign_box_corners(box, ll, lr, ul, ur);
- switch(index)
- {
- case 1 : point = ul; break;
- case 2 : point = ur; break;
- case 3 : point = lr; break;
- default : // 0,4 or 'overflow'
- point = ll; break;
- }
- return true;
- }
-};
-
-
-
-
-}} // namespace detail::copy_segments
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename Tag,
- typename GeometryIn,
- typename SegmentIdentifier,
- typename PointOut
->
-struct copy_segment_point
-{};
-
-
-template <typename LineString, typename SegmentIdentifier, typename PointOut>
-struct copy_segment_point<linestring_tag, LineString, SegmentIdentifier, PointOut>
- : detail::copy_segments::copy_segment_point_range
- <
- LineString, SegmentIdentifier, PointOut
- >
-{};
-
-
-template <typename Ring, typename SegmentIdentifier, typename PointOut>
-struct copy_segment_point<ring_tag, Ring, SegmentIdentifier, PointOut>
- : detail::copy_segments::copy_segment_point_range
- <
- Ring, SegmentIdentifier, PointOut
- >
-{};
-
-template <typename Polygon, typename SegmentIdentifier, typename PointOut>
-struct copy_segment_point<polygon_tag, Polygon, SegmentIdentifier, PointOut>
- : detail::copy_segments::copy_segment_point_polygon
- <
- Polygon, SegmentIdentifier, PointOut
- >
-{};
-
-
-template <typename Box, typename SegmentIdentifier, typename PointOut>
-struct copy_segment_point<box_tag, Box, SegmentIdentifier, PointOut>
- : detail::copy_segments::copy_segment_point_box
- <
- Box, SegmentIdentifier, PointOut
- >
-{};
-
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-
-
-
-/*!
- \brief Helper function, copies a point from a segment
- \ingroup overlay
- */
-template<typename Geometry, typename SegmentIdentifier, typename PointOut>
-inline bool copy_segment_point(Geometry const& geometry,
- SegmentIdentifier const& seg_id, bool second,
- PointOut& point_out)
-{
- concept::check<Geometry const>();
-
- return dispatch::copy_segment_point
- <
- typename tag<Geometry>::type,
- Geometry,
- SegmentIdentifier,
- PointOut
- >::apply(geometry, seg_id, second, point_out);
-}
-
-
-/*!
- \brief Helper function, to avoid the same construct several times,
- copies a point, based on a source-index and two geometries
- \ingroup overlay
- */
-template
-<
- typename Geometry1,
- typename Geometry2,
- typename SegmentIdentifier,
- typename PointOut
->
-inline bool copy_segment_point(Geometry1 const& geometry1, Geometry2 const& geometry2,
- SegmentIdentifier const& seg_id, bool second,
- PointOut& point_out)
-{
- concept::check<Geometry1 const>();
- concept::check<Geometry2 const>();
-
- if (seg_id.source_index == 0)
- {
- return dispatch::copy_segment_point
- <
- typename tag<Geometry1>::type,
- Geometry1,
- SegmentIdentifier,
- PointOut
- >::apply(geometry1, seg_id, second, point_out);
- }
- else if (seg_id.source_index == 1)
- {
- return dispatch::copy_segment_point
- <
- typename tag<Geometry2>::type,
- Geometry2,
- SegmentIdentifier,
- PointOut
- >::apply(geometry2, seg_id, second, point_out);
- }
- // Exception?
- return false;
-}
-
-
-/*!
- \brief Helper function, to avoid the same construct several times,
- copies a point, based on a source-index and two geometries
- \ingroup overlay
- */
-template
-<
- typename Geometry1,
- typename Geometry2,
- typename SegmentIdentifier,
- typename PointOut
->
-inline bool copy_segment_points(Geometry1 const& geometry1, Geometry2 const& geometry2,
- SegmentIdentifier const& seg_id,
- PointOut& point1, PointOut& point2)
-{
- concept::check<Geometry1 const>();
- concept::check<Geometry2 const>();
-
- return copy_segment_point(geometry1, geometry2, seg_id, false, point1)
- && copy_segment_point(geometry1, geometry2, seg_id, true, point2);
-}
-
-
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/copy_segments.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,226 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
-
-
-#include <vector>
-
-#include <boost/assert.hpp>
-#include <boost/range.hpp>
-
-#include <boost/geometry/core/tags.hpp>
-
-#include <boost/geometry/core/ring_type.hpp>
-#include <boost/geometry/core/exterior_ring.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-
-#include <boost/geometry/geometries/concepts/check.hpp>
-
-#include <boost/geometry/iterators/ever_circling_iterator.hpp>
-
-#include <boost/geometry/iterators/range_type.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace copy_segments
-{
-
-
-template <typename Ring, typename SegmentIdentifier, typename RangeOut>
-struct copy_segments_ring
-{
- static inline void apply(Ring const& ring,
- SegmentIdentifier const& seg_id, int to_index,
- RangeOut& current_output)
- {
- typedef typename boost::range_iterator<Ring const>::type iterator;
-
- typedef geometry::ever_circling_iterator<iterator> ec_iterator;
-
- // The problem: sometimes we want to from "3" to "2" -> end = "3" -> end == begin
- // This is not convenient with iterators.
-
- // So we use the ever-circling iterator and determine when to step out
-
- int from_index = seg_id.segment_index + 1;
-
- // Sanity check
- BOOST_ASSERT(from_index < boost::size(ring));
-
- ec_iterator it(boost::begin(ring), boost::end(ring),
- boost::begin(ring) + from_index);
-
- // [2..4] -> 4 - 2 + 1 = 3 -> {2,3,4} -> OK
- // [4..2],size=6 -> 6 - 4 + 2 + 1 = 5 -> {4,5,0,1,2} -> OK
- // [1..1], travel the whole ring round
- typedef typename boost::range_difference<Ring>::type size_type;
- size_type count = from_index <= to_index
- ? to_index - from_index + 1
- : boost::size(ring) - from_index + to_index + 1;
-
- for (size_type i = 0; i < count; ++i, ++it)
- {
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
- std::cout << " add: ("
- << geometry::get<0>(*it) << ", " << geometry::get<1>(*it) << ")"
- << std::endl;
-#endif
- typename geometry::point_type<RangeOut>::type p;
- geometry::copy_coordinates(*it, p);
- //current_output.push_back(p);
- *(std::back_inserter(current_output)++) = p;
- }
- }
-};
-
-
-template <typename Polygon, typename SegmentIdentifier, typename RangeOut>
-struct copy_segments_polygon
-{
- static inline void apply(Polygon const& polygon,
- SegmentIdentifier const& seg_id, int to_index,
- RangeOut& current_output)
- {
- // Call ring-version with the right ring
- copy_segments_ring
- <
- typename geometry::ring_type<Polygon>::type,
- SegmentIdentifier,
- RangeOut
- >::apply
- (
- seg_id.ring_index < 0
- ? geometry::exterior_ring(polygon)
- : geometry::interior_rings(polygon)[seg_id.ring_index],
- seg_id, to_index,
- current_output
- );
- }
-};
-
-
-template <typename Box, typename SegmentIdentifier, typename RangeOut>
-struct copy_segments_box
-{
- static inline void apply(Box const& box,
- SegmentIdentifier const& seg_id, int to_index,
- RangeOut& current_output)
- {
- // Convert again...
- // TODO: avoid that...
-
- typedef typename point_type<Box>::type point_type;
-
- point_type ll, lr, ul, ur;
- assign_box_corners(box, ll, lr, ul, ur);
-
- std::vector<point_type> points;
- points.push_back(ll);
- points.push_back(ul);
- points.push_back(ur);
- points.push_back(lr);
- points.push_back(ll);
-
- copy_segments_ring
- <
- std::vector<point_type>,
- SegmentIdentifier,
- RangeOut
- >
- ::apply(points, seg_id, to_index, current_output);
- }
-};
-
-
-
-
-}} // namespace detail::copy_segments
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename Tag,
- typename GeometryIn,
- typename SegmentIdentifier,
- typename RangeOut
->
-struct copy_segments
-{
-};
-
-
-template <typename Ring, typename SegmentIdentifier, typename RangeOut>
-struct copy_segments<ring_tag, Ring, SegmentIdentifier, RangeOut>
- : detail::copy_segments::copy_segments_ring
- <
- Ring, SegmentIdentifier, RangeOut
- >
-{};
-
-template <typename Polygon, typename SegmentIdentifier, typename RangeOut>
-struct copy_segments<polygon_tag, Polygon, SegmentIdentifier, RangeOut>
- : detail::copy_segments::copy_segments_polygon
- <
- Polygon, SegmentIdentifier, RangeOut
- >
-{};
-
-
-template <typename Box, typename SegmentIdentifier, typename RangeOut>
-struct copy_segments<box_tag, Box, SegmentIdentifier, RangeOut>
- : detail::copy_segments::copy_segments_box
- <
- Box, SegmentIdentifier, RangeOut
- >
-{};
-
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-
-
-
-/*!
- \brief Traverses through intersection points / geometries
- \ingroup overlay
- */
-template<typename Geometry, typename SegmentIdentifier, typename RangeOut>
-inline void copy_segments(Geometry const& geometry,
- SegmentIdentifier const& seg_id, int to_index,
- RangeOut& range_out)
-{
- concept::check<Geometry const>();
-
- dispatch::copy_segments
- <
- typename tag<Geometry>::type,
- Geometry,
- SegmentIdentifier,
- RangeOut
- >::apply(geometry, seg_id, to_index, range_out);
-}
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/enrich_intersection_points.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,433 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
-
-
-#include <cstddef>
-#include <algorithm>
-#include <map>
-#include <vector>
-
-//#ifdef BOOST_GEOMETRY_DEBUG_OVERLAY
-#include <iostream>
-#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
-//#endif
-
-#include <boost/assert.hpp>
-#include <boost/range.hpp>
-
-
-
-#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
-#include <boost/geometry/algorithms/overlay/copy_segment_point.hpp>
-#include <boost/geometry/algorithms/detail/overlay/get_relative_order.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template <typename Operation>
-struct indexed_operation
-{
- typedef Operation type;
-
- int index;
- int operation_index;
- Operation subject;
-
- inline indexed_operation(int i, int oi, Operation const& s)
- : index(i)
- , operation_index(oi)
- , subject(s)
- {}
-};
-
-
-template
-<
- typename Indexed,
- typename Geometry1,
- typename Geometry2,
- typename Strategy
->
-struct sort_on_distance
-{
-private :
- Geometry1 const& m_geometry1;
- Geometry2 const& m_geometry2;
- Strategy const& m_strategy;
-
- typedef typename Indexed::type operation_type;
- typedef typename point_type<Geometry1>::type point_type;
-
-
- inline bool normal_compare_distances(operation_type const& left,
- operation_type const& right) const
- {
- return left.enriched.distance < right.enriched.distance;
- }
-
-protected :
-
-
- // Note that left/right do NOT correspond to m_geometry1/m_geometry2
- inline bool compare_distances(operation_type const& left,
- operation_type const& right) const
- {
- // TODO: change this, it gives non-consequent behaviour resulting in
- // an assertion within sort.
- // SOLUTION: first sort on distance, then check if the sorted vector
- // has distances close to zero, swap them mutually if there is a reason
- // (reason by sides)
- //if (fuzzy_equals(left.enriched.distance, right.enriched.distance))
- if (false)
- {
-
- // Distances are the same, or quite close.
- // We sort now using sides instead of using distance
- // In most cases, this is possible. Else we fallback to distance
- // (--> very rare cases, when both methods fail)
-
-#ifdef BOOST_GEOMETRY_DEBUG_OVERLAY
- std::cout << "Equal Distance"
- << " : " << left.seg_id << " / " << left.other_id
- << " and " << right.seg_id << " / " << right.other_id
- << std::endl;
-#endif
-
- point_type pi, pj, ri, rj, si, sj;
- if (left.seg_id == right.seg_id)
- {
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.seg_id,
- pi, pj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.other_id,
- ri, rj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- right.other_id,
- si, sj);
- }
- else if (left.other_id == right.other_id)
- {
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.other_id,
- pi, pj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- left.seg_id,
- ri, rj);
- geometry::copy_segment_points(m_geometry1, m_geometry2,
- right.seg_id,
- si, sj);
- }
- else
- {
- return normal_compare_distances(left, right);
- }
-
- int const order = get_relative_order<point_type>::apply(pi, pj,
- ri, rj, si, sj);
- if (order != 0)
- {
- // If order == -1, r is the first segment along p
- // So then return true;
- return order == -1;
- }
- }
-
- return normal_compare_distances(left, right);
- }
-
-public :
- sort_on_distance(Geometry1 const& geometry1, Geometry2 const& geometry2,
- Strategy const& strategy)
- : m_geometry1(geometry1)
- , m_geometry2(geometry2)
- , m_strategy(strategy)
- {}
-
- inline bool operator()(Indexed const& left, Indexed const& right) const
- {
- return compare_distances(left.subject, right.subject);
- }
-};
-
-
-template
-<
- typename Indexed,
- typename Geometry1,
- typename Geometry2,
- typename Strategy
->
-struct sort_on_segment_and_distance
- : public sort_on_distance
- <
- Indexed,
- Geometry1, Geometry2, Strategy
- >
-{
- sort_on_segment_and_distance(Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- Strategy const& strategy)
- : sort_on_distance
- <
- Indexed,
- Geometry1, Geometry2, Strategy
- >(geometry1, geometry2, strategy)
- {}
-
- inline bool operator()(Indexed const& left, Indexed const& right) const
- {
- segment_identifier const& sl = left.subject.seg_id;
- segment_identifier const& sr = right.subject.seg_id;
-
- return sl == sr
- ? compare_distances(left.subject, right.subject)
- : sl < sr;
- }
-};
-
-
-template <typename Point, typename Operation, typename Geometry1, typename Geometry2>
-inline bool swap_operations(Operation const& left, Operation const& right,
- Geometry1 const& geometry1, Geometry2 const& geometry2)
-{
- Point pi, pj, ri, rj, si, sj;
- if (left.seg_id == right.seg_id)
- {
- geometry::copy_segment_points(geometry1, geometry2,
- left.seg_id,
- pi, pj);
- geometry::copy_segment_points(geometry1, geometry2,
- left.other_id,
- ri, rj);
- geometry::copy_segment_points(geometry1, geometry2,
- right.other_id,
- si, sj);
- std::cout << "Considering seg" << std::endl;
- }
- else if (left.other_id == right.other_id)
- {
- geometry::copy_segment_points(geometry1, geometry2,
- left.other_id,
- pi, pj);
- geometry::copy_segment_points(geometry1, geometry2,
- left.seg_id,
- ri, rj);
- geometry::copy_segment_points(geometry1, geometry2,
- right.seg_id,
- si, sj);
- std::cout << "Considering other" << std::endl;
- }
- else
- {
- return false;
- }
-
- int const order = get_relative_order<Point>::apply(pi, pj,
- ri, rj, si, sj);
- std::cout << "Order: " << order << std::endl;
- return order == 1;
-}
-
-
-// Sorts IP-s of this ring on segment-identifier, and if on same segment,
-// on distance.
-// Then assigns for each IP which is the next IP on this segment,
-// plus the vertex-index to travel to, plus the next IP
-// (might be on another segment)
-template
-<
- typename IndexType,
- typename Container,
- typename TurnPoints,
- typename Geometry1,
- typename Geometry2,
- typename Strategy
->
-static inline bool enrich(Container& operations,
- TurnPoints& turn_points,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- Strategy const& strategy)
-{
- std::sort(boost::begin(operations),
- boost::end(operations),
- sort_on_segment_and_distance
- <
- IndexType,
- Geometry1, Geometry2,
- Strategy
- >(geometry1, geometry2, strategy));
-
-
- typedef typename IndexType::type operation_type;
- typedef typename boost::range_iterator<Container const>::type iterator_type;
-
-//#ifdef BOOST_GEOMETRY_DEBUG_OVERLAY
- /***
- // Check if it is really sorted.
- if (operations.size() > 1)
- {
- typedef typename boost::range_iterator<Container>::type nc_iterator;
- nc_iterator it = boost::begin(operations);
- for (nc_iterator prev = it++;
- it != boost::end(operations);
- prev = it++)
- {
- operation_type& prev_op = turn_points[prev->index]
- .operations[prev->operation_index];
- operation_type& op = turn_points[it->index]
- .operations[it->operation_index];
- if ((prev_op.seg_id == op.seg_id || prev_op.other_id == op.other_id)
- && geometry::math::equals(prev_op.enriched.distance,
- op.enriched.distance))
- {
- std::cout << "Equal Distance on "
- << " : " << prev_op.seg_id << " / " << prev_op.other_id
- << " and " << op.seg_id << " / " << op.other_id
- << std::endl;
- std::cout << "\tType of intersections: "
- << operation_char(prev_op.operation)
- << " , " << operation_char(op.operation)
- << std::endl;
-
- if (swap_operations
- <
- typename point_type<Geometry1>::type
- >(prev_op, op, geometry1, geometry2))
- {
- std::cout << "Should be swapped" << std::endl;
-
- std::swap(*prev, *it);
- }
- }
- }
- }
- ***/
-//#endif
-
-
- // Assign travel-to-vertex/ip index for each turning point.
- // Because IP's are circular, PREV starts at the very last one,
- // being assigned from the first one.
- // For "next ip on same segment" it should not be considered circular.
- bool first = true;
- iterator_type it = boost::begin(operations);
- for (iterator_type prev = it + (boost::size(operations) - 1);
- it != boost::end(operations);
- prev = it++)
- {
- operation_type& prev_op = turn_points[prev->index]
- .operations[prev->operation_index];
-
- prev_op.enriched.travels_to_ip_index = it->index;
- prev_op.enriched.travels_to_vertex_index
- = it->subject.seg_id.segment_index;
-
- operation_type& op = turn_points[it->index]
- .operations[it->operation_index];
-
- if (! first && prev_op.seg_id.segment_index == op.seg_id.segment_index)
- {
- prev_op.enriched.next_ip_index = it->index;
- }
- first = false;
- }
-
- return true;
-}
-
-
-}} // namespace detail::overlay
-#endif //DOXYGEN_NO_DETAIL
-
-
-/*!
- \brief All intersection points are enriched with successor information
- \ingroup overlay
- \tparam TurnPoints type of intersection container
- (e.g. vector of "intersection/turn point"'s)
- \param turn_points container containing intersectionpoints
- */
-template
-<
- typename TurnPoints,
- typename Geometry1,
- typename Geometry2,
- typename Strategy
->
-inline void enrich_intersection_points(TurnPoints& turn_points,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- Strategy const& strategy)
-{
- typedef typename boost::range_value<TurnPoints>::type turn_point_type;
- typedef typename turn_point_type::container_type container_type;
- typedef typename boost::range_value<container_type>::type operation_type;
- typedef detail::overlay::indexed_operation<operation_type> indexed_type;
- typedef std::map
- <
- ring_identifier,
- std::vector<indexed_type>
- > mapped_vector_type;
-
- // Create a map of vectors of indexed operation-types to be able
- // to sort per ring, later on.
- mapped_vector_type mapped_vector;
-
- int index = 0;
- for (typename boost::range_iterator<TurnPoints const>::type
- it = boost::begin(turn_points);
- it != boost::end(turn_points);
- ++it, ++index)
- {
- if (! it->ignore)
- {
- int op_index = 0;
- for (typename boost::range_iterator<container_type const>::type
- op_it = boost::begin(it->operations);
- op_it != boost::end(it->operations);
- ++op_it, ++op_index)
- {
- ring_identifier ring_id
- (
- op_it->seg_id.source_index,
- op_it->seg_id.multi_index,
- op_it->seg_id.ring_index
- );
- mapped_vector[ring_id].push_back
- (
- indexed_type(index, op_index, *op_it)
- );
- }
- }
- }
-
- // Note: no const-operator because contents of mapped copy is temporary,
- // and changed by enrich)
- for (typename mapped_vector_type::iterator mit
- = mapped_vector.begin();
- mit != mapped_vector.end();
- ++mit)
- {
- detail::overlay::enrich<indexed_type>(mit->second, turn_points,
- geometry1, geometry2, strategy);
- }
-}
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,887 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_TURNS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_TURNS_HPP
-
-
-#include <cstddef>
-#include <map>
-
-#include <boost/mpl/if.hpp>
-#include <boost/range.hpp>
-
-#include <boost/tuple/tuple.hpp>
-
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/coordinate_dimension.hpp>
-#include <boost/geometry/core/is_multi.hpp>
-#include <boost/geometry/core/reverse_dispatch.hpp>
-
-#include <boost/geometry/core/exterior_ring.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
-#include <boost/geometry/core/ring_type.hpp>
-
-#include <boost/geometry/geometries/concepts/check.hpp>
-
-#include <boost/geometry/util/math.hpp>
-
-#include <boost/geometry/geometries/box.hpp>
-
-#include <boost/geometry/iterators/range_type.hpp>
-#include <boost/geometry/iterators/ever_circling_iterator.hpp>
-
-#include <boost/geometry/strategies/cartesian/cart_intersect.hpp>
-#include <boost/geometry/strategies/intersection.hpp>
-#include <boost/geometry/strategies/intersection_result.hpp>
-
-#include <boost/geometry/algorithms/detail/disjoint.hpp>
-#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
-
-#include <boost/geometry/algorithms/overlay/segment_identifier.hpp>
-
-
-#include <boost/geometry/algorithms/detail/sections/get_full_section.hpp>
-
-#include <boost/geometry/algorithms/combine.hpp>
-#include <boost/geometry/algorithms/distance.hpp>
-#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
-#include <boost/geometry/algorithms/detail/sections/get_section.hpp>
-#include <boost/geometry/algorithms/within.hpp>
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
-# include <sstream>
-# include <boost/geometry/util/write_dsv.hpp>
-#endif
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace get_turns
-{
-
-
-struct no_interrupt_policy
-{
- static bool const enabled = false;
-
- template <typename Range>
- static inline bool apply(Range const&)
- {
- return false;
- }
-};
-
-
-template
-<
- typename Geometry1, typename Geometry2,
- typename Section1, typename Section2,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-class get_turns_in_sections
-{
-
-public :
- // Returns true if terminated, false if interrupted
- static inline bool apply(
- int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
- int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
-
- typedef typename boost::range_iterator
- <
- typename geometry::range_type<Geometry1>::type const
- >::type range1_iterator;
-
- typedef typename boost::range_iterator
- <
- typename geometry::range_type<Geometry2>::type const
- >::type range2_iterator;
-
- int const dir1 = sec1.directions[0];
- int const dir2 = sec2.directions[0];
- int index1 = sec1.begin_index;
- int ndi1 = sec1.non_duplicate_index;
-
- bool const same_source =
- source_id1 == source_id2
- && sec1.multi_index == sec2.multi_index
- && sec1.ring_index == sec2.ring_index;
-
- range1_iterator prev1, it1, end1;
- range1_iterator begin_range_1, end_range_1;
-
- ever_circling_iterator<range1_iterator> next1
- = start_at_section(sec1, prev1, it1, end1, begin_range_1, end_range_1,
- index1, ndi1, geometry1, dir1, sec2.bounding_box);
-
- // Walk through section and stop if we exceed the other box
- for (prev1 = it1++, next1++;
- it1 != end1 && ! exceeding<0>(dir1, *prev1, sec2.bounding_box);
- prev1 = it1++, index1++, next1++, ndi1++)
- {
- ever_circling_iterator<range1_iterator> nd_next1(
- begin_range_1, end_range_1, next1, true);
- advance_to_non_duplicate_next(nd_next1, it1, sec1);
-
- int index2 = sec2.begin_index;
- int ndi2 = sec2.non_duplicate_index;
-
- range2_iterator prev2, it2, end2;
- range2_iterator begin_range_2, end_range_2;
-
- ever_circling_iterator<range2_iterator> next2 =
- start_at_section(sec2, prev2, it2, end2, begin_range_2, end_range_2,
- index2, ndi2, geometry2, dir2, sec1.bounding_box);
-
- for (prev2 = it2++, next2++;
- it2 != end2 && ! exceeding<0>(dir2, *prev2, sec1.bounding_box);
- prev2 = it2++, index2++, next2++, ndi2++)
- {
- bool skip = same_source;
- if (skip)
- {
- // If sources are the same (possibly self-intersecting):
- // skip if it is a neighbouring sement.
- // (including first-last segment
- // and two segments with one or more degenerate/duplicate
- // (zero-length) segments in between)
-
- // Also skip if index1 < index2 to avoid getting all
- // intersections twice (only do this on same source!)
-
- // About n-2:
- // (square: range_count=5, indices 0,1,2,3
- // -> 0-3 are adjacent)
- skip = index2 >= index1
- || ndi1 == ndi2 + 1
- || (index2 == 0 && index1 >= int(sec1.range_count) - 2)
- ;
- }
-
- if (! skip)
- {
- // Move to the "non duplicate next"
- ever_circling_iterator<range2_iterator> nd_next2(
- begin_range_2, end_range_2, next2, true);
- advance_to_non_duplicate_next(nd_next2, it2, sec2);
-
- typedef typename boost::range_value<Turns>::type turn_info;
- typedef typename turn_info::point_type ip;
-
- turn_info ti;
- ti.operations[0].seg_id = segment_identifier(source_id1,
- sec1.multi_index, sec1.ring_index, index1),
- ti.operations[1].seg_id = segment_identifier(source_id2,
- sec2.multi_index, sec2.ring_index, index2),
-
- ti.operations[0].other_id = ti.operations[1].seg_id;
- ti.operations[1].other_id = ti.operations[0].seg_id;
-
- std::size_t const size_before = boost::size(turns);
-
- detail::overlay::get_turn_info
- <
- point1_type, point2_type,
- turn_info,
- AssignPolicy
- >::apply(*prev1, *it1, *nd_next1, *prev2, *it2, *nd_next2,
- ti, std::back_inserter(turns));
-
- if (InterruptPolicy::enabled)
- {
- if (interrupt_policy.apply(
- std::make_pair(boost::begin(turns) + size_before,
- boost::end(turns))))
- {
- return false;
- }
- }
- }
- }
- }
- return true;
- }
-
-
-private :
- typedef typename geometry::point_type<Geometry1>::type point1_type;
- typedef typename geometry::point_type<Geometry2>::type point2_type;
- typedef typename geometry::segment<point1_type const> segment1_type;
- typedef typename geometry::segment<point2_type const> segment2_type;
-
-
- template <size_t Dim, typename Point, typename Box>
- static inline bool preceding(int dir, Point const& point, Box const& box)
- {
- return (dir == 1 && get<Dim>(point) < get<min_corner, Dim>(box))
- || (dir == -1 && get<Dim>(point) > get<max_corner, Dim>(box));
- }
-
- template <size_t Dim, typename Point, typename Box>
- static inline bool exceeding(int dir, Point const& point, Box const& box)
- {
- return (dir == 1 && get<Dim>(point) > get<max_corner, Dim>(box))
- || (dir == -1 && get<Dim>(point) < get<min_corner, Dim>(box));
- }
-
- template <typename Iterator, typename RangeIterator, typename Section>
- static inline void advance_to_non_duplicate_next(Iterator& next,
- RangeIterator const& it, Section const& section)
- {
- // To see where the next segments bend to, in case of touch/intersections
- // on end points, we need (in case of degenerate/duplicate points) an extra
- // iterator which moves to the REAL next point, so non duplicate.
- // This needs an extra comparison (disjoint).
- // (Note that within sections, non duplicate points are already asserted,
- // by the sectionalize process).
-
- // So advance to the "non duplicate next"
- // (the check is defensive, to avoid endless loops)
- std::size_t check = 0;
- while(! detail::disjoint::disjoint_point_point(*it, *next)
- && check++ < section.range_count)
- {
- next++;
- }
- }
-
- // It is NOT possible to have section-iterators here
- // because of the logistics of "index" (the section-iterator automatically
- // skips to the begin-point, we loose the index or have to recalculate it)
- // So we mimic it here
- template <typename RangeIterator, typename Section, typename Geometry, typename Box>
- static inline ever_circling_iterator<RangeIterator> start_at_section(Section & section,
- RangeIterator& it, RangeIterator& prev, RangeIterator& end,
- RangeIterator& begin_range_it, RangeIterator& end_range_it,
- int& index, int& ndi,
- Geometry const& geometry,
- int dir, Box const& other_bounding_box)
- {
- get_section(geometry, section, it, end);
-
- // Mimic section-iterator:
- // Skip to point such that section interects other box
- prev = it++;
- for(; it != end && preceding<0>(dir, *it, other_bounding_box);
- prev = it++, index++, ndi++)
- {}
- // Go back one step because we want to start completely preceding
- it = prev;
-
- get_full_section(geometry, section, begin_range_it, end_range_it);
-
- ever_circling_iterator<RangeIterator> next(begin_range_it, end_range_it, it, true);
- next++;
- return next;
- }
-};
-
-
-
-template
-<
- typename Geometry1,
- typename Geometry2,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-class get_turns_generic
-{
- template <typename Box, typename Sections>
- static inline void add_sections(Box& box, Sections const& sections)
- {
- for (typename boost::range_iterator<Sections const>::type
- it = sections.begin();
- it != sections.end();
- ++it)
- {
- geometry::combine(box, it->bounding_box);
- }
- }
-
- template <typename Sections, typename Box>
- static inline void get_sections(Sections const& sections,
- Box const& box, Sections& selection)
- {
- for (typename boost::range_iterator<Sections const>::type
- it = sections.begin();
- it != sections.end();
- ++it)
- {
- if (! geometry::detail::disjoint::disjoint_box_box(box, it->bounding_box))
- {
- selection.push_back(*it);
- }
- }
- }
-
- template <typename Sections1, typename Sections2, typename Map>
- static inline bool intersect(
- int source_id1, Geometry1 const& geometry1,
- int source_id2, Geometry2 const& geometry2,
- Turns& turns,
- InterruptPolicy& interrupt_policy,
- Sections1 const& sec1, Sections2 const& sec2,
- Map& map)
- {
- for (typename boost::range_iterator<Sections1 const>::type
- it1 = sec1.begin();
- it1 != sec1.end();
- ++it1)
- {
- for (typename boost::range_iterator<Sections2 const>::type
- it2 = sec2.begin();
- it2 != sec2.end();
- ++it2)
- {
- std::pair<int, int> p = std::make_pair(it1->id, it2->id);
- bool processed = map[p];
- if (! processed)
- {
- map[p] = true;
- if (! geometry::detail::disjoint::disjoint_box_box(
- it1->bounding_box, it2->bounding_box))
- {
- if (! get_turns_in_sections
- <
- Geometry1,
- Geometry2,
- typename boost::range_value<Sections1>::type,
- typename boost::range_value<Sections2>::type,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >::apply(
- source_id1, geometry1, *it1,
- source_id2, geometry2, *it2,
- turns, interrupt_policy)
- )
- {
- return false;
- }
- }
- }
- }
- }
- return true;
- }
-
-
- // Divide and conquer (suggested by Luke during GGL Formal Review)
- template
- <
- std::size_t Dimension,
- typename Box,
- typename Sections1, typename Sections2,
- typename Map
- >
- static inline bool divide_and_conquer(
- int source_id1, Geometry1 const& geometry1,
- int source_id2, Geometry2 const& geometry2,
- Turns& turns,
- InterruptPolicy& interrupt_policy,
-
- Box const& box,
- Sections1 const& sec1, Sections2 const& sec2,
- Map& map,
- std::size_t iteration = 0, std::size_t previous_count = 0)
- {
- // To stop the iteration, fallback to (quadratic) behaviour below certain limits,
- // or if dividing does not give any profit.
- std::size_t n = sec1.size() + sec2.size();
- if (sec1.size() < 5
- || sec2.size() < 5
- || n == previous_count
- || iteration > 100)
- {
- return intersect(source_id1, geometry1, source_id2, geometry2,
- turns, interrupt_policy, sec1, sec2, map);
- }
-
- // Divide the complete box in two (alternating) halves
- Box lower = box, upper = box;
- typename geometry::coordinate_type<Box>::type two = 2.0;
- typename geometry::coordinate_type<Box>::type mid
- = (geometry::get<min_corner, Dimension>(box)
- + geometry::get<max_corner, Dimension>(box)) / two;
-
- geometry::set<max_corner, Dimension>(lower, mid);
- geometry::set<min_corner, Dimension>(upper, mid);
-
- Sections1 lower1, upper1;
- Sections2 lower2, upper2;
- get_sections(sec1, lower, lower1);
- get_sections(sec2, lower, lower2);
- get_sections(sec1, upper, upper1);
- get_sections(sec2, upper, upper2);
-
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION_DIVIDE_AND_CONQUER
- std::cout
- << "Get IP's, iteration: " << iteration
- << " box: " << geometry::dsv(box)
- << " n: " << n
- << " lower: " << lower1.size() << " , " << lower2.size()
- << " upper: " << upper1.size() << " , " << upper2.size()
- << std::endl;
-#endif
-
- // Recursively handle lower and upper half, dividing in other dimension
- return divide_and_conquer<1 - Dimension>(source_id1, geometry1,
- source_id2, geometry2, turns, interrupt_policy,
- lower, lower1, lower2, map, iteration + 1, n)
- && divide_and_conquer<1 - Dimension>(source_id1, geometry1,
- source_id2, geometry2, turns, interrupt_policy,
- upper, upper1, upper2, map, iteration + 1, n);
- }
-
-public:
- static inline void apply(
- int source_id1, Geometry1 const& geometry1,
- int source_id2, Geometry2 const& geometry2,
- Turns& turns, InterruptPolicy& interrupt_policy)
- {
- // Create monotonic sections in ONE direction
- // - in most cases ONE direction is faster (e.g. ~1% faster for the NLP4 testset)
- // - the sections now have a limit (default 10) so will not be too large
-
- // Note that the sections contain boxes, are dynamic, and therefore
- // are specified using output/intersection-point-type
- // (to enable input-pointer-point-types)
- typedef typename boost::range_value<Turns>::type ip_type;
- typedef typename ip_type::point_type point_type;
- typedef typename geometry::sections<geometry::box<point_type>, 1> sections1_type;
- typedef typename geometry::sections<geometry::box<point_type>, 1> sections2_type;
-
- sections1_type sec1;
- sections2_type sec2;
-
- geometry::sectionalize(geometry1, sec1);
- geometry::sectionalize(geometry2, sec2);
-
- // Divide and conquer
- geometry::box<point_type> box;
- geometry::assign_inverse(box);
- add_sections(box, sec1);
- add_sections(box, sec2);
-
- // House-keeping map, to avoid section-pairs being compared twice
- std::map<std::pair<int, int>, bool> map;
-
- divide_and_conquer<1>(source_id1, geometry1, source_id2, geometry2,
- turns, interrupt_policy, box, sec1, sec2, map);
- }
-};
-
-
-// Get turns for something with a box, following Cohen-Sutherland (cs) approach
-template
-<
- typename Range,
- typename Box,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns_cs
-{
- static inline void apply(
- int source_id1, Range const& range,
- int multi_index, int ring_index,
- int source_id2, Box const& box,
- Turns& turns,
- InterruptPolicy& )
- {
- if (boost::size(range) <= 1)
- {
- return;
- }
-
-
- typedef typename geometry::point_type<Box>::type box_point_type;
- typedef typename geometry::point_type<Range>::type point_type;
-
- point_type lower_left, upper_left, lower_right, upper_right;
- assign_box_corners(box, lower_left, lower_right, upper_left, upper_right);
-
- /*
- box_segment_type left(lower_left, upper_left);
- box_segment_type top(upper_left, upper_right);
- box_segment_type right(upper_right, lower_right);
- box_segment_type bottom(lower_right, lower_left);
- */
-
- typedef typename boost::range_iterator
- <Range const>::type iterator_type;
- iterator_type it = boost::begin(range);
-
- ever_circling_iterator<iterator_type> next(boost::begin(range),
- boost::end(range), it, true);
- next++;
- next++;
-
- bool first = true;
-
- char previous_side[2] = {0, 0};
-
- int index = 0;
-
- for (iterator_type prev = it++;
- it != boost::end(range);
- prev = it++, next++, index++)
- {
- segment_identifier seg_id(source_id1,
- multi_index, ring_index, index);
-
- if (first)
- {
- previous_side[0] = get_side<0>(box, *prev);
- previous_side[1] = get_side<1>(box, *prev);
- }
-
- char current_side[2];
- current_side[0] = get_side<0>(box, *it);
- current_side[1] = get_side<1>(box, *it);
-
- // There can NOT be intersections if
- // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
- // 2) OR same in Y-direction
- // 3) OR all points are inside the box (0)
- /*if (! (
- (current_side[0] != 0 && current_side[0] == previous_side[0])
- || (current_side[1] != 0 && current_side[1] == previous_side[1])
- || (current_side[0] == 0
- && current_side[1] == 0
- && previous_side[0] == 0
- && previous_side[1] == 0)
- )
- )*/
- if (true)
- {
- typedef typename boost::range_value<Turns>::type turn_info;
- typedef detail::overlay::get_turn_info
- <
- box_point_type,
- point_type,
- turn_info,
- AssignPolicy
- > relater;
-
- // Depending on code some relations can be left out
- turn_info ti;
- ti.operations[0].seg_id = seg_id;
- ti.operations[1].other_id = ti.operations[0].seg_id;
-
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
- ti.operations[0].other_id = ti.operations[1].seg_id;
- relater::apply(*prev, *it, *next,
- lower_left, upper_left, upper_right,
- ti, std::back_inserter(turns));
-
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
- ti.operations[0].other_id = ti.operations[1].seg_id;
- relater::apply(*prev, *it, *next,
- upper_left, upper_right, lower_right,
- ti, std::back_inserter(turns));
-
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
- ti.operations[0].other_id = ti.operations[1].seg_id;
- relater::apply(*prev, *it, *next,
- upper_right, lower_right, lower_left,
- ti, std::back_inserter(turns));
-
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
- ti.operations[0].other_id = ti.operations[1].seg_id;
- relater::apply(*prev, *it, *next,
- lower_right, lower_left, upper_left,
- ti, std::back_inserter(turns));
-
- // TODO: call the break policy
-
- }
- }
- }
-
-private:
- template<std::size_t Index, typename Point>
- static inline int get_side(Box const& box, Point const& point)
- {
- // Inside -> 0
- // Outside -> -1 (left/below) or 1 (right/above)
- // On border -> -2 (left/lower) or 2 (right/upper)
- // The only purpose of the value is to not be the same,
- // and to denote if it is inside (0)
-
- typename coordinate_type<Point>::type const& c = get<Index>(point);
- typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
- typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
-
- if (geometry::math::equals(c, left)) return -2;
- else if (geometry::math::equals(c, right)) return 2;
- else if (c < left) return -1;
- else if (c > right) return 1;
- else return 0;
- }
-
-
-};
-
-
-}} // namespace detail::get_turns
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-// Because this is "detail" method, and most implementations will use "generic",
-// we take the freedom to derive it from "generic".
-template
-<
- typename GeometryTag1, typename GeometryTag2,
- bool IsMulti1, bool IsMulti2,
- typename Geometry1, typename Geometry2,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns
- : detail::get_turns::get_turns_generic
- <
- Geometry1,
- Geometry2,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >
-{};
-
-
-template
-<
- typename Polygon,
- typename Box,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns
- <
- polygon_tag, box_tag, false, false,
- Polygon, Box,
- Turns,
- IntersectionStrategy,
- AssignPolicy,
- InterruptPolicy
- >
-{
-
- static inline void apply(
- int source_id1, Polygon const& polygon,
- int source_id2, Box const& box,
- Turns& turns, InterruptPolicy& interrupt_policy)
- {
- typedef typename geometry::ring_type<Polygon>::type ring_type;
-
- typedef typename boost::range_iterator
- <
- typename interior_type<Polygon>::type const
- >::type iterator_type;
-
-
- typedef detail::get_turns::get_turns_cs
- <
- ring_type,
- Box,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- > intersector_type;
-
- intersector_type::apply(
- source_id1, geometry::exterior_ring(polygon), -1, -1,
- source_id2, box,
- turns, interrupt_policy);
-
- int i = 0;
- for (iterator_type it = boost::begin(interior_rings(polygon));
- it != boost::end(interior_rings(polygon));
- ++it, ++i)
- {
- intersector_type::apply(
- source_id1, *it, -1, i,
- source_id2, box, turns, interrupt_policy);
- }
-
- }
-};
-
-
-template
-<
- typename Ring,
- typename Box,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns
- <
- ring_tag, box_tag, false, false,
- Ring, Box,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >
-{
- static inline void apply(
- int source_id1, Ring const& ring,
- int source_id2, Box const& box,
- Turns& turns, InterruptPolicy& interrupt_policy)
- {
- typedef typename boost::range_iterator
- <
- Ring const
- >::type iterator_type;
-
- typedef detail::get_turns::get_turns_cs
- <
- Ring,
- Box,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- > intersector_type;
-
- intersector_type::apply(
- source_id1, ring, -1, -1,
- source_id2, box,
- turns, interrupt_policy);
-
- }
-};
-
-
-template
-<
- typename GeometryTag1, typename GeometryTag2,
- bool IsMulti1, bool IsMulti2,
- typename Geometry1, typename Geometry2,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy, typename InterruptPolicy
->
-struct get_turns_reversed
-{
- static inline void apply(
- int source_id1, Geometry1 const& g1,
- int source_id2, Geometry2 const& g2,
- Turns& turns, InterruptPolicy& interrupt_policy)
- {
- get_turns
- <
- GeometryTag2, GeometryTag1,
- IsMulti2, IsMulti1,
- Geometry2, Geometry1,
- Turns, IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >::apply(source_id2, g2, source_id1, g1, turns, interrupt_policy);
- }
-};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-
-/*!
- \brief Calculate intersection points of two geometries
- \ingroup overlay
- \tparam Geometry1 first geometry type
- \tparam Geometry2 second geometry type
- \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
- \param geometry1 first geometry
- \param geometry2 second geometry
- \param turns container which will contain intersection points
- */
-template
-<
- typename AssignPolicy,
- typename Geometry1,
- typename Geometry2,
- typename Turns,
- typename InterruptPolicy
->
-inline void get_turns(Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
-{
- concept::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
-
- typedef typename strategy_intersection
- <
- typename cs_tag<Geometry1>::type,
- Geometry1,
- Geometry2,
- typename boost::range_value<Turns>::type
- >::segment_intersection_strategy_type segment_intersection_strategy_type;
-
- boost::mpl::if_c
- <
- reverse_dispatch<Geometry1, Geometry2>::type::value,
- dispatch::get_turns_reversed
- <
- typename tag<Geometry1>::type,
- typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
- Geometry1,
- Geometry2,
- Turns,
- segment_intersection_strategy_type,
- AssignPolicy, InterruptPolicy
- >,
- dispatch::get_turns
- <
- typename tag<Geometry1>::type,
- typename tag<Geometry2>::type,
- is_multi<Geometry1>::type::value,
- is_multi<Geometry2>::type::value,
- Geometry1,
- Geometry2,
- Turns,
- segment_intersection_strategy_type,
- AssignPolicy, InterruptPolicy
- >
- >::type::apply(
- 0, geometry1,
- 1, geometry2,
- turns, interrupt_policy);
-}
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_GET_TURNS_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/msm_state.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/msm_state.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,186 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_MSM_STATE_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_MSM_STATE_HPP
-
-
-
-#ifdef USE_MSM_MINI
-
-# include <boost/msm/back/mini_state_machine.hpp>
-# include <boost/fusion/include/vector.hpp>
-
-#else
-
-# include <boost/msm/back/state_machine.hpp>
-# include <boost/msm/front/state_machine_def.hpp>
-
-#endif
-
-
-
-// Events
-struct starting {};
-struct visit {};
-struct finish {};
-
-
-// Flags
-struct is_init {};
-struct is_visited {};
-
-enum StatesEnum
-{
- STATE_NONE=0,
- STATE_IS_INIT=1,
- STATE_IS_VISITED=2
-};
-
-
-
-#ifndef USE_MSM_MINI
-
-// front-end: define the FSM structure
-struct traverse_state_ : public boost::msm::front::state_machine_def<traverse_state_>
-{
- traverse_state_():m_state(STATE_IS_INIT){}
- // The list of FSM states
- struct Init : public boost::msm::front::state<>
- {
- typedef boost::mpl::vector1<is_init> flag_list;
- //template <class Event,class FSM>
- //void on_entry(Event const&,FSM& fsm) {fsm.m_state=STATE_IS_INIT;}
- };
-
- struct Started : public boost::msm::front::state<>
- {
- //template <class Event,class FSM>
- //void on_entry(Event const&,FSM& fsm) {fsm.m_state=STATE_NONE;}
- };
-
- struct Visited : public boost::msm::front::state<>
- {
- typedef boost::mpl::vector1<is_visited> flag_list;
- //template <class Event,class FSM>
- //void on_entry(Event const&,FSM& fsm) {fsm.m_state=STATE_IS_VISITED;}
- };
-
- struct Finished : public boost::msm::front::state<>
- {
- typedef boost::mpl::vector1<is_visited> flag_list;
- //template <class Event,class FSM>
- //void on_entry(Event const&,FSM& fsm) {fsm.m_state=STATE_IS_VISITED;}
- };
-
-
- // the initial state of the player SM. Must be defined
- typedef Init initial_state;
-
- // transition actions
- void start_traverse(starting const&) {m_state=STATE_NONE;}
- void finish_after_visit(finish const&) {m_state=STATE_IS_VISITED;}
- void do_finish(finish const&) {m_state=STATE_IS_VISITED;}
- void do_visit(visit const&) {m_state=STATE_IS_VISITED;}
- void do_visit2(visit const&) {m_state=STATE_IS_VISITED;}
- void do_nothing(finish const&) {m_state=STATE_IS_VISITED;}
-
-
- typedef traverse_state_ p; // makes transition table cleaner
-
- // Transition table for player
- struct transition_table : mpl::vector
- <
- // Start Event Next Action Guard
- // +---------+-------------+---------+---------------------+----------------------+
- a_row < Init , starting , Started , &p::start_traverse >,
- a_row < Init , visit , Visited , &p::do_visit >,
- a_row < Init , finish , Finished , &p::do_nothing >,
- a_row < Started , finish , Finished , &p::do_finish >,
- a_row < Started , visit , Visited , &p::do_visit2 >,
- // +---------+-------------+---------+---------------------+----------------------+
- a_row < Visited , finish , Finished , &p::finish_after_visit >
- // +---------+-------------+---------+---------------------+----------------------+
- > {};
-
- // Replaces the default no-transition response.
- template <class Machine, class Event>
- void no_transition(Event const& e, Machine&, int state)
- {
- //std::cout << "no transition from state " << state << " on event " << typeid(e).name() << std::endl;
- }
-
- typedef int no_exception_thrown;
- typedef int no_message_queue;
- StatesEnum m_state;
-
-};
-
-
-typedef boost::msm::back::state_machine<traverse_state_> traverse_state;
-
-#else
-
-// mini-back-end
-
-
-struct traverse_state : public boost::msm::back::mini::state_machine<traverse_state>
-{
- traverse_state():m_state(STATE_IS_INIT){}
-
- // The list of FSM states
- enum states
- {
- Init, Started, Visited, Finished
- , initial_state = Init
- };
-
- friend class boost::msm::back::mini::state_machine<traverse_state>;
- typedef traverse_state p; // makes transition table cleaner
-
- // transition actions
- void start_traverse(starting const&) {m_state=STATE_NONE;}
- void finish_after_visit(finish const&) {m_state=STATE_IS_VISITED;}
- void do_finish(finish const&) {m_state=STATE_IS_VISITED;}
- void do_visit(visit const&) {m_state=STATE_IS_VISITED;}
- void do_visit2(visit const&) {m_state=STATE_IS_VISITED;}
- void do_nothing(finish const&) {m_state=STATE_IS_VISITED;}
-
- bool flag_none() const { return m_state == STATE_IS_INIT; }
- bool flag_visited() const { return m_state == STATE_IS_VISITED; }
-
-
- // Transition table
- struct transition_table : mpl::vector6<
- // Start Event Next Action
- // +---------+-------------+---------+---------------------+
- row < Init , starting , Started , &p::start_traverse >,
- row < Init , visit , Visited , &p::do_visit >,
- row < Init , finish , Finished, &p::do_nothing >,
- row < Started , finish , Finished, &p::do_finish >,
- row < Started , visit , Visited , &p::do_visit2 >,
- row < Visited , finish , Finished, &p::finish_after_visit>
- // +---------+-------------+---------+---------------------+
- > {};
-
- // Replaces the default no-transition response.
- template <class Event>
- int no_transition(int state, Event const& e)
- {
- std::cout << "no transition from state " << state
- << " on event " << typeid(e).name() << std::endl;
- return state;
- }
- StatesEnum m_state;
-
-};
-
-#endif
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_MSM_STATE_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/segment_identifier.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/segment_identifier.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,92 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SEGMENT_IDENTIFIER_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SEGMENT_IDENTIFIER_HPP
-
-
-#if defined(BOOST_GEOMETRY_DEBUG_OVERLAY)
-# define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
-#endif
-
-
-#include <vector>
-
-
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/coordinate_dimension.hpp>
-
-#include <boost/geometry/strategies/distance_result.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-// Internal struct to uniquely identify a segment
-// on a linestring,ring
-// or polygon (needs ring_index)
-// or multi-geometry (needs multi_index)
-struct segment_identifier
-{
- inline segment_identifier()
- : source_index(-1)
- , multi_index(-1)
- , ring_index(-1)
- , segment_index(-1)
- {}
-
- inline segment_identifier(int src, int mul, int rin, int seg)
- : source_index(src)
- , multi_index(mul)
- , ring_index(rin)
- , segment_index(seg)
- {}
-
- inline bool operator<(segment_identifier const& other) const
- {
- return source_index != other.source_index ? source_index < other.source_index
- : multi_index !=other.multi_index ? multi_index < other.multi_index
- : ring_index != other.ring_index ? ring_index < other.ring_index
- : segment_index < other.segment_index
- ;
- }
-
- inline bool operator==(segment_identifier const& other) const
- {
- return source_index == other.source_index
- && segment_index == other.segment_index
- && ring_index == other.ring_index
- && multi_index == other.multi_index
- ;
- }
-
-#if defined(BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER)
- friend std::ostream& operator<<(std::ostream &os, segment_identifier const& seg_id)
- {
- std::cout
- << "s:" << seg_id.source_index
- << ", v:" << seg_id.segment_index // ~vertex
- ;
- if (seg_id.ring_index >= 0) std::cout << ", r:" << seg_id.ring_index;
- if (seg_id.multi_index >= 0) std::cout << ", m:" << seg_id.multi_index;
- return os;
- }
-#endif
-
- int source_index;
- int multi_index;
- int ring_index;
- int segment_index;
-};
-
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SEGMENT_IDENTIFIER_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/self_turn_points.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,214 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
-
-#include <cstddef>
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/coordinate_dimension.hpp>
-#include <boost/geometry/core/is_multi.hpp>
-
-#include <boost/geometry/geometries/concepts/check.hpp>
-
-#include <boost/geometry/algorithms/detail/disjoint.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace self_get_turn_points
-{
-
-template
-<
- typename Geometry,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns
-{
- static inline bool apply(
- Geometry const& geometry,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
- typedef typename geometry::sections
- <
- geometry::box <typename geometry::point_type<Geometry>::type>,
- 1
- > sections_type;
-
- sections_type sec;
- geometry::sectionalize(geometry, sec);
-
- for (typename boost::range_iterator<sections_type const>::type
- it1 = sec.begin();
- it1 != sec.end();
- ++it1)
- {
- for (typename boost::range_iterator<sections_type const>::type
- it2 = sec.begin();
- it2 != sec.end();
- ++it2)
- {
- if (! geometry::detail::disjoint::disjoint_box_box(
- it1->bounding_box, it2->bounding_box)
- && ! it1->duplicate
- && ! it2->duplicate
- )
- {
- if (! geometry::detail::get_turns::get_turns_in_sections
- <
- Geometry, Geometry,
- typename boost::range_value<sections_type>::type,
- typename boost::range_value<sections_type>::type,
- Turns, IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >::apply(
- 0, geometry, *it1,
- 0, geometry, *it2,
- turns, interrupt_policy))
- {
- return false;
- }
- }
- }
- }
- return true;
- }
-};
-
-
-}} // namespace detail::self_get_turn_points
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-template
-<
- typename GeometryTag,
- bool IsMulti,
- typename Geometry,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct self_get_turn_points
-{
-};
-
-
-template
-<
- typename Ring,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct self_get_turn_points
- <
- ring_tag, false, Ring,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >
- : detail::self_get_turn_points::get_turns
- <
- Ring,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >
-{};
-
-
-template
-<
- typename Polygon,
- typename Turns,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct self_get_turn_points
- <
- polygon_tag, false, Polygon,
- Turns, IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >
- : detail::self_get_turn_points::get_turns
- <
- Polygon,
- Turns,
- IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >
-{};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-/*!
- \brief Calculate self intersections of a geometry
- \ingroup overlay
- \tparam Geometry geometry type
- \tparam Turns type of intersection container
- (e.g. vector of "intersection/turn point"'s)
- \param geometry geometry
- \param turns container which will contain intersection points
- */
-template
-<
- typename AssignPolicy,
- typename Geometry,
- typename Turns,
- typename InterruptPolicy
->
-inline void get_turns(Geometry const& geometry,
- Turns& turns, InterruptPolicy& interrupt_policy)
-{
- concept::check<Geometry const>();
-
- typedef typename strategy_intersection
- <
- typename cs_tag<Geometry>::type,
- Geometry,
- Geometry,
- typename boost::range_value<Turns>::type
- >::segment_intersection_strategy_type strategy_type;
-
-
- dispatch::self_get_turn_points
- <
- typename tag<Geometry>::type,
- is_multi<Geometry>::type::value,
- Geometry,
- Turns, strategy_type,
- AssignPolicy, InterruptPolicy
- >::apply(geometry, turns, interrupt_policy);
-}
-
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
Deleted: sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,411 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAY_TRAVERSE_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_OVERLAY_TRAVERSE_HPP
-
-
-#include <cstddef>
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-#include <boost/geometry/algorithms/overlay/copy_segments.hpp>
-#include <boost/geometry/core/access.hpp>
-#include <boost/geometry/core/coordinate_dimension.hpp>
-#include <boost/geometry/geometries/concepts/check.hpp>
-
-
-#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT)
-# include <string>
-# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
-# include <boost/geometry/extensions/gis/io/wkt/wkt.hpp>
-#endif
-
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template <typename Turns>
-inline void clear_visit_info(Turns& turns)
-{
- typedef typename boost::range_value<Turns>::type tp_type;
-
- for (typename boost::range_iterator<Turns>::type
- it = boost::begin(turns);
- it != boost::end(turns);
- ++it)
- {
- for (typename boost::range_iterator
- <
- typename tp_type::container_type
- >::type op_it = boost::begin(it->operations);
- op_it != boost::end(it->operations);
- ++op_it)
- {
- op_it->visited.clear();
- }
- }
-}
-
-
-template <typename Info, typename Turn>
-inline void set_visited_for_contine(Info& info, Turn const& turn)
-{
- // On "continue", set "visited" for ALL directions
- if (turn.operation == detail::overlay::operation_continue)
- {
- for (typename boost::range_iterator
- <
- typename Info::container_type
- >::type it = boost::begin(info.operations);
- it != boost::end(info.operations);
- ++it)
- {
- if (it->visited.none())
- {
- it->visited.set_visited();
- }
- }
- }
-}
-
-
-template
-<
- typename GeometryOut,
- typename G1,
- typename G2,
- typename Turns,
- typename IntersectionInfo
->
-inline void assign_next_ip(G1 const& g1, G2 const& g2,
- Turns& turns,
- typename boost::range_iterator<Turns>::type & ip,
- GeometryOut& current_output,
- IntersectionInfo & info,
- segment_identifier& seg_id)
-{
- info.visited.set_visited();
- set_visited_for_contine(*ip, info);
-
- // If there is no next IP on this segment
- if (info.enriched.next_ip_index < 0)
- {
- if (info.seg_id.source_index == 0)
- {
- geometry::copy_segments(g1, info.seg_id,
- info.enriched.travels_to_vertex_index,
- current_output);
- }
- else
- {
- geometry::copy_segments(g2, info.seg_id,
- info.enriched.travels_to_vertex_index,
- current_output);
- }
- ip = boost::begin(turns) + info.enriched.travels_to_ip_index;
- seg_id = info.seg_id;
- }
- else
- {
- ip = boost::begin(turns) + info.enriched.next_ip_index;
- seg_id = info.seg_id;
- }
- *(std::back_inserter(current_output)++) = ip->point;
-}
-
-
-inline bool select_source(operation_type operation, int source1, int source2)
-{
- return operation == operation_intersection && source1 != source2;
-}
-
-
-template
-<
- typename Turn,
- typename Iterator
->
-inline bool select_next_ip(operation_type operation,
- Turn& turn,
- segment_identifier const& seg_id,
- Iterator& selected)
-{
- bool has_tp = false;
- selected = boost::end(turn.operations);
- for (Iterator it = boost::begin(turn.operations);
- it != boost::end(turn.operations);
- ++it)
- {
- // In some cases there are two alternatives.
- // For "ii", take the other one (alternate)
- // For "uu", take the same one (see above);
- // For "cc", take either one, but if there is a starting one,
- // take that one.
- if ( (it->operation == operation_continue
- && (! has_tp
- || it->visited.started()
- )
- )
- || (it->operation == operation
- && (! has_tp
- || select_source(operation,
- it->seg_id.source_index, seg_id.source_index)
- )
- )
- )
- {
- selected = it;
- has_tp = true;
- }
-
- if (it->visited.started())
- {
- selected = it;
- return true;
- }
- }
-
- return has_tp;
-}
-
-
-
-template
-<
- typename Rings,
- typename Turns,
- typename Operation,
- typename Geometry1,
- typename Geometry2
->
-inline void backtrack(std::size_t size_at_start, bool& fail,
- Rings& rings, typename boost::range_value<Rings>::type& ring,
- Turns& turns, Operation& operation,
-
-#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
- std::string const& reason,
- Geometry1 const& geometry1,
- Geometry2 const& geometry2
-#else
- std::string const& reason,
- Geometry1 const& ,
- Geometry2 const&
-#endif
- )
-{
- fail = true;
-
- // Make bad output clean
- rings.resize(size_at_start);
- ring.clear();
-
- // Reject this as a starting point
- operation.visited.set_rejected();
-
- // And clear all visit info
- clear_visit_info(turns);
-
- /***
- int c = 0;
- for (int i = 0; i < turns.size(); i++)
- {
- for (int j = 0; j < 2; j++)
- {
- if (turns[i].operations[j].visited.rejected())
- {
- c++;
- }
- }
- }
- std::cout << "BACKTRACK (" << reason << " )"
- << " " << c << " of " << turns.size() << " rejected"
- << std::endl;
- ***/
-
-
-
-#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
- std::cout << " BT (" << reason << " )";
- std::cout
- << geometry::wkt(geometry1) << std::endl
- << geometry::wkt(geometry2) << std::endl;
-#endif
-
-}
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
-/*!
- \brief Traverses through intersection points / geometries
- \ingroup overlay
- */
-template
-<
- typename Geometry1,
- typename Geometry2,
- typename Turns,
- typename Rings
->
-inline void traverse(Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- detail::overlay::operation_type operation,
- Turns& turns, Rings& rings)
-{
- typedef typename boost::range_iterator<Turns>::type turn_iterator;
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename boost::range_iterator
- <
- typename turn_type::container_type
- >::type turn_operation_iterator_type;
-
- std::size_t size_at_start = boost::size(rings);
-
- bool fail = false;
- do
- {
- fail = false;
- // Iterate through all unvisited points
- for (turn_iterator it = boost::begin(turns);
- ! fail && it != boost::end(turns);
- ++it)
- {
- // Skip the ones marked ignore (these are: "uu", so self-tangent)
- if (! it->ignore)
- {
- for (turn_operation_iterator_type iit = boost::begin(it->operations);
- ! fail && iit != boost::end(it->operations);
- ++iit)
- {
- if (iit->visited.none()
- && ! iit->visited.rejected()
- && (iit->operation == operation
- || iit->operation == detail::overlay::operation_continue)
- )
- {
- set_visited_for_contine(*it, *iit);
-
- typename boost::range_value<Rings>::type current_output;
- *(std::back_inserter(current_output)++) = it->point;
-
- turn_iterator current = it;
- turn_operation_iterator_type current_iit = iit;
- segment_identifier current_seg_id;
-
- detail::overlay::assign_next_ip(geometry1, geometry2,
- turns,
- current, current_output,
- *iit, current_seg_id);
-
- if (! detail::overlay::select_next_ip(
- operation,
- *current,
- current_seg_id,
-
- current_iit))
- {
- detail::overlay::backtrack(
- size_at_start, fail,
- rings, current_output, turns, *iit,
- "Dead end at start",
- geometry1, geometry2);
- }
- else
- {
-
- iit->visited.set_started();
-
- unsigned int i = 0;
-
- while (current_iit != iit && ! fail)
- {
- if (current_iit->visited.visited())
- {
- // It visits a visited node again, without passing the start node.
- // This makes it suspicious for endless loops
- detail::overlay::backtrack(
- size_at_start, fail,
- rings, current_output, turns, *iit,
- "Visit again",
- geometry1, geometry2);
- }
- else
- {
-
-
- // We assume clockwise polygons only, non self-intersecting, closed.
- // However, the input might be different, and checking validity
- // is up to the library user.
-
- // Therefore we make here some sanity checks. If the input
- // violates the assumptions, the output polygon will not be correct
- // but the routine will stop and output the current polygon, and
- // will continue with the next one.
-
- // Below three reasons to stop.
- assign_next_ip(geometry1, geometry2,
- turns, current, current_output,
- *current_iit, current_seg_id);
-
- if (! detail::overlay::select_next_ip(
- operation,
- *current,
- current_seg_id,
-
- current_iit))
- {
- // Should not occur in valid (non-self-intersecting) polygons
- // Should not occur in self-intersecting polygons without spikes
- // Might occur in polygons with spikes
- detail::overlay::backtrack(
- size_at_start, fail,
- rings, current_output, turns, *iit,
- "Dead end",
- geometry1, geometry2);
- }
-
- if (i++ > turns.size())
- {
- // Sanity check: there may be never more loops
- // than intersection points.
- detail::overlay::backtrack(
- size_at_start, fail,
- rings, current_output, turns, *iit,
- "Endless loop",
- geometry1, geometry2);
- }
- }
- }
-
- if (! fail)
- {
- iit->visited.set_finished();
- rings.push_back(current_output);
- }
- }
- }
- }
- }
- }
- } while (fail);
-}
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAY_TRAVERSE_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/union.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/union.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/union.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -17,7 +17,7 @@
#include <boost/geometry/core/interior_rings.hpp>
#include <boost/geometry/core/reverse_dispatch.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/algorithms/overlay/assemble.hpp>
+#include <boost/geometry/algorithms/detail/overlay/assemble.hpp>
#include <boost/geometry/algorithms/within.hpp>
Copied: sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/assemble.hpp (from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/assemble.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,20 +5,20 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
+#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
+#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
#include <boost/assert.hpp>
#include <boost/range.hpp>
-#include <boost/geometry/algorithms/overlay/assemble.hpp>
+#include <boost/geometry/algorithms/detail/overlay/assemble.hpp>
#include <boost/geometry/multi/core/ring_type.hpp>
-#include <boost/geometry/multi/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/multi/algorithms/overlay/copy_segments.hpp>
-#include <boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp>
#include <boost/geometry/multi/algorithms/detail/point_on_border.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp>
@@ -90,4 +90,5 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
+
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_ASSEMBLE_HPP
Copied: sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp (from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,14 +5,14 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
+#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENT_POINT_HPP
+#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENT_POINT_HPP
#include <boost/range.hpp>
#include <boost/geometry/multi/core/tags.hpp>
-#include <boost/geometry/algorithms/overlay/copy_segment_point.hpp>
+#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
namespace boost { namespace geometry
@@ -94,4 +94,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENT_POINT_HPP
Copied: sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp (from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segments.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segments.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -6,14 +6,14 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
+#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
+#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
#include <boost/assert.hpp>
#include <boost/range.hpp>
-#include <boost/geometry/algorithms/overlay/copy_segments.hpp>
+#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
#include <boost/geometry/multi/core/ring_type.hpp>
#include <boost/geometry/multi/core/tags.hpp>
@@ -98,4 +98,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
Copied: sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp (from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,12 +5,12 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_TURNS_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_TURNS_HPP
+#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
+#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
#include <boost/geometry/multi/core/is_multi.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/multi/algorithms/distance.hpp>
#include <boost/geometry/multi/iterators/range_type.hpp>
@@ -19,7 +19,6 @@
#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
-
namespace boost { namespace geometry
{
@@ -130,4 +129,4 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_TURNS_HPP
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
Copied: sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/self_turn_points.hpp (from r61534, /sandbox/geometry/boost/geometry/multi/algorithms/overlay/self_turn_points.hpp)
==============================================================================
--- /sandbox/geometry/boost/geometry/multi/algorithms/overlay/self_turn_points.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/detail/overlay/self_turn_points.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -5,20 +5,18 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
+#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
+#define BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
#include <boost/geometry/multi/core/tags.hpp>
-#include <boost/geometry/algorithms/overlay/self_turn_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
namespace boost { namespace geometry
{
-
-
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
@@ -55,4 +53,5 @@
}} // namespace boost::geometry
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
+
+#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
Modified: sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/intersection.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -10,7 +10,7 @@
#include <boost/geometry/algorithms/intersection.hpp>
-#include <boost/geometry/multi/algorithms/overlay/assemble.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/assemble.hpp>
namespace boost { namespace geometry
Deleted: sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/assemble.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,93 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
-
-
-#include <boost/assert.hpp>
-#include <boost/range.hpp>
-
-#include <boost/geometry/algorithms/overlay/assemble.hpp>
-
-#include <boost/geometry/multi/core/ring_type.hpp>
-
-#include <boost/geometry/multi/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/multi/algorithms/overlay/copy_segments.hpp>
-#include <boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp>
-#include <boost/geometry/multi/algorithms/detail/point_on_border.hpp>
-#include <boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp>
-
-#include <boost/geometry/multi/algorithms/envelope.hpp>
-#include <boost/geometry/multi/algorithms/num_points.hpp>
-#include <boost/geometry/multi/algorithms/within.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template <typename MultiPolygon>
-struct add_to_containment<multi_polygon_tag, MultiPolygon>
-{
- template <typename ContainmentContainer, typename Map>
- static inline void apply(ContainmentContainer& container,
- ring_identifier const& id, MultiPolygon const& multi_polygon,
- Map const& map, bool dissolve)
- {
- ring_identifier copy = id;
- copy.multi_index = 0;
-
- // Add all rings with the updated index
- for (typename boost::range_iterator<MultiPolygon const>::type it
- = boost::begin(multi_polygon);
- it != boost::end(multi_polygon);
- ++it, ++copy.multi_index)
- {
- add_to_containment
- <
- polygon_tag,
- typename boost::range_value<MultiPolygon>::type
- >::apply(container, copy, *it, map, dissolve);
- }
- }
-};
-
-
-
-template<>
-struct get_ring<multi_polygon_tag>
-{
- template<typename MultiPolygon>
- static inline typename ring_type<MultiPolygon>::type const& apply(
- ring_identifier const& id,
- MultiPolygon const& multi_polygon)
- {
- BOOST_ASSERT
- (
- id.multi_index >= 0
- && id.multi_index < boost::size(multi_polygon)
- );
- return get_ring<polygon_tag>::apply(id,
- multi_polygon[id.multi_index]);
- }
-};
-
-
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_ASSEMBLE_HPP
Deleted: sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,97 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
-
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/multi/core/tags.hpp>
-#include <boost/geometry/algorithms/overlay/copy_segment_point.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace copy_segments
-{
-
-
-template
-<
- typename MultiGeometry,
- typename SegmentIdentifier,
- typename PointOut,
- typename Policy
->
-struct copy_segment_point_multi
-{
- static inline bool apply(MultiGeometry const& multi,
- SegmentIdentifier const& seg_id, bool second,
- PointOut& point)
- {
-
- BOOST_ASSERT
- (
- seg_id.multi_index >= 0
- && seg_id.multi_index < boost::size(multi)
- );
-
- // Call the single-version
- return Policy::apply(multi[seg_id.multi_index], seg_id, second, point);
- }
-};
-
-
-}} // namespace detail::copy_segments
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename MultiGeometry,
- typename SegmentIdentifier,
- typename PointOut
->
-struct copy_segment_point
- <
- multi_polygon_tag,
- MultiGeometry,
- SegmentIdentifier,
- PointOut
- >
- : detail::copy_segments::copy_segment_point_multi
- <
- MultiGeometry,
- SegmentIdentifier,
- PointOut,
- detail::copy_segments::copy_segment_point_polygon
- <
- typename boost::range_value<MultiGeometry>::type,
- SegmentIdentifier,
- PointOut
- >
- >
-{};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENT_POINT_HPP
Deleted: sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segments.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/copy_segments.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,101 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands.
-// Copyright Bruno Lalande 2008, 2009
-// 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)
-
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
-
-
-#include <boost/assert.hpp>
-#include <boost/range.hpp>
-
-#include <boost/geometry/algorithms/overlay/copy_segments.hpp>
-
-#include <boost/geometry/multi/core/ring_type.hpp>
-#include <boost/geometry/multi/core/tags.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace copy_segments
-{
-
-
-template
-<
- typename MultiGeometry,
- typename SegmentIdentifier,
- typename RangeOut,
- typename Policy
->
-struct copy_segments_multi
-{
- static inline void apply(MultiGeometry const& multi_geometry,
- SegmentIdentifier const& seg_id, int to_index,
- RangeOut& current_output)
- {
-
- BOOST_ASSERT
- (
- seg_id.multi_index >= 0
- && seg_id.multi_index < boost::size(multi_geometry)
- );
-
- // Call the single-version
- Policy::apply(multi_geometry[seg_id.multi_index],
- seg_id, to_index, current_output);
- }
-};
-
-
-}} // namespace detail::copy_segments
-#endif // DOXYGEN_NO_DETAIL
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename MultiPolygon,
- typename SegmentIdentifier,
- typename RangeOut
->
-struct copy_segments
- <
- multi_polygon_tag,
- MultiPolygon,
- SegmentIdentifier,
- RangeOut
- >
- : detail::copy_segments::copy_segments_multi
- <
- MultiPolygon,
- SegmentIdentifier,
- RangeOut,
- detail::copy_segments::copy_segments_polygon
- <
- typename boost::range_value<MultiPolygon>::type,
- SegmentIdentifier,
- RangeOut
- >
- >
-{};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_COPY_SEGMENTS_HPP
Deleted: sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/get_turns.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,133 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_TURNS_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_TURNS_HPP
-
-#include <boost/geometry/multi/core/is_multi.hpp>
-
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-
-#include <boost/geometry/multi/algorithms/distance.hpp>
-#include <boost/geometry/multi/iterators/range_type.hpp>
-
-#include <boost/geometry/multi/algorithms/detail/sections/get_section.hpp>
-#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
-
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename MultiTag1,
- typename MultiTag2,
- typename MultiGeometry1,
- typename MultiGeometry2,
- typename IntersectionPoints,
- typename Strategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns
- <
- MultiTag1, MultiTag2,
- true, true,
- MultiGeometry1, MultiGeometry2,
- IntersectionPoints,
- Strategy,
- AssignPolicy, InterruptPolicy
- >
- : detail::get_turns::get_turns_generic
- <
- MultiGeometry1,
- MultiGeometry2,
- IntersectionPoints,
- Strategy,
- AssignPolicy, InterruptPolicy
- >
-{};
-
-
-template
-<
- typename SingleTag,
- typename MultiTag,
- typename SingleGeometry,
- typename MultiGeometry,
- typename IntersectionPoints,
- typename Strategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns
- <
- SingleTag, MultiTag,
- false, true,
- SingleGeometry, MultiGeometry,
- IntersectionPoints,
- Strategy,
- AssignPolicy, InterruptPolicy
- >
- : detail::get_turns::get_turns_generic
- <
- SingleGeometry,
- MultiGeometry,
- IntersectionPoints,
- Strategy,
- AssignPolicy, InterruptPolicy
- >
-{};
-
-
-// Version for multi/single, necessary for multi_polygon/ring
-template
-<
- typename MultiTag,
- typename SingleTag,
- typename MultiGeometry,
- typename SingleGeometry,
- typename IntersectionPoints,
- typename Strategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct get_turns
- <
- MultiTag, SingleTag,
- true, false,
- MultiGeometry, SingleGeometry,
- IntersectionPoints,
- Strategy,
- AssignPolicy, InterruptPolicy
- >
- : detail::get_turns::get_turns_generic
- <
- MultiGeometry,
- SingleGeometry,
- IntersectionPoints,
- Strategy,
- AssignPolicy, InterruptPolicy
- >
-{};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_GET_TURNS_HPP
Deleted: sandbox/geometry/boost/geometry/multi/algorithms/overlay/self_turn_points.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/overlay/self_turn_points.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
+++ (empty file)
@@ -1,58 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
-// 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)
-
-#ifndef BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
-#define BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
-
-
-#include <boost/geometry/multi/core/tags.hpp>
-#include <boost/geometry/algorithms/overlay/self_turn_points.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-
-
-#ifndef DOXYGEN_NO_DISPATCH
-namespace dispatch
-{
-
-
-template
-<
- typename MultiPolygon,
- typename IntersectionPoints,
- typename IntersectionStrategy,
- typename AssignPolicy,
- typename InterruptPolicy
->
-struct self_get_turn_points
- <
- multi_polygon_tag, true, MultiPolygon,
- IntersectionPoints, IntersectionStrategy,
- AssignPolicy, InterruptPolicy
- >
- : detail::self_get_turn_points::get_turns
- <
- MultiPolygon,
- IntersectionPoints,
- IntersectionStrategy,
- AssignPolicy,
- InterruptPolicy
- >
-{};
-
-
-} // namespace dispatch
-#endif // DOXYGEN_NO_DISPATCH
-
-
-}} // namespace boost::geometry
-
-#endif // BOOST_GEOMETRY_MULTI_ALGORITHMS_OVERLAY_SELF_TURN_POINTS_HPP
Modified: sandbox/geometry/boost/geometry/multi/algorithms/union.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/union.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/union.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -10,7 +10,7 @@
#include <boost/geometry/algorithms/union.hpp>
-#include <boost/geometry/multi/algorithms/overlay/assemble.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/assemble.hpp>
namespace boost { namespace geometry
{
Modified: sandbox/geometry/boost/geometry/multi/multi.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/multi.hpp (original)
+++ sandbox/geometry/boost/geometry/multi/multi.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -46,8 +46,8 @@
#include <boost/geometry/multi/algorithms/detail/sections/get_section.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/sectionalize.hpp>
-#include <boost/geometry/multi/algorithms/overlay/copy_segments.hpp>
-#include <boost/geometry/multi/algorithms/overlay/self_turn_points.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/self_turn_points.hpp>
#include <boost/geometry/multi/geometries/multi_point.hpp>
#include <boost/geometry/multi/geometries/multi_linestring.hpp>
Modified: sandbox/geometry/libs/geometry/test/algorithms/difference.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/difference.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/difference.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -44,7 +44,7 @@
/* TODO: erroneous in assemble
test_one<polygon, polygon, polygon>("fitting",
fitting[0], fitting[1],
- 1, 0, 21.0,
+ 1, 0, 21.0,
1, 0, 4.0);
*/
@@ -76,24 +76,24 @@
7, 27, 3.18452380952381);
test_one<polygon, polygon, polygon>(
- "positive_negative",
- "POLYGON((0 0,0 4,4 4,4 0,0 0))",
- //"POLYGON((2 2,6 2,6 3,2 3,2 2))",
- "POLYGON((2 2,2 3,6 3,6 2,2 2))",
+ "positive_negative",
+ "POLYGON((0 0,0 4,4 4,4 0,0 0))",
+ //"POLYGON((2 2,6 2,6 3,2 3,2 2))",
+ "POLYGON((2 2,2 3,6 3,6 2,2 2))",
5, 22, 1.1901714,
5, 27, 1.6701714);
test_one<polygon, polygon, polygon>(
- "polygon_pseudo_line",
- "POLYGON((0 0,0 4,4 4,4 0,0 0))",
- "POLYGON((2 -2,2 -1,2 6,2 -2))",
+ "polygon_pseudo_line",
+ "POLYGON((0 0,0 4,4 4,4 0,0 0))",
+ "POLYGON((2 -2,2 -1,2 6,2 -2))",
5, 22, 1.1901714,
5, 27, 1.6701714);
test_one<polygon, polygon, polygon>(
- "reverse",
- "POLYGON((0 0,4 0,4 4,0 4,0 0))",
- "POLYGON((2 2,2 3,6 3,6 2,2 2))",
+ "reverse",
+ "POLYGON((0 0,4 0,4 4,0 4,0 0))",
+ "POLYGON((2 2,2 3,6 3,6 2,2 2))",
5, 22, 1.1901714,
5, 27, 1.6701714);
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/enrich_intersection_points.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/enrich_intersection_points.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/enrich_intersection_points.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -12,9 +12,9 @@
#include <boost/geometry/algorithms/intersection.hpp>
-//#include <boost/geometry/algorithms/overlay/get_intersection_points.hpp>
-//#include <boost/geometry/algorithms/overlay/merge_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/enrich_intersection_points.hpp>
+//#include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp>
+//#include <boost/geometry/algorithms/detail/overlay/merge_intersection_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
#include <boost/geometry/strategies/strategies.hpp>
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/get_turns.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/get_turns.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/get_turns.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -16,7 +16,7 @@
#include <boost/geometry/strategies/strategies.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_pies.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_pies.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_pies.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -14,13 +14,9 @@
#include <boost/timer.hpp>
#include <boost/lexical_cast.hpp>
-
-#include <boost/geometry/geometry.hpp>
-
-#include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
-#include <geometry_test_common.hpp>
#include <test_overlay_p_q.hpp>
+#include <boost/geometry/geometry.hpp>
template <typename Polygon>
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_stars.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_stars.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/intersection_stars.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -10,6 +10,13 @@
#define BOOST_GEOMETRY_NO_BOOST_TEST
+// For mixing int/float
+#if defined(_MSC_VER)
+#pragma warning( disable : 4267 )
+#endif
+
+
+
#include <algorithms/test_intersection.hpp>
#include <algorithms/test_overlay.hpp>
@@ -28,6 +35,7 @@
+
template <typename Polygon>
inline void make_star(Polygon& polygon,
int count, double factor1, double factor2, long double offset = 0)
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/random_ellipses_stars.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/random_ellipses_stars.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/random_ellipses_stars.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -14,11 +14,6 @@
#define BOOST_GEOMETRY_REPORT_OVERLAY_ERROR
#define BOOST_GEOMETRY_NO_BOOST_TEST
-// For mixing int/float
-#if defined(_MSC_VER)
-#pragma warning( disable : 4244 )
-#endif
-
#include <boost/timer.hpp>
#include <boost/lexical_cast.hpp>
@@ -28,15 +23,10 @@
#include <boost/random/variate_generator.hpp>
+#include <test_overlay_p_q.hpp>
#include <boost/geometry/geometry.hpp>
-#include <boost/geometry/extensions/gis/io/wkt/wkt.hpp>
-
-#include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
-#include <geometry_test_common.hpp>
-#include <test_overlay_p_q.hpp>
-
struct star_params
{
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/recursive_boxes.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/recursive_boxes.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/recursive_boxes.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -14,6 +14,7 @@
#define BOOST_GEOMETRY_REPORT_OVERLAY_ERROR
#define BOOST_GEOMETRY_NO_BOOST_TEST
+
#include <boost/timer.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/random/linear_congruential.hpp>
@@ -21,19 +22,15 @@
#include <boost/random/uniform_real.hpp>
#include <boost/random/variate_generator.hpp>
-
+#include <test_overlay_p_q.hpp>
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/multi/multi.hpp>
-#include <boost/geometry/multi/algorithms/overlay/assemble.hpp>
-
+#include <boost/geometry/multi/algorithms/detail/overlay/assemble.hpp>
#include <boost/geometry/multi/geometries/multi_polygon.hpp>
-
#include <boost/geometry/extensions/gis/io/wkt/wkt.hpp>
-
#include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
-#include <geometry_test_common.hpp>
-#include <test_overlay_p_q.hpp>
+
template <typename Polygon, typename Generator>
inline void make_box(Polygon& polygon, Generator& generator)
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/test_overlay_p_q.hpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/test_overlay_p_q.hpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/robustness/test_overlay_p_q.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -11,8 +11,16 @@
#include <fstream>
#include <iomanip>
+// For mixing int/float
+#if defined(_MSC_VER)
+#pragma warning( disable : 4244 )
+#pragma warning( disable : 4267 )
+#endif
+
+
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/extensions/gis/io/wkt/wkt.hpp>
+#include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
#include <geometry_test_common.hpp>
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/self_intersection_points.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -15,8 +15,8 @@
#include <boost/geometry/algorithms/intersection.hpp>
#include <boost/geometry/algorithms/intersects.hpp>
-//#include <boost/geometry/algorithms/overlay/self_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/self_turn_points.hpp>
+//#include <boost/geometry/algorithms/detail/overlay/self_intersection_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
#include <boost/geometry/strategies/strategies.hpp>
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -40,9 +40,9 @@
#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/algorithms/overlay/enrich_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/traverse.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
#include <boost/geometry/algorithms/area.hpp>
@@ -168,10 +168,10 @@
{
// Map characteristics
- // Create a rounded off point
+ // Create a rounded off point
std::pair<int, int> p
= std::make_pair(
- boost::numeric_cast<int>(0.5 + 10 * bg::get<0>(turn.point)),
+ boost::numeric_cast<int>(0.5 + 10 * bg::get<0>(turn.point)),
boost::numeric_cast<int>(0.5 + 10 * bg::get<1>(turn.point))
);
std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:8px";
@@ -182,8 +182,8 @@
<< " " << bg::operation_char(turn.operations[1].operation)
<< " (" << bg::method_char(turn.method) << ")"
<< (turn.ignore ? " (ignore) " : " ")
- << std::endl
-
+ << std::endl
+
<< "ip: " << turn.operations[0].enriched.travels_to_ip_index
<< "/" << turn.operations[1].enriched.travels_to_ip_index;
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse_gmp.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse_gmp.cpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse_gmp.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -34,9 +34,9 @@
#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/algorithms/overlay/enrich_intersection_points.hpp>
-#include <boost/geometry/algorithms/overlay/traverse.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
+#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
Modified: sandbox/geometry/libs/geometry/test/algorithms/test_overlay.hpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/test_overlay.hpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/test_overlay.hpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -83,7 +83,7 @@
{"POLYGON((4 4,4 16,16 16,16 4,4 4),(7 6,14 10,7 14,11 10,7 6))",
"POLYGON((2 2,2 18,18 18,18 2,2 2),(13 6,9 10,13 14,6 10,13 6))"};
-// case 2102 from "algorithms/overlay/robustness/assemble.hpp"
+// case 2102 from "algorithms/detail/overlay/robustness/assemble.hpp"
static std::string intersect_exterior_and_interiors_winded[2] =
{"POLYGON((2 0.5,0.5 2,0.5 8,2 9.5,6 9.5,8.5 8,8.5 2,7 0.5,2 0.5),(2 2,7 2,7 8,2 8,2 2))",
"POLYGON((1 1,1 9,8 9,8 1,1 1),(4 4,5 4,5 5,4 5,4 4))"};
Modified: sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp (original)
+++ sandbox/geometry/libs/geometry/test/multi/algorithms/multi_intersection.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -11,7 +11,7 @@
#include <algorithms/test_intersection.hpp>
#include <algorithms/test_overlay.hpp>
-#include <multi/algorithms/overlay/multi_overlay_cases.hpp>
+#include <multi/algorithms/detail/overlay/multi_overlay_cases.hpp>
#include <boost/geometry/multi/algorithms/intersection.hpp>
Modified: sandbox/geometry/libs/geometry/test/multi/algorithms/multi_union.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/multi/algorithms/multi_union.cpp (original)
+++ sandbox/geometry/libs/geometry/test/multi/algorithms/multi_union.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -11,7 +11,7 @@
#include <algorithms/test_union.hpp>
#include <algorithms/test_overlay.hpp>
-#include <multi/algorithms/overlay/multi_overlay_cases.hpp>
+#include <multi/algorithms/detail/overlay/multi_overlay_cases.hpp>
#include <boost/geometry/multi/algorithms/union.hpp>
Modified: sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp (original)
+++ sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp 2010-04-24 12:57:53 EDT (Sat, 24 Apr 2010)
@@ -14,9 +14,9 @@
#include <boost/geometry/multi/core/ring_type.hpp>
#include <boost/geometry/multi/algorithms/num_points.hpp>
-#include <boost/geometry/multi/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/multi/algorithms/overlay/copy_segments.hpp>
-#include <boost/geometry/multi/algorithms/overlay/copy_segment_point.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/copy_segments.hpp>
+#include <boost/geometry/multi/algorithms/detail/overlay/copy_segment_point.hpp>
#include <boost/geometry/multi/algorithms/detail/sections/get_full_section.hpp>
#include <boost/geometry/multi/geometries/multi_linestring.hpp>
@@ -72,7 +72,7 @@
test_traverse<ov::operation_union>, Tuple>
(
"recursive_box1", boost::make_tuple(1, 14.58),
- "MULTIPOLYGON(((3 9,3 10,4 10,4 9,3 9)),((1 1,1 2,2 2,2 1,1 1)),((7 8,7 9,8 9,8 8,7 8)),((8 0,8 1,9 1,9 0,8 0)))",
+ "MULTIPOLYGON(((3 9,3 10,4 10,4 9,3 9)),((1 1,1 2,2 2,2 1,1 1)),((7 8,7 9,8 9,8 8,7 8)),((8 0,8 1,9 1,9 0,8 0)))",
"MULTIPOLYGON(((0 1,0 2,1 2,1 1,0 1)),((7 5,7 6,8 6,8 5,7 5)),((1 1,1 1,2 1,2 1,2 0,2 0,1 0,1 0,1 0,1 1)))"
);
***/