Subject: [Boost-commit] svn:boost r86579 - in trunk: boost/geometry/algorithms libs/geometry/doc libs/geometry/test/algorithms libs/geometry/test/algorithms/overlay
From: barend.gehrels_at_[hidden]
Date: 2013-11-06 17:42:02
Author: barendgehrels
Date: 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)
New Revision: 86579
URL: http://svn.boost.org/trac/boost/changeset/86579
Log:
[geometry] fixed ticket 8310, disjoint did give the wrong results. Fixed using point_on_surface. Added unit test. Also tests for overlay algorithms because they might suffer from the same problem
Text files modified:
trunk/boost/geometry/algorithms/disjoint.hpp | 56 +++++++++++++--------------------------
trunk/boost/geometry/algorithms/touches.hpp | 39 ++++++++++++++++++++++++++-
trunk/libs/geometry/doc/release_notes.qbk | 2 +
trunk/libs/geometry/test/algorithms/difference.cpp | 15 ++++++++++
trunk/libs/geometry/test/algorithms/disjoint.cpp | 6 ++++
trunk/libs/geometry/test/algorithms/intersection.cpp | 7 +++++
trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp | 20 ++++++++++----
trunk/libs/geometry/test/algorithms/point_on_surface.cpp | 5 ++-
trunk/libs/geometry/test/algorithms/union.cpp | 7 +++++
9 files changed, 110 insertions(+), 47 deletions(-)
Modified: trunk/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/disjoint.hpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/boost/geometry/algorithms/disjoint.hpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -31,9 +31,8 @@
#include <boost/geometry/core/reverse_dispatch.hpp>
#include <boost/geometry/algorithms/detail/disjoint.hpp>
-#include <boost/geometry/algorithms/detail/for_each_range.hpp>
-#include <boost/geometry/algorithms/detail/point_on_border.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/point_on_surface.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>
@@ -49,39 +48,6 @@
namespace detail { namespace disjoint
{
-template<typename Geometry>
-struct check_each_ring_for_within
-{
- bool has_within;
- Geometry const& m_geometry;
-
- inline check_each_ring_for_within(Geometry const& g)
- : has_within(false)
- , m_geometry(g)
- {}
-
- template <typename Range>
- inline void apply(Range const& range)
- {
- typename geometry::point_type<Range>::type p;
- geometry::point_on_border(p, range);
- if (geometry::within(p, m_geometry))
- {
- has_within = true;
- }
- }
-};
-
-template <typename FirstGeometry, typename SecondGeometry>
-inline bool rings_containing(FirstGeometry const& geometry1,
- SecondGeometry const& geometry2)
-{
- check_each_ring_for_within<FirstGeometry> checker(geometry1);
- geometry::detail::for_each_range(geometry2, checker);
- return checker.has_within;
-}
-
-
struct assign_disjoint_policy
{
// We want to include all points:
@@ -166,8 +132,24 @@
// If there is no intersection of segments, they might located
// inside each other
- if (rings_containing(geometry1, geometry2)
- || rings_containing(geometry2, geometry1))
+
+ // We check that using a point on the surface, and see if that is inside
+ // the other geometry. And vice versa.
+
+ typedef typename geometry::point_type<Geometry1>::type point_type1;
+ typedef typename geometry::point_type<Geometry2>::type point_type2;
+
+ if (geometry::within
+ (
+ geometry::return_point_on_surface(geometry1),
+ geometry2
+ )
+ || geometry::within
+ (
+ geometry::return_point_on_surface(geometry2),
+ geometry1
+ )
+ )
{
return false;
}
Modified: trunk/boost/geometry/algorithms/touches.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/touches.hpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/boost/geometry/algorithms/touches.hpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -19,6 +19,7 @@
#include <deque>
#include <boost/geometry/geometries/concepts/check.hpp>
+#include <boost/geometry/algorithms/detail/for_each_range.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
#include <boost/geometry/algorithms/disjoint.hpp>
@@ -83,6 +84,40 @@
return has_touch;
}
+template<typename Geometry>
+struct check_each_ring_for_within
+{
+ bool has_within;
+ Geometry const& m_geometry;
+
+ inline check_each_ring_for_within(Geometry const& g)
+ : has_within(false)
+ , m_geometry(g)
+ {}
+
+ template <typename Range>
+ inline void apply(Range const& range)
+ {
+ typename geometry::point_type<Range>::type p;
+ geometry::point_on_border(p, range);
+ if (geometry::within(p, m_geometry))
+ {
+ has_within = true;
+ }
+ }
+};
+
+
+template <typename FirstGeometry, typename SecondGeometry>
+inline bool rings_containing(FirstGeometry const& geometry1,
+ SecondGeometry const& geometry2)
+{
+ check_each_ring_for_within<FirstGeometry> checker(geometry1);
+ geometry::detail::for_each_range(geometry2, checker);
+ return checker.has_within;
+}
+
+
}}
#endif // DOXYGEN_NO_DETAIL
@@ -173,8 +208,8 @@
>(geometry1, geometry2, turns, policy);
return detail::touches::has_only_turns(turns)
- && ! geometry::detail::disjoint::rings_containing(geometry1, geometry2)
- && ! geometry::detail::disjoint::rings_containing(geometry2, geometry1)
+ && ! geometry::detail::touches::rings_containing(geometry1, geometry2)
+ && ! geometry::detail::touches::rings_containing(geometry2, geometry1)
;
}
Modified: trunk/libs/geometry/doc/release_notes.qbk
==============================================================================
--- trunk/libs/geometry/doc/release_notes.qbk Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/libs/geometry/doc/release_notes.qbk 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -20,11 +20,13 @@
[*Additional functionality]
* added remove_spikes, algorithm to remove spikes from a ring, polygon or multi_polygon.
+* added point_on_surface, generating a point lying on the surface (interior) of the polygon
[*Solved tickets]
* [@https://svn.boost.org/trac/boost/ticket/9245 9245] Check for process errors in make_qbk.py
* [@https://svn.boost.org/trac/boost/ticket/9081 9081] Booleans create self-intersecting polygons from non-self-intersecting polygons
+* [@https://svn.boost.org/trac/boost/ticket/8310 8310] Wrong results with overlapping polygons (fixed using point_on_surface for disjoint)
[/=================]
[heading Boost 1.55]
Modified: trunk/libs/geometry/test/algorithms/difference.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/difference.cpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/libs/geometry/test/algorithms/difference.cpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -321,6 +321,21 @@
}
#endif
+ // Ticket 8310, one should be completely subtracted from the other.
+ test_one<polygon, polygon, polygon>("ticket_8310a",
+ ticket_8310a[0], ticket_8310a[1],
+ 1, 10, 10.11562724,
+ 0, 0, 0);
+ test_one<polygon, polygon, polygon>("ticket_8310b",
+ ticket_8310b[0], ticket_8310b[1],
+ 1, 10, 10.12655608,
+ 0, 0, 0);
+ test_one<polygon, polygon, polygon>("ticket_8310c",
+ ticket_8310c[0], ticket_8310c[1],
+ 1, 10, 10.03103292,
+ 0, 0, 0);
+
+
// Other combi's
{
test_one<polygon, polygon, ring>(
Modified: trunk/libs/geometry/test/algorithms/disjoint.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/disjoint.cpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/libs/geometry/test/algorithms/disjoint.cpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -21,6 +21,8 @@
#include <test_common/test_point.hpp>
+#include <algorithms/overlay/overlay_cases.hpp>
+
#include <algorithms/test_relate.hpp>
@@ -66,6 +68,10 @@
test_disjoint<ring, ring>("disjoint_simplex_rr", disjoint_simplex[0], disjoint_simplex[1], true);
test_disjoint<polygon, ring>("disjoint_simplex_pr", disjoint_simplex[0], disjoint_simplex[1], true);
+ test_disjoint<polygon, polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1], false);
+ test_disjoint<polygon, polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1], false);
+ test_disjoint<polygon, polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1], false);
+
// Testing touch
test_disjoint<polygon, polygon>("touch_simplex_pp", touch_simplex[0], touch_simplex[1], false);
Modified: trunk/libs/geometry/test/algorithms/intersection.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/intersection.cpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/libs/geometry/test/algorithms/intersection.cpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -214,6 +214,13 @@
test_one<Polygon, Polygon, Polygon>("ticket_8652", ticket_8652[0], ticket_8652[1],
1, 4, 0.0003, 0.00001);
+ test_one<Polygon, Polygon, Polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1],
+ 1, 5, 0.3843747, 0.00001);
+ test_one<Polygon, Polygon, Polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1],
+ 1, 5, 0.3734379, 0.00001);
+ test_one<Polygon, Polygon, Polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1],
+ 1, 5, 0.4689541, 0.00001);
+
test_one<Polygon, Polygon, Polygon>("buffer_mp1", buffer_mp1[0], buffer_mp1[1],
1, 31, 2.271707796);
Modified: trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -575,15 +575,23 @@
"POLYGON((2.76143527 1.093332171 , 2.076887131 1.822299719 , 4.263789177 3.875944376 , 4.948337555 3.146976948 , 2.76143527 1.093332171))"
};
-static std::string ticket_8180[2] =
+// Ticket 8310 https://svn.boost.org/trac/boost/ticket/8310
+// The problem was in disjoint, "point_on_border" on the smallest polygon
+// is not considered as "within" the other, though there are no further intersection points.
+static std::string ticket_8310a[2] =
{
- "POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371 ))",
- "POLYGON(( 1.000000000000000 0.384374707937241, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.384374737739563 ))"
+ "POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371, -2.559375047683716 -0.615625500679016 ))",
+ "POLYGON(( 1.000000000000000 0.384374707937241, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.384374737739563, 1.000000000000000 0.384374707937241 ))"
};
-static std::string ticket_8180b[2] =
+static std::string ticket_8310b[2] =
{
- "POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371 ))",
- "POLYGON(( 1 0.384374707937241, 1 1, 0 1, 0 0.384374737739563 ))"
+ "POLYGON(( -2.592187881469727 -0.626561701297760, -2.592187643051147 0.373438000679016, 7.907812595367432 0.373437851667404, 7.907812595367432 -0.626561224460602, -2.592187881469727 -0.626561701297760 ))",
+ "POLYGON(( 0.000000000000000 0.373437941074371, 1.000000000000000 0.373437792062759, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.373437941074371 ))"
+ };
+static std::string ticket_8310c[2] =
+ {
+ "POLYGON(( 5.204249382019043 3.531043529510498, 5.204247951507568 2.531045675277710, -5.295750617980957 2.531046152114868, -5.295751094818115 3.531045913696289, 5.204249382019043 3.531043529510498 ))",
+ "POLYGON(( 1.000000000000000 2.531045913696289, 1.000000000000000 3.000000000000000, 2.000000000000000 3.000000000000000, 2.000000000000000 2.531045913696289, 1.000000000000000 2.531045913696289 ))"
};
static std::string ticket_8254[2] =
Modified: trunk/libs/geometry/test/algorithms/point_on_surface.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/point_on_surface.cpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/libs/geometry/test/algorithms/point_on_surface.cpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -281,8 +281,9 @@
test_geometry<polygon>("ticket_17", ticket_17[0], 0, 0);
test_geometry<polygon>("ticket_5103", ticket_5103[0], 0, 0);
test_geometry<polygon>("ticket_7462", ticket_7462[0], 0, 0);
- test_geometry<polygon>("ticket_8180", ticket_8180[0], 0, 0);
- test_geometry<polygon>("ticket_8180b", ticket_8180b[0], 0, 0);
+ test_geometry<polygon>("ticket_8310a", ticket_8310a[0], 0, 0);
+ test_geometry<polygon>("ticket_8310b", ticket_8310b[0], 0, 0);
+ test_geometry<polygon>("ticket_8310c", ticket_8310c[0], 0, 0);
test_geometry<polygon>("ticket_8254", ticket_8254[0], 0, 0);
}
Modified: trunk/libs/geometry/test/algorithms/union.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/union.cpp Wed Nov 6 17:02:18 2013 (r86578)
+++ trunk/libs/geometry/test/algorithms/union.cpp 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013) (r86579)
@@ -265,6 +265,13 @@
test_one<Polygon, Polygon, Polygon>("ticket_5103", ticket_5103[0], ticket_5103[1],
1, 0, 25, 2515271327070.5);
+ test_one<Polygon, Polygon, Polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1],
+ 1, 0, 5, 10.5000019595);
+ test_one<Polygon, Polygon, Polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1],
+ 1, 0, 5, 10.5000019595);
+ test_one<Polygon, Polygon, Polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1],
+ 1, 0, 5, 10.5000019595);
+
test_one<Polygon, Polygon, Polygon>("buffer_rt_a", buffer_rt_a[0], buffer_rt_a[1],
1, 0, 265, 19.280667);