322 lines
11 KiB
C++
322 lines
11 KiB
C++
// Boost.Geometry (aka GGL, Generic Geometry Library)
|
|
//
|
|
// Copyright (c) 2012-2014 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 <geometry_test_common.hpp>
|
|
|
|
#include <boost/algorithm/string/trim.hpp>
|
|
#include <boost/assign/list_of.hpp>
|
|
|
|
#include <boost/geometry/geometries/point_xy.hpp>
|
|
#include <boost/geometry/algorithms/detail/get_left_turns.hpp>
|
|
|
|
#if defined(TEST_WITH_SVG)
|
|
# include <boost/geometry/io/svg/svg_mapper.hpp>
|
|
#endif
|
|
|
|
|
|
NOTE: this unit test is out of date.
|
|
get_left_turns is used by buffer and might be used in the future by solving self-tangencies in overlays.
|
|
it is currently being changed by buffer.
|
|
|
|
namespace bglt = boost::geometry::detail::left_turns;
|
|
|
|
#if defined(TEST_WITH_SVG)
|
|
template <typename Point>
|
|
inline Point further_than(Point const& p, Point const& origin, int mul, int div)
|
|
{
|
|
typedef Point vector_type;
|
|
|
|
vector_type v = p;
|
|
bg::subtract_point(v, origin);
|
|
|
|
bg::divide_value(v, div);
|
|
bg::multiply_value(v, mul);
|
|
Point result = origin;
|
|
bg::add_point(result, v);
|
|
return result;
|
|
}
|
|
|
|
inline std::string get_color(int index)
|
|
{
|
|
switch (index)
|
|
{
|
|
case 0 : return "rgb(0,192,0)";
|
|
case 1 : return "rgb(0,0,255)";
|
|
case 2 : return "rgb(255,0,0)";
|
|
case 3 : return "rgb(255,255,0)";
|
|
}
|
|
return "rgb(128,128,128)";
|
|
}
|
|
#endif
|
|
|
|
|
|
template <typename Point>
|
|
void test_one(std::string const& caseid,
|
|
Point const& p,
|
|
std::vector<bglt::turn_angle_info<Point> > const& angles,
|
|
std::string const& expected_sorted_indices,
|
|
std::string const& expected_left_indices)
|
|
{
|
|
typedef Point vector_type;
|
|
|
|
std::vector<bglt::angle_info<Point> > sorted;
|
|
for (typename std::vector<bglt::turn_angle_info<Point> >::const_iterator it =
|
|
angles.begin(); it != angles.end(); ++it)
|
|
{
|
|
for (int i = 0; i < 2; i++)
|
|
{
|
|
bglt::angle_info<Point> info(it->seg_id, i == 0, it->points[i]);
|
|
sorted.push_back(info);
|
|
}
|
|
}
|
|
|
|
// Sort on angle
|
|
std::sort(sorted.begin(), sorted.end(), bglt::angle_less<Point>(p));
|
|
|
|
// Block all turns on the right side of any turn
|
|
bglt::block_turns_on_right_sides(angles, sorted);
|
|
|
|
// Check the sorting
|
|
{
|
|
std::ostringstream out;
|
|
out << std::boolalpha;
|
|
for (typename std::vector<bglt::angle_info<Point> >::const_iterator it =
|
|
sorted.begin(); it != sorted.end(); ++it)
|
|
{
|
|
out << " " << it->seg_id.segment_index
|
|
<< "-" << it->incoming;
|
|
}
|
|
std::string detected = boost::trim_copy(out.str());
|
|
BOOST_CHECK_EQUAL(expected_sorted_indices, detected);
|
|
}
|
|
|
|
|
|
// Check outgoing lines
|
|
std::vector<bglt::left_turn> seg_ids;
|
|
bglt::get_left_turns(sorted, p, seg_ids);
|
|
{
|
|
std::ostringstream out;
|
|
out << std::boolalpha;
|
|
for (std::vector<bglt::left_turn>::const_iterator it =
|
|
seg_ids.begin(); it != seg_ids.end(); ++it)
|
|
{
|
|
out
|
|
<< " " << it->from.segment_index
|
|
<< "->" << it->to.segment_index
|
|
;
|
|
}
|
|
std::string detected = boost::trim_copy(out.str());
|
|
BOOST_CHECK_EQUAL(expected_left_indices, detected);
|
|
}
|
|
|
|
#if defined(TEST_WITH_SVG)
|
|
{
|
|
std::ostringstream filename;
|
|
filename << "get_left_turns_" << caseid
|
|
<< "_" << string_from_type<typename bg::coordinate_type<Point>::type>::name()
|
|
<< ".svg";
|
|
|
|
std::ofstream svg(filename.str().c_str());
|
|
|
|
bg::svg_mapper<Point> mapper(svg, 500, 500);
|
|
mapper.add(p);
|
|
for (typename std::vector<bglt::turn_angle_info<Point> >::const_iterator it =
|
|
angles.begin(); it != angles.end(); ++it)
|
|
{
|
|
// Add a point further then it->to_point, just for the mapping
|
|
for (int i = 0; i < 2; i++)
|
|
{
|
|
mapper.add(further_than(it->points[i], p, 12, 10));
|
|
}
|
|
}
|
|
|
|
int color_index = 0;
|
|
typedef bg::model::referring_segment<Point const> segment_type;
|
|
for (typename std::vector<bglt::turn_angle_info<Point> >::const_iterator it =
|
|
angles.begin(); it != angles.end(); ++it, color_index++)
|
|
{
|
|
for (int i = 0; i < 2; i++)
|
|
{
|
|
std::string style = "opacity:0.5;stroke-width:1;stroke:rgb(0,0,0);fill:" + get_color(color_index);
|
|
|
|
bool const incoming = i == 0;
|
|
Point const& pf = incoming ? it->points[i] : p;
|
|
Point const& pt = incoming ? p : it->points[i];
|
|
vector_type v = pt;
|
|
bg::subtract_point(v, pf);
|
|
|
|
bg::divide_value(v, 10.0);
|
|
|
|
// Generate perpendicular vector to right-side
|
|
vector_type perpendicular;
|
|
bg::set<0>(perpendicular, bg::get<1>(v));
|
|
bg::set<1>(perpendicular, -bg::get<0>(v));
|
|
|
|
bg::model::ring<Point> ring;
|
|
ring.push_back(pf);
|
|
ring.push_back(pt);
|
|
|
|
// Extra point at 9/10
|
|
{
|
|
Point pe = pt;
|
|
bg::add_point(pe, perpendicular);
|
|
ring.push_back(pe);
|
|
}
|
|
{
|
|
Point pe = pf;
|
|
bg::add_point(pe, perpendicular);
|
|
ring.push_back(pe);
|
|
}
|
|
ring.push_back(pf);
|
|
|
|
mapper.map(ring, style);
|
|
|
|
segment_type s(pf, pt);
|
|
mapper.map(s, "opacity:0.9;stroke-width:4;stroke:rgb(0,0,0);");
|
|
}
|
|
}
|
|
|
|
// Output angles for left-turns
|
|
for (std::vector<bglt::left_turn>::const_iterator ltit =
|
|
seg_ids.begin(); ltit != seg_ids.end(); ++ltit)
|
|
{
|
|
for (typename std::vector<bglt::angle_info<Point> >::const_iterator sit =
|
|
sorted.begin(); sit != sorted.end(); ++sit, color_index++)
|
|
{
|
|
Point pf, pt;
|
|
int factor = 0;
|
|
if (sit->seg_id == ltit->from && sit->incoming)
|
|
{
|
|
pf = sit->point;
|
|
pt = p;
|
|
factor = -1; // left side
|
|
}
|
|
else if (sit->seg_id == ltit->to && ! sit->incoming)
|
|
{
|
|
pf = p;
|
|
pt = sit->point;
|
|
factor = -1; // left side
|
|
}
|
|
if (factor != 0)
|
|
{
|
|
vector_type v = pt;
|
|
bg::subtract_point(v, pf);
|
|
bg::divide_value(v, 10.0);
|
|
|
|
// Generate perpendicular vector to right-side
|
|
vector_type perpendicular;
|
|
bg::set<0>(perpendicular, factor * bg::get<1>(v));
|
|
bg::set<1>(perpendicular, -factor * bg::get<0>(v));
|
|
|
|
bg::add_point(pf, v);
|
|
bg::subtract_point(pt, v);
|
|
|
|
bg::add_point(pf, perpendicular);
|
|
bg::add_point(pt, perpendicular);
|
|
|
|
segment_type s(pf, pt);
|
|
mapper.map(s, "opacity:0.9;stroke-width:4;stroke:rgb(255,0,0);");
|
|
}
|
|
}
|
|
}
|
|
|
|
// Output texts with info about sorted/blocked
|
|
int index = 0;
|
|
for (typename std::vector<bglt::angle_info<Point> >::const_iterator it =
|
|
sorted.begin(); it != sorted.end(); ++it, ++index)
|
|
{
|
|
std::ostringstream out;
|
|
out << std::boolalpha;
|
|
out << " seg:" << it->seg_id.segment_index
|
|
<< " " << (it->incoming ? "in" : "out")
|
|
<< " idx:" << index
|
|
<< (it->blocked ? " blocked" : "")
|
|
;
|
|
mapper.text(further_than(it->point, p, 11, 10), out.str(), "fill:rgb(0,0,0);font-family='Verdana'");
|
|
}
|
|
|
|
mapper.map(p, "fill:rgb(255,0,0)");
|
|
|
|
}
|
|
|
|
#endif
|
|
|
|
}
|
|
|
|
|
|
template <typename P>
|
|
void test_all()
|
|
{
|
|
using bglt::turn_angle_info;
|
|
|
|
test_one<P>("cross",
|
|
bg::make<P>(50, 50), // ip
|
|
boost::assign::list_of
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(100, 100), bg::make<P>(0, 0)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 0), bg::make<P>(0, 100)))
|
|
, "1-true 2-true 1-false 2-false"
|
|
, "2->1"
|
|
);
|
|
|
|
test_one<P>("occupied",
|
|
bg::make<P>(50, 50), // ip
|
|
boost::assign::list_of
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(100, 100), bg::make<P>(0, 0)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 0), bg::make<P>(0, 100)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(0, 30), bg::make<P>(100, 70)))
|
|
, "1-true 3-false 2-true 1-false 3-true 2-false"
|
|
, ""
|
|
);
|
|
|
|
test_one<P>("uu",
|
|
bg::make<P>(50, 50), // ip
|
|
boost::assign::list_of
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(0, 0), bg::make<P>(100, 0)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 100), bg::make<P>(0, 100)))
|
|
, "2-true 1-false 1-true 2-false"
|
|
, "2->1 1->2"
|
|
);
|
|
|
|
test_one<P>("uu2",
|
|
bg::make<P>(50, 50), // ip
|
|
boost::assign::list_of
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(0, 0), bg::make<P>(100, 0)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 100), bg::make<P>(0, 100)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(0, 50), bg::make<P>(100, 50)))
|
|
, "2-true 3-false 1-false 1-true 3-true 2-false"
|
|
, "2->3 3->2"
|
|
);
|
|
|
|
test_one<P>("uu3",
|
|
bg::make<P>(50, 50), // ip
|
|
boost::assign::list_of
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(0, 0), bg::make<P>(100, 0)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 100), bg::make<P>(0, 100)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(50, 0), bg::make<P>(50, 100)))
|
|
, "3-false 2-true 1-false 3-true 1-true 2-false"
|
|
, "1->2"
|
|
);
|
|
|
|
test_one<P>("longer",
|
|
bg::make<P>(50, 50), // ip
|
|
boost::assign::list_of
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(100, 100), bg::make<P>(0, 0)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 0), bg::make<P>(0, 100)))
|
|
(turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(90, 10), bg::make<P>(10, 10)))
|
|
, "1-true 2-true 3-true 1-false 3-false 2-false"
|
|
, "3->1"
|
|
);
|
|
}
|
|
|
|
int test_main( int , char* [] )
|
|
{
|
|
test_all<bg::model::d2::point_xy<int> >();
|
|
|
|
return 0;
|
|
}
|