|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r59806 - in sandbox/geometry: boost/geometry/algorithms/detail/overlay boost/geometry/algorithms/overlay libs/geometry/doc/testcases libs/geometry/test/algorithms/overlay
From: barend.gehrels_at_[hidden]
Date: 2010-02-21 07:38:46
Author: barendgehrels
Date: 2010-02-21 07:38:45 EST (Sun, 21 Feb 2010)
New Revision: 59806
URL: http://svn.boost.org/trac/boost/changeset/59806
Log:
Moved rejected to the operation level, now state of visited
This solves cases 56/57. 55 still to be solved
Binary files modified:
sandbox/geometry/libs/geometry/doc/testcases/overlay_cases.ppt
Text files modified:
sandbox/geometry/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp | 11 +++++++++++
sandbox/geometry/boost/geometry/algorithms/detail/overlay/turn_info.hpp | 2 --
sandbox/geometry/boost/geometry/algorithms/detail/overlay/visit_info.hpp | 14 +++++++++++++-
sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp | 21 ++++++++++++---------
sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay_cases.hpp | 8 +++++---
sandbox/geometry/libs/geometry/test/algorithms/overlay/traverse.cpp | 34 ++++++++++++++++++++++++++--------
6 files changed, 67 insertions(+), 23 deletions(-)
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp 2010-02-21 07:38:45 EST (Sun, 21 Feb 2010)
@@ -44,6 +44,17 @@
}
}
+inline char visited_char(detail::overlay::visit_info const& v)
+{
+ if (v.rejected()) return 'R';
+ if (v.started()) return 's';
+ if (v.visited()) return 'v';
+ if (v.none()) return '-';
+ if (v.finished()) return 'f';
+ return '?';
+}
+
+
}} // namespace boost::geometry
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-02-21 07:38:45 EST (Sun, 21 Feb 2010)
@@ -86,14 +86,12 @@
Point point;
method_type method;
bool ignore;
- bool rejected;
Container operations;
turn_info()
: method(method_none)
, ignore(false)
- , rejected(false)
{}
};
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-02-21 07:38:45 EST (Sun, 21 Feb 2010)
@@ -30,6 +30,7 @@
static const int STARTED = 1;
static const int VISITED = 2;
static const int FINISHED = 3;
+ static const int REJECTED = 4;
int visit_code;
@@ -38,14 +39,25 @@
: visit_code(0)
{}
- inline void set_none() { visit_code = NONE; }
inline void set_visited() { visit_code = VISITED; }
inline void set_started() { visit_code = STARTED; }
inline void set_finished() { visit_code = FINISHED; }
+ inline void set_rejected() { visit_code = REJECTED; }
inline bool none() const { return visit_code == NONE; }
inline bool visited() const { return visit_code == VISITED; }
inline bool started() const { return visit_code == STARTED; }
+ inline bool finished() const { return visit_code == FINISHED; }
+ inline bool rejected() const { return visit_code == REJECTED; }
+
+ inline void clear()
+ {
+ if (! rejected())
+ {
+ visit_code = NONE;
+ }
+ }
+
#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
friend std::ostream& operator<<(std::ostream &os, visit_info const& v)
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/traverse.hpp 2010-02-21 07:38:45 EST (Sun, 21 Feb 2010)
@@ -53,7 +53,7 @@
op_it != boost::end(it->operations);
++op_it)
{
- op_it->visited.set_none();
+ op_it->visited.clear();
}
}
}
@@ -185,12 +185,14 @@
<
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, typename boost::range_value<Turns>::type& turn,
+ Turns& turns, Operation& operation,
+
#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
std::string const& reason,
Geometry1 const& geometry1,
@@ -209,8 +211,8 @@
ring.clear();
// Reject this as a starting point
- turn.rejected = true;
-
+ operation.visited.set_rejected();
+
// And clear all visit info
clear_visit_info(turns);
@@ -266,10 +268,11 @@
if (! it->ignore)
{
for (turn_operation_iterator_type iit = boost::begin(it->operations);
- ! fail && ! it->rejected && iit != boost::end(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)
)
@@ -297,7 +300,7 @@
{
detail::overlay::backtrack(
size_at_start, fail,
- rings, current_output, turns, *it,
+ rings, current_output, turns, *iit,
"Dead end at start",
geometry1, geometry2);
}
@@ -316,7 +319,7 @@
// This makes it suspicious for endless loops
detail::overlay::backtrack(
size_at_start, fail,
- rings, current_output, turns, *it,
+ rings, current_output, turns, *iit,
"Visit again",
geometry1, geometry2);
}
@@ -350,7 +353,7 @@
// Might occur in polygons with spikes
detail::overlay::backtrack(
size_at_start, fail,
- rings, current_output, turns, *it,
+ rings, current_output, turns, *iit,
"Dead end",
geometry1, geometry2);
}
@@ -361,7 +364,7 @@
// than intersection points.
detail::overlay::backtrack(
size_at_start, fail,
- rings, current_output, turns, *it,
+ rings, current_output, turns, *iit,
"Endless loop",
geometry1, geometry2);
}
Modified: sandbox/geometry/libs/geometry/doc/testcases/overlay_cases.ppt
==============================================================================
Binary files. No diff available.
Modified: sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay_cases.hpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay_cases.hpp (original)
+++ sandbox/geometry/libs/geometry/test/algorithms/overlay/overlay_cases.hpp 2010-02-21 07:38:45 EST (Sun, 21 Feb 2010)
@@ -249,14 +249,16 @@
static std::string case_56[2] = {
"POLYGON((0 0,0 1,2 3,3 0,4 2,5 0,0 0))",
- "POLYGON((0 1,0 4,5 4,5 0,3 0,4 1,4 3,2 3,2 1,3 0,0 0))"
+ //"POLYGON((0 -1,0 1,2 3,3 0,4 2,5 -1,0 -1))",
+ //"POLYGON((0 1,0 4,5 4,5 0,3 0,4 1,4 3,2 3,2 1,3 0,0 0))"
+ "POLYGON((1 0,1 4,5 4,5 0,3 0,4 1,4 3,2 3,2 1,3 0,1 0))"
};
static std::string case_57[2] = {
- //case_56[0],
+ case_56[0],
//"POLYGON((0 2,4 5,5 1,0 2))"
//"POLYGON((0 -1,0 1,2 3,3 0,4 2,5 -1,0 -1))",
- "POLYGON((0 0,0 1,2 3,3 0,4 2,6 0,0 0))",
+ //"POLYGON((0 0,0 1,2 3,3 0,4 2,6 0,0 0))",
"POLYGON((0 0,4 5,5 0,0 0))"
};
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-02-21 07:38:45 EST (Sun, 21 Feb 2010)
@@ -156,7 +156,7 @@
typedef typename bg::coordinate_type<G1>::type coordinate_type;
// Simple map to avoid two texts at same place (note that can still overlap!)
- std::map<std::pair<coordinate_type, coordinate_type>, int> offsets;
+ std::map<std::pair<int, int>, int> offsets;
int index = 0;
int const lineheight = 10;
int const margin = 5;
@@ -168,8 +168,12 @@
{
// Map characteristics
- std::pair<coordinate_type, coordinate_type> p
- = std::make_pair(bg::get<0>(turn.point), bg::get<1>(turn.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<1>(turn.point))
+ );
std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:8px";
{
@@ -225,6 +229,18 @@
int offset = offsets[p];
mapper.text(turn.point, out.str(), style, margin, offset);
}
+
+ {
+ std::ostringstream out;
+ out << std::setprecision(3)
+ << "vis: " << bg::visited_char(turn.operations[0].visited)
+ << " / " << bg::visited_char(turn.operations[1].visited);
+
+ offsets[p] += lineheight;
+ int offset = offsets[p];
+ mapper.text(turn.point, out.str(), style, margin, offset);
+ }
+
}
index++;
}
@@ -273,6 +289,8 @@
return;
*/
+ //test_overlay<polygon, polygon, test_traverse<operation_intersection>, Tuple>("57", boost::make_tuple(2, 1.489899), case_57[0], case_57[1]);
+ //return;
// 1-6
@@ -352,8 +370,8 @@
// 55-60
test_overlay<polygon, polygon, test_traverse<operation_intersection>, Tuple>("55", boost::make_tuple(1, 2), case_55[0], case_55[1]);
- test_overlay<polygon, polygon, test_traverse<operation_intersection>, Tuple>("56", boost::make_tuple(2, 6), case_56[0], case_56[1]);
- test_overlay<polygon, polygon, test_traverse<operation_intersection>, Tuple>("57", boost::make_tuple(2, 1.489899), case_57[0], case_57[1]);
+ test_overlay<polygon, polygon, test_traverse<operation_intersection>, Tuple>("56", boost::make_tuple(2, 4.5), case_56[0], case_56[1]);
+ test_overlay<polygon, polygon, test_traverse<operation_intersection>, Tuple>("57", boost::make_tuple(2, 5.9705882), case_57[0], case_57[1]);
// other
@@ -458,9 +476,9 @@
// 55-60
// 55 is going wrong!
// TODO: implement "node" behaviour which merges nodes
- test_overlay<polygon, polygon, test_traverse<operation_union>, Tuple>("55", boost::make_tuple(3, 18), case_55[0], case_55[1]);
- test_overlay<polygon, polygon, test_traverse<operation_union>, Tuple>("56", boost::make_tuple(3, 18), case_56[0], case_56[1]);
- test_overlay<polygon, polygon, test_traverse<operation_union>, Tuple>("57", boost::make_tuple(2, 15.510101), case_57[0], case_57[1]);
+ //test_overlay<polygon, polygon, test_traverse<operation_union>, Tuple>("55", boost::make_tuple(3, 18), case_55[0], case_55[1]);
+ test_overlay<polygon, polygon, test_traverse<operation_union>, Tuple>("56", boost::make_tuple(2, 14), case_56[0], case_56[1]);
+ test_overlay<polygon, polygon, test_traverse<operation_union>, Tuple>("57", boost::make_tuple(1, 14.029412), case_57[0], case_57[1]);
// other
test_overlay<polygon, polygon, test_traverse<operation_union>, Tuple>("collinear_overlaps",
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk