Subject: [Boost-commit] svn:boost r85451 - in trunk: boost/geometry/algorithms/detail boost/geometry/algorithms/detail/overlay boost/geometry/util libs/geometry/doc libs/geometry/test/algorithms libs/geometry/test/multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2013-08-24 18:53:43
Author: barendgehrels
Date: 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013)
New Revision: 85451
URL: http://svn.boost.org/trac/boost/changeset/85451
Log:
[geometry] avoid generation of spikes in overlays, this fixes ticket 8364 and 8365. Added unit tests for these tickets. These changes result in (at about 3 places) changes in the output-number-of-points, this is verified visually
Added:
trunk/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp (contents, props changed)
trunk/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp (contents, props changed)
trunk/libs/geometry/test/multi/algorithms/multi_difference_spike.cpp
- copied unchanged from r85450, trunk/libs/geometry/test/algorithms/difference_spike.cpp
Deleted:
trunk/libs/geometry/test/algorithms/difference_spike.cpp
Text files modified:
trunk/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp | 63 ++++++++++++++++++++++++
trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp | 8 +-
trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp | 8 +-
trunk/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp | 71 +++++++++++++++++++++++++++
trunk/boost/geometry/util/math.hpp | 16 ++++-
trunk/libs/geometry/doc/release_notes.qbk | 3 +
trunk/libs/geometry/test/algorithms/Jamfile.v2 | 1
trunk/libs/geometry/test/algorithms/difference.cpp | 4
/dev/null | 105 ----------------------------------------
trunk/libs/geometry/test/algorithms/intersection.cpp | 4 +
trunk/libs/geometry/test/algorithms/union.cpp | 6 +-
trunk/libs/geometry/test/multi/algorithms/Jamfile.v2 | 1
trunk/libs/geometry/test/multi/algorithms/multi_difference_spike.cpp | 105 ++++++++++++++++++++++++++++++++++++++++
13 files changed, 272 insertions(+), 123 deletions(-)
Added: trunk/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -0,0 +1,63 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 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_OVERLAY_APPEND_NO_DUPS_OR_SPIKES_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_APPEND_NO_DUPS_OR_SPIKES_HPP
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/algorithms/append.hpp>
+#include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
+#include <boost/geometry/algorithms/detail/disjoint.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+template <typename Range, typename Point>
+inline void append_no_dups_or_spikes(Range& range, Point const& point)
+{
+#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
+ std::cout << " add: ("
+ << geometry::get<0>(point) << ", " << geometry::get<1>(point) << ")"
+ << std::endl;
+#endif
+
+ geometry::append(range, point);
+ // If a point is equal, or forming a spike, remove the pen-ultimate point because this one caused the spike.
+ // If so, the now-new-pen-ultimate point can again cause a spike (possibly at a corner). So keep doing this.
+ // Besides spikes it will also avoid duplicates.
+ while(boost::size(range) >= 3
+ && point_is_spike_or_equal(point, *(boost::end(range) - 3), *(boost::end(range) - 2)))
+ {
+ // There is not yet a concept for this in Boost.Geometry or Boost.Range
+ range.erase(boost::end(range) - 2);
+ }
+
+ // There might still be one duplicate not catched by the condition above
+ if (boost::size(range) == 2
+ && geometry::detail::equals::equals_point_point(*boost::begin(range), point))
+ {
+ range.erase(boost::begin(range));
+ }
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_APPEND_NO_DUPS_OR_SPIKES_HPP
Modified: trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -27,7 +27,7 @@
#include <boost/geometry/views/closeable_view.hpp>
#include <boost/geometry/views/reversible_view.hpp>
-#include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
+#include <boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp>
namespace boost { namespace geometry
{
@@ -93,7 +93,7 @@
for (size_type i = 0; i < count; ++i, ++it)
{
- detail::overlay::append_no_duplicates(current_output, *it);
+ detail::overlay::append_no_dups_or_spikes(current_output, *it);
}
}
};
@@ -129,7 +129,7 @@
for (size_type i = 0; i < count; ++i, ++it)
{
- detail::overlay::append_no_duplicates(current_output, *it);
+ detail::overlay::append_no_dups_or_spikes(current_output, *it);
}
}
};
@@ -195,7 +195,7 @@
// (see comments in ring-version)
for (int i = 0; i < count; i++, index++)
{
- detail::overlay::append_no_duplicates(current_output, bp[index % 5]);
+ detail::overlay::append_no_dups_or_spikes(current_output, bp[index % 5]);
}
}
Modified: trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -13,7 +13,7 @@
#include <boost/range.hpp>
-#include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
+#include <boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp>
#include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
@@ -139,7 +139,8 @@
seg_id = info.seg_id;
}
- detail::overlay::append_no_duplicates(current_output, ip->point);
+ detail::overlay::append_no_dups_or_spikes(current_output, ip->point);
+
return true;
}
@@ -277,8 +278,7 @@
set_visited_for_continue(*it, *iit);
ring_type current_output;
- detail::overlay::append_no_duplicates(current_output,
- it->point, true);
+ geometry::append(current_output, it->point);
turn_iterator current = it;
turn_operation_iterator_type current_iit = iit;
Added: trunk/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -0,0 +1,71 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2008-2013 Bruno Lalande, Paris, France.
+// Copyright (c) 2009-2013 Mateusz Loskot, London, UK.
+// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
+
+// 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_POINT_IS_EQUAL_OR_SPIKE_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
+
+#include <boost/geometry/arithmetic/arithmetic.hpp>
+#include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
+#include <boost/geometry/strategies/side.hpp>
+#include <boost/geometry/util/math.hpp>
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail
+{
+
+template <typename Point1, typename Point2, typename Point3>
+static inline bool point_is_spike_or_equal(Point1 const& last_point, Point2 const& segment_a, Point3 const& segment_b)
+{
+ typedef typename strategy::side::services::default_strategy
+ <
+ typename cs_tag<Point1>::type
+ >::type side_strategy;
+
+ typedef Point1 vector_type;
+
+ int const side = side_strategy::apply(last_point, segment_a, segment_b);
+ if (side == 0)
+ {
+ // Last point is collinear w.r.t previous segment.
+ // Check if it is equal
+ vector_type diff1;
+ conversion::convert_point_to_point(last_point, diff1);
+ geometry::subtract_point(diff1, segment_b);
+ int const sgn_x1 = math::sign(geometry::get<0>(diff1));
+ int const sgn_y1 = math::sign(geometry::get<1>(diff1));
+ if (sgn_x1 == 0 && sgn_y1 == 0)
+ {
+ return true;
+ }
+
+ // Check if it moves forward
+ vector_type diff2;
+ conversion::convert_point_to_point(segment_b, diff2);
+ geometry::subtract_point(diff2, segment_a);
+ int const sgn_x2 = math::sign(geometry::get<0>(diff2));
+ int const sgn_y2 = math::sign(geometry::get<1>(diff2));
+
+ return sgn_x1 != sgn_x2 || sgn_y1 != sgn_y2;
+ }
+ return false;
+}
+
+} // namespace detail
+#endif
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
Modified: trunk/boost/geometry/util/math.hpp
==============================================================================
--- trunk/boost/geometry/util/math.hpp Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/boost/geometry/util/math.hpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -216,16 +216,26 @@
return value * value;
}
-
/*!
\brief Short utility to workaround gcc/clang problem that abs is converting to integer
\ingroup utility
*/
template<typename T>
-inline T abs(const T& t)
+inline T abs(T const& value)
{
using std::abs;
- return abs(t);
+ return abs(value);
+}
+
+/*!
+\brief Short utility to calculate the sign of a number: -1 (negative), 0 (zero), 1 (positive)
+\ingroup utility
+*/
+template <typename T>
+static inline int sign(T const& val)
+{
+ T const zero = T();
+ return val > zero ? 1 : val < zero ? -1 : 0;
}
Modified: trunk/libs/geometry/doc/release_notes.qbk
==============================================================================
--- trunk/libs/geometry/doc/release_notes.qbk Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/libs/geometry/doc/release_notes.qbk 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -29,11 +29,14 @@
* [@https://svn.boost.org/trac/boost/ticket/8969 8969] boost::geometry::model::point single argument constructor should be explicit
* [@https://svn.boost.org/trac/boost/ticket/8825 8825] Patch adding member variable documentation to doxygen_xml2qbk
+* [@https://svn.boost.org/trac/boost/ticket/8364 8364] Invalid input exception, caused by spikes in previous steps, fixed
+* [@https://svn.boost.org/trac/boost/ticket/8365 8365] Invalid input exception, caused by spikes in previous steps, fixed
[*Internal changes]
* Distance-strategy TODO
* Transform-strategy TODO
+* Spikes (could be generated in difference) in integer-based overlays are now avoided during generation
* Cleanup, removed old MSVC2005 project files, let all tests pass green (also in extensions)
Modified: trunk/libs/geometry/test/algorithms/Jamfile.v2
==============================================================================
--- trunk/libs/geometry/test/algorithms/Jamfile.v2 Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/libs/geometry/test/algorithms/Jamfile.v2 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -21,7 +21,6 @@
[ run convert.cpp ]
[ run covered_by.cpp ]
[ run difference.cpp ]
- [ run difference_spike.cpp ]
[ run disjoint.cpp ]
[ run distance.cpp ]
[ run envelope.cpp ]
Modified: trunk/libs/geometry/test/algorithms/difference.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/difference.cpp Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/libs/geometry/test/algorithms/difference.cpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -258,8 +258,8 @@
{
test_one<polygon, polygon, polygon>("buffer_mp2",
buffer_mp2[0], buffer_mp2[1],
- 1, 92, 12.09857,
- 1, 157, 24.19787);
+ 1, 91, 12.09857,
+ 1, 156, 24.19787);
}
/*** TODO: self-tangencies for difference
Deleted: trunk/libs/geometry/test/algorithms/difference_spike.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/difference_spike.cpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85450)
+++ /dev/null 00:00:00 1970 (deleted)
@@ -1,105 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Unit Test
-
-// Copyright (c) 2013 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)
-
-
-#include <boost/geometry.hpp>
-#include <boost/geometry/geometries/geometries.hpp>
-#include <boost/geometry/geometries/point_xy.hpp>
-#include <boost/geometry/multi/geometries/multi_geometries.hpp>
-
-#include <algorithms/test_difference.hpp>
-
-
-template <typename P, bool ClockWise, bool Closed>
-void test_spikes_in_ticket_8364()
-{
- // See: https://svn.boost.org/trac/boost/ticket/8364
- //_TPolygon<T> polygon( "MULTIPOLYGON(((1031 1056,3232 1056,3232 2856,1031 2856)))" );
- //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 1458,1032 1212,2136 2328,3234 2220,3234 2412,2136 2646)))" );
- //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 1764,1032 1458,2136 2646,3234 2412,3234 2532,2136 2790)))" );
- // RESULTS OF ABOVE IS USED IN STEP 3 BELOW
- //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 2130,1032 1764,2052 2712)),((3234 2580,2558 2690,3234 2532)),((2558 2690,2136 2790,2052 2712,2136 2760)))" ); USED IN STEP 3
- //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 2556,1032 2130,1778 2556)),((3234 2580,2136 2760,1778 2556,3234 2556)))" ); USED IN STEP 4
- // NOTE: polygons below are closed and clockwise
-
- typedef typename bg::coordinate_type<P>::type ct;
- typedef bg::model::polygon<P, ClockWise, Closed> polygon;
- typedef bg::model::multi_polygon<polygon> multi_polygon;
-
- // The difference of polygons below result in a spike. The spike should be there, it is also generated in ttmath,
- // and (e.g.) in SQL Server. However, using int-coordinates, the spike makes the polygon invalid. Therefore it is now (since August 2013) checked and removed.
-
- // So using int's, the spike is removed automatically. Therefore there is one polygon less, and less points. Also area differs
- test_one<polygon, multi_polygon, multi_polygon>("ticket_8364_step3",
- "MULTIPOLYGON(((3232 2532,2136 2790,1032 1764,1032 1458,1032 1212,2136 2328,3232 2220,3232 1056,1031 1056,1031 2856,3232 2856,3232 2532)))",
- "MULTIPOLYGON(((1032 2130,2052 2712,1032 1764,1032 2130)),((3234 2580,3234 2532,2558 2690,3234 2580)),((2558 2690,2136 2760,2052 2712,2136 2790,2558 2690)))",
- if_typed<ct, int>(1, 2),
- if_typed<ct, int>(15, 22),
- if_typed<ct, int>(2775561.0, 2775256.487954), // SQL Server: 2775256.47588724
- 3,
- 14,
- if_typed<ct, int>(7710.5, 7810.487954)); // SQL Server: 7810.48711165739
-
- test_one<polygon, multi_polygon, multi_polygon>("ticket_8364_step4",
- "MULTIPOLYGON(((2567 2688,2136 2790,2052 2712,1032 2130,1032 1764,1032 1458,1032 1212,2136 2328,3232 2220,3232 1056,1031 1056,1031 2856,3232 2856,3232 2580,2567 2688)))",
- "MULTIPOLYGON(((1032 2556,1778 2556,1032 2130,1032 2556)),((3234 2580,3234 2556,1778 2556,2136 2760,3234 2580)))",
- 1,
- if_typed<ct, int>(17, 20),
- if_typed<ct, int>(2616292.0, 2616029.559567), // SQL Server: 2616029.55616044
- 1,
- if_typed<ct, int>(9, 11),
- if_typed<ct, int>(160996.0, 161054.559567)); // SQL Server: 161054.560110092
-}
-
-template <typename P, bool ClockWise, bool Closed>
-void test_spikes_in_ticket_8365()
-{
- // See: https://svn.boost.org/trac/boost/ticket/8365
- // NOTE: polygons below are closed and clockwise
-
- typedef typename bg::coordinate_type<P>::type ct;
- typedef bg::model::polygon<P, ClockWise, Closed> polygon;
- typedef bg::model::multi_polygon<polygon> multi_polygon;
-
- test_one<polygon, multi_polygon, multi_polygon>("ticket_8365_step2",
- "MULTIPOLYGON(((971 2704,971 1402,4640 1402,3912 1722,3180 2376,3912 1884,4643 1402,5395 1402,5395 3353,971 3353,971 2865,1704 3348)))",
- "MULTIPOLYGON(((5388 1560,4650 1722,3912 1884,4650 1398)),((2442 3186,1704 3348,966 2700,1704 3024)))",
- if_typed<ct, int>(1, 2),
- if_typed<ct, int>(17, 21),
- if_typed<ct, int>(7974930.5, 7975207.6047877), // SQL Server:
- 2,
- 9,
- if_typed<ct, int>(199.0, 197.1047877)); // SQL Server:
-}
-
-
-
-
-
-int test_main(int, char* [])
-{
- test_spikes_in_ticket_8364<bg::model::d2::point_xy<double>, true, true>();
- test_spikes_in_ticket_8364<bg::model::d2::point_xy<int>, true, true>();
- test_spikes_in_ticket_8364<bg::model::d2::point_xy<double>, false, false>();
- test_spikes_in_ticket_8364<bg::model::d2::point_xy<int>, false, false>();
-
- test_spikes_in_ticket_8365<bg::model::d2::point_xy<double>, true, true>();
- test_spikes_in_ticket_8365<bg::model::d2::point_xy<int>, true, true >();
- test_spikes_in_ticket_8365<bg::model::d2::point_xy<double>, false, false>();
- test_spikes_in_ticket_8365<bg::model::d2::point_xy<int>, false, false >();
-
-#ifdef HAVE_TTMATH
- std::cout << "Testing TTMATH" << std::endl;
- test_spikes_in_ticket_8364<bg::model::d2::point_xy<ttmath_big>, true, true>();
- test_spikes_in_ticket_8365<bg::model::d2::point_xy<ttmath_big>, true, true>();
-#endif
-
- return 0;
-}
-
Modified: trunk/libs/geometry/test/algorithms/intersection.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/intersection.cpp Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/libs/geometry/test/algorithms/intersection.cpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -182,9 +182,11 @@
//std::cout << typeid(ct).name() << std::endl;
+ // Pointcount for ttmath/double (both 5) or float (4)
+ // double returns 5 (since method append_no_dups_or_spikes)
test_one<Polygon, Polygon, Polygon>("ggl_list_20110306_javier",
ggl_list_20110306_javier[0], ggl_list_20110306_javier[1],
- 1, if_typed_tt<ct>(5, 4),
+ 1, if_typed<ct, float>(4, 5),
0.6649875,
if_typed<ct, float>(1.0, 0.01));
Modified: trunk/libs/geometry/test/algorithms/union.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/union.cpp Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/libs/geometry/test/algorithms/union.cpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -282,9 +282,9 @@
// Robustness issues, followed out buffer-robustness-tests, test them also reverse
test_one<Polygon, Polygon, Polygon>("buffer_rt_f", buffer_rt_f[0], buffer_rt_f[1],
- 1, 0, if_typed<ct, double>(22, 23), 4.60853);
+ 1, 0, if_typed<ct, double>(21, 23), 4.60853);
test_one<Polygon, Polygon, Polygon>("buffer_rt_f_rev", buffer_rt_f[1], buffer_rt_f[0],
- 1, 0, if_typed<ct, double>(22, 23), 4.60853);
+ 1, 0, if_typed<ct, double>(21, 23), 4.60853);
test_one<Polygon, Polygon, Polygon>("buffer_rt_g", buffer_rt_g[0], buffer_rt_g[1],
1, 0, 17, 16.571);
@@ -352,7 +352,7 @@
// Contains robustness issue for collinear-opposite.
// In double it delivers a polygon and a hole
test_one<Polygon, Polygon, Polygon>("buffer_mp2", buffer_mp2[0], buffer_mp2[1],
- 1, 1, 218, 36.7535642);
+ 1, 1, 217, 36.7535642);
}
else if (boost::is_same<ct, float>::type::value)
{
Modified: trunk/libs/geometry/test/multi/algorithms/Jamfile.v2
==============================================================================
--- trunk/libs/geometry/test/multi/algorithms/Jamfile.v2 Sat Aug 24 17:10:12 2013 (r85450)
+++ trunk/libs/geometry/test/multi/algorithms/Jamfile.v2 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451)
@@ -17,6 +17,7 @@
[ run multi_correct.cpp ]
[ run multi_covered_by.cpp ]
[ run multi_difference.cpp ]
+ [ run multi_difference_spike.cpp ]
[ run multi_disjoint.cpp ]
[ run multi_distance.cpp ]
[ run multi_envelope.cpp ]
Copied: trunk/libs/geometry/test/multi/algorithms/multi_difference_spike.cpp (from r85450, trunk/libs/geometry/test/algorithms/difference_spike.cpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/geometry/test/multi/algorithms/multi_difference_spike.cpp 2013-08-24 18:53:43 EDT (Sat, 24 Aug 2013) (r85451, copy of r85450, trunk/libs/geometry/test/algorithms/difference_spike.cpp)
@@ -0,0 +1,105 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+// Unit Test
+
+// Copyright (c) 2013 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)
+
+
+#include <boost/geometry.hpp>
+#include <boost/geometry/geometries/geometries.hpp>
+#include <boost/geometry/geometries/point_xy.hpp>
+#include <boost/geometry/multi/geometries/multi_geometries.hpp>
+
+#include <algorithms/test_difference.hpp>
+
+
+template <typename P, bool ClockWise, bool Closed>
+void test_spikes_in_ticket_8364()
+{
+ // See: https://svn.boost.org/trac/boost/ticket/8364
+ //_TPolygon<T> polygon( "MULTIPOLYGON(((1031 1056,3232 1056,3232 2856,1031 2856)))" );
+ //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 1458,1032 1212,2136 2328,3234 2220,3234 2412,2136 2646)))" );
+ //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 1764,1032 1458,2136 2646,3234 2412,3234 2532,2136 2790)))" );
+ // RESULTS OF ABOVE IS USED IN STEP 3 BELOW
+ //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 2130,1032 1764,2052 2712)),((3234 2580,2558 2690,3234 2532)),((2558 2690,2136 2790,2052 2712,2136 2760)))" ); USED IN STEP 3
+ //polygon -= _TPolygon<T>( "MULTIPOLYGON(((1032 2556,1032 2130,1778 2556)),((3234 2580,2136 2760,1778 2556,3234 2556)))" ); USED IN STEP 4
+ // NOTE: polygons below are closed and clockwise
+
+ typedef typename bg::coordinate_type<P>::type ct;
+ typedef bg::model::polygon<P, ClockWise, Closed> polygon;
+ typedef bg::model::multi_polygon<polygon> multi_polygon;
+
+ // The difference of polygons below result in a spike. The spike should be there, it is also generated in ttmath,
+ // and (e.g.) in SQL Server. However, using int-coordinates, the spike makes the polygon invalid. Therefore it is now (since August 2013) checked and removed.
+
+ // So using int's, the spike is removed automatically. Therefore there is one polygon less, and less points. Also area differs
+ test_one<polygon, multi_polygon, multi_polygon>("ticket_8364_step3",
+ "MULTIPOLYGON(((3232 2532,2136 2790,1032 1764,1032 1458,1032 1212,2136 2328,3232 2220,3232 1056,1031 1056,1031 2856,3232 2856,3232 2532)))",
+ "MULTIPOLYGON(((1032 2130,2052 2712,1032 1764,1032 2130)),((3234 2580,3234 2532,2558 2690,3234 2580)),((2558 2690,2136 2760,2052 2712,2136 2790,2558 2690)))",
+ if_typed<ct, int>(1, 2),
+ if_typed<ct, int>(15, 22),
+ if_typed<ct, int>(2775561.0, 2775256.487954), // SQL Server: 2775256.47588724
+ 3,
+ 14,
+ if_typed<ct, int>(7710.5, 7810.487954)); // SQL Server: 7810.48711165739
+
+ test_one<polygon, multi_polygon, multi_polygon>("ticket_8364_step4",
+ "MULTIPOLYGON(((2567 2688,2136 2790,2052 2712,1032 2130,1032 1764,1032 1458,1032 1212,2136 2328,3232 2220,3232 1056,1031 1056,1031 2856,3232 2856,3232 2580,2567 2688)))",
+ "MULTIPOLYGON(((1032 2556,1778 2556,1032 2130,1032 2556)),((3234 2580,3234 2556,1778 2556,2136 2760,3234 2580)))",
+ 1,
+ if_typed<ct, int>(17, 20),
+ if_typed<ct, int>(2616292.0, 2616029.559567), // SQL Server: 2616029.55616044
+ 1,
+ if_typed<ct, int>(9, 11),
+ if_typed<ct, int>(160996.0, 161054.559567)); // SQL Server: 161054.560110092
+}
+
+template <typename P, bool ClockWise, bool Closed>
+void test_spikes_in_ticket_8365()
+{
+ // See: https://svn.boost.org/trac/boost/ticket/8365
+ // NOTE: polygons below are closed and clockwise
+
+ typedef typename bg::coordinate_type<P>::type ct;
+ typedef bg::model::polygon<P, ClockWise, Closed> polygon;
+ typedef bg::model::multi_polygon<polygon> multi_polygon;
+
+ test_one<polygon, multi_polygon, multi_polygon>("ticket_8365_step2",
+ "MULTIPOLYGON(((971 2704,971 1402,4640 1402,3912 1722,3180 2376,3912 1884,4643 1402,5395 1402,5395 3353,971 3353,971 2865,1704 3348)))",
+ "MULTIPOLYGON(((5388 1560,4650 1722,3912 1884,4650 1398)),((2442 3186,1704 3348,966 2700,1704 3024)))",
+ if_typed<ct, int>(1, 2),
+ if_typed<ct, int>(17, 21),
+ if_typed<ct, int>(7974930.5, 7975207.6047877), // SQL Server:
+ 2,
+ 9,
+ if_typed<ct, int>(199.0, 197.1047877)); // SQL Server:
+}
+
+
+
+
+
+int test_main(int, char* [])
+{
+ test_spikes_in_ticket_8364<bg::model::d2::point_xy<double>, true, true>();
+ test_spikes_in_ticket_8364<bg::model::d2::point_xy<int>, true, true>();
+ test_spikes_in_ticket_8364<bg::model::d2::point_xy<double>, false, false>();
+ test_spikes_in_ticket_8364<bg::model::d2::point_xy<int>, false, false>();
+
+ test_spikes_in_ticket_8365<bg::model::d2::point_xy<double>, true, true>();
+ test_spikes_in_ticket_8365<bg::model::d2::point_xy<int>, true, true >();
+ test_spikes_in_ticket_8365<bg::model::d2::point_xy<double>, false, false>();
+ test_spikes_in_ticket_8365<bg::model::d2::point_xy<int>, false, false >();
+
+#ifdef HAVE_TTMATH
+ std::cout << "Testing TTMATH" << std::endl;
+ test_spikes_in_ticket_8364<bg::model::d2::point_xy<ttmath_big>, true, true>();
+ test_spikes_in_ticket_8365<bg::model::d2::point_xy<ttmath_big>, true, true>();
+#endif
+
+ return 0;
+}
+