Subject: [Boost-commit] svn:boost r71357 - in trunk/boost/geometry/algorithms/detail: . overlay
From: barend.gehrels_at_[hidden]
Date: 2011-04-17 16:55:58
Author: barendgehrels
Date: 2011-04-17 16:55:57 EDT (Sun, 17 Apr 2011)
New Revision: 71357
URL: http://svn.boost.org/trac/boost/changeset/71357
Log:
Added check for valid input for all intersections. If not valid, it throws.
Added:
trunk/boost/geometry/algorithms/detail/has_self_intersections.hpp (contents, props changed)
Text files modified:
trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp | 5 +++++
trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp | 27 ++++++++++++++++++++++++++-
2 files changed, 31 insertions(+), 1 deletions(-)
Added: trunk/boost/geometry/algorithms/detail/has_self_intersections.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/has_self_intersections.hpp 2011-04-17 16:55:57 EDT (Sun, 17 Apr 2011)
@@ -0,0 +1,121 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2011 Barend Gehrels, 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_HAS_SELF_INTERSECTIONS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
+
+#include <deque>
+
+#include <boost/range.hpp>
+#include <boost/geometry/core/point_type.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
+
+#include <boost/geometry/multi/algorithms/detail/overlay/self_turn_points.hpp>
+
+#ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
+# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
+# include <boost/geometry/util/write_dsv.hpp>
+#endif
+
+
+namespace boost { namespace geometry
+{
+
+
+#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
+
+/*!
+\brief Overlay Invalid Input Exception
+\ingroup overlay
+\details The overlay_invalid_input_exception is thrown at invalid input
+ */
+class overlay_invalid_input_exception : public geometry::exception
+{
+public:
+
+ inline overlay_invalid_input_exception() {}
+
+ virtual char const* what() const throw()
+ {
+ return "Boost.Geometry Overlay invald input exception";
+ }
+};
+
+#endif
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+template <typename Geometry>
+inline bool has_self_intersections(Geometry const& geometry)
+{
+ using namespace boost::geometry;
+ typedef typename point_type<Geometry>::type point_type;
+ typedef detail::overlay::turn_info<point_type> turn_info;
+ std::deque<turn_info> turns;
+ detail::get_turns::no_interrupt_policy policy;
+ geometry::self_turns<detail::overlay::assign_null_policy>(geometry, turns, policy);
+
+#ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
+ bool first = true;
+#endif
+ for(typename std::deque<turn_info>::const_iterator it = boost::begin(turns);
+ it != boost::end(turns); ++it)
+ {
+ turn_info const& info = *it;
+ bool const both_union_turn =
+ info.operations[0].operation == detail::overlay::operation_union
+ && info.operations[1].operation == detail::overlay::operation_union;
+ bool const both_intersection_turn =
+ info.operations[0].operation == detail::overlay::operation_intersection
+ && info.operations[1].operation == detail::overlay::operation_intersection;
+
+ bool const valid = (both_union_turn || both_intersection_turn)
+ && (info.method == detail::overlay::method_touch
+ || info.method == detail::overlay::method_touch_interior);
+
+ if (! valid)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
+ if (first)
+ {
+ std::cout << "turn points: " << std::endl;
+ first = false;
+ }
+ std::cout << method_char(info.method);
+ for (int i = 0; i < 2; i++)
+ {
+ std::cout << " " << operation_char(info.operations[i].operation);
+ }
+ std::cout << " " << geometry::dsv(info.point) << std::endl;
+#endif
+
+#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
+ throw overlay_invalid_input_exception();
+#endif
+ }
+
+ }
+ return false;
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
+
Modified: trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp 2011-04-17 16:55:57 EDT (Sun, 17 Apr 2011)
@@ -25,6 +25,8 @@
#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/algorithms/detail/has_self_intersections.hpp>
+
#include <boost/geometry/algorithms/num_points.hpp>
#include <boost/geometry/algorithms/reverse.hpp>
@@ -168,6 +170,9 @@
GeometryOut, Direction, ReverseOut
>(geometry1, geometry2, out);
}
+
+ has_self_intersections(geometry1);
+ has_self_intersections(geometry2);
container_type turn_points;
Modified: trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp 2011-04-17 16:55:57 EDT (Sun, 17 Apr 2011)
@@ -138,6 +138,31 @@
template
<
+ typename Box,
+ typename Turns,
+ typename TurnPolicy,
+ typename InterruptPolicy
+>
+struct self_get_turn_points
+ <
+ box_tag, Box,
+ Turns,
+ TurnPolicy,
+ InterruptPolicy
+ >
+{
+ static inline bool apply(
+ Box const& ,
+ Turns& ,
+ InterruptPolicy& )
+ {
+ return true;
+ }
+};
+
+
+template
+<
typename Polygon,
typename Turns,
typename TurnPolicy,
@@ -182,7 +207,7 @@
typename Turns,
typename InterruptPolicy
>
-inline void get_turns(Geometry const& geometry,
+inline void self_turns(Geometry const& geometry,
Turns& turns, InterruptPolicy& interrupt_policy)
{
concept::check<Geometry const>();