[ceph.git] / ceph / src / boost / libs / geometry / test / algorithms / overlay / overlay.cpp

// Boost.Geometry (aka GGL, Generic Geometry Library)
// Unit Test

// Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.

// This file was modified by Oracle on 2017.
// Modifications copyright (c) 2017, Oracle and/or its affiliates.
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle

// 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 <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>

#include <boost/type_traits/is_same.hpp>

#if defined(TEST_WITH_SVG)
#  include <boost/geometry/io/svg/svg_mapper.hpp>
#endif

#include <geometry_test_common.hpp>


#include <boost/geometry.hpp>
#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
#include <boost/geometry/geometries/geometries.hpp>

//#include <boost/geometry/extensions/algorithms/inverse.hpp>

#if defined(TEST_WITH_SVG)
#  include <boost/geometry/io/svg/svg_mapper.hpp>
#endif

#include "multi_overlay_cases.hpp"


#if defined(TEST_WITH_SVG)
template <typename Mapper>
struct map_visitor
{
    map_visitor(Mapper& mapper)
        : m_mapper(mapper)
        , m_traverse_seq(0)
        , m_do_output(true)
    {}

    void print(char const* header)
    {}

    template <typename Turns>
    void print(char const* header, Turns const& turns, int turn_index)
    {
        std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
        stream(turns, turns[turn_index], turns[turn_index].operations[0], header, style);
    }

    template <typename Turns>
    void print(char const* header, Turns const& turns, int turn_index, int op_index)
    {
        std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
        stream(turns, turns[turn_index], turns[turn_index].operations[op_index], header, style);
    }

    template <typename Turns>
    void visit_turns(int phase, Turns const& turns)
    {
        typedef typename boost::range_value<Turns>::type turn_type;
        int index = 0;
        BOOST_FOREACH(turn_type const& turn, turns)
        {
            switch (phase)
            {
                case 1 :
                    m_mapper.map(turn.point, "fill:rgb(255,128,0);"
                            "stroke:rgb(0,0,0);stroke-width:1", 3);
                    break;
                case 11 :
                    m_mapper.map(turn.point, "fill:rgb(92,255,0);" // Greenish
                            "stroke:rgb(0,0,0);stroke-width:1", 3);
                    break;
                case 21 :
                    m_mapper.map(turn.point, "fill:rgb(0,128,255);" // Blueish
                            "stroke:rgb(0,0,0);stroke-width:1", 3);
                    break;
                case 3 :
                    label_turn(index, turn);
                    break;
            }
            index++;
        }
    }

    template <typename Turns, typename Turn, typename Operation>
    std::string stream_turn_index(Turns const& turns, Turn const& turn, Operation const& op)
    {
        std::ostringstream out;

        if (turn.cluster_id >= 0)
        {
            out << "cl=" << turn.cluster_id << " ";
        }

        // Because turn index is unknown here, and still useful for debugging,
        std::size_t index = 0;
        for (typename Turns::const_iterator it = turns.begin();
           it != turns.end(); ++it, ++index)
        {
          Turn const& t = *it;
          if (&t == &turn)
          {
              out << index;
              break;
          }
        }

        if (&op == &turn.operations[0]) { out << "[0]"; }
        if (&op == &turn.operations[1]) { out << "[1]"; }
        return out.str();
    }

    template <typename Clusters, typename Turns>
    void visit_clusters(Clusters const& clusters, Turns const& turns)
    {
        typedef typename boost::range_value<Turns>::type turn_type;
        int index = 0;
        BOOST_FOREACH(turn_type const& turn, turns)
        {
            if (turn.cluster_id >= 0)
            {
                std::cout << " TURN: " << index << "  part of cluster "  << turn.cluster_id << std::endl;
            }
            index++;
        }

        for (typename Clusters::const_iterator it = clusters.begin(); it != clusters.end(); ++it)
        {
            std::cout << " CLUSTER " << it->first << ": ";
            for (typename std::set<bg::signed_size_type>::const_iterator sit
                 = it->second.turn_indices.begin();
                 sit != it->second.turn_indices.end(); ++sit)
            {
                std::cout << " "  << *sit;
            }
            std::cout << std::endl;
        }

        std::cout << std::endl;

    }

    template <typename Turns, typename Turn, typename Operation>
    void visit_traverse(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header)
    {
        typedef typename boost::range_value<Turns>::type turn_type;

        if (! m_do_output)
        {
            return;
        }

        std::cout << "Visit turn " << stream_turn_index(turns, turn, op)
                  << " " << bg::operation_char(turn.operations[0].operation)
                    << bg::operation_char(turn.operations[1].operation)
                << " (" << bg::operation_char(op.operation) << ")"
                << " "  << header << std::endl;

        // Uncomment for more detailed debug info in SVG on traversal
        std::string style
                = header == "Visit" ? "fill:rgb(80,80,80)" : "fill:rgb(0,0,0)";

        style += ";font-family:Arial;font-size:6px";

        stream(turns, turn, op, header.substr(0, 1), style);
    }

    template <typename Turns, typename Turn, typename Operation>
    void visit_traverse_reject(Turns const& turns, Turn const& turn, Operation const& op,
                               bg::detail::overlay::traverse_error_type error)
    {
        if (! m_do_output)
        {
            return;
        }
        std::cout << "Reject turn " << stream_turn_index(turns, turn, op)
                  << bg::operation_char(turn.operations[0].operation)
                    << bg::operation_char(turn.operations[1].operation)
                << " (" << bg::operation_char(op.operation) << ")"
                << " "  << bg::detail::overlay::traverse_error_string(error) << std::endl;
        //return;

        std::string style =  "fill:rgb(255,0,0);font-family:Arial;font-size:7px";
        stream(turns, turn, op, bg::detail::overlay::traverse_error_string(error), style);

        m_do_output = false;
    }

    template <typename Turns, typename Turn, typename Operation>
    void visit_traverse_select_turn_from_cluster(Turns const& turns, Turn const& turn, Operation const& op)
    {
        std::cout << "Visit turn from cluster " << stream_turn_index(turns, turn, op)
                  << " " << bg::operation_char(turn.operations[0].operation)
                    << bg::operation_char(turn.operations[1].operation)
                << " (" << bg::operation_char(op.operation) << ")"
                << std::endl;
        return;
    }

    template <typename Turns, typename Turn, typename Operation>
    void stream(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header, const std::string& style)
    {
        std::ostringstream out;
        out << m_traverse_seq++ << " " << header
            << " " << stream_turn_index(turns, turn, op);

        out << " " << bg::visited_char(op.visited);

        add_text(turn, out.str(), style);
    }

    template <typename Turn>
    bool label_operation(Turn const& turn, int index, std::ostream& os)
    {
        os << bg::operation_char(turn.operations[index].operation);
        bool result = false;
        if (! turn.discarded)
        {
            if (turn.operations[index].enriched.next_ip_index != -1)
            {
                os << "->" << turn.operations[index].enriched.next_ip_index;
                if (turn.operations[index].enriched.next_ip_index != -1)
                {
                    result = true;
                }
            }
            else
            {
                os << "->"  << turn.operations[index].enriched.travels_to_ip_index;
                if (turn.operations[index].enriched.travels_to_ip_index != -1)
                {
                    result = true;
                }
            }

            os << " {" << turn.operations[index].enriched.region_id
               << (turn.operations[index].enriched.isolated ? " ISO" : "")
               << "}";

            if (! turn.operations[index].enriched.startable)
            {
                os << "$";
            }
        }

        return result;
    }

    template <typename Turn>
    void label_turn(int index, Turn const& turn)
    {
        std::ostringstream out;
        out << index << " ";
        if (turn.cluster_id != -1)
        {
            out << " c=" << turn.cluster_id << " ";
        }
        bool lab1 = label_operation(turn, 0, out);
        out << " / ";
        bool lab2 = label_operation(turn, 1, out);
        if (turn.switch_source)
        {
            out << "#";
        }
        if (turn.discarded)
        {
            out << "!";
        }
        if (turn.has_colocated_both)
        {
            out << "+";
        }
        bool const self_turn = bg::detail::overlay::is_self_turn<bg::overlay_union>(turn);
        if (self_turn)
        {
            out << "@";
        }

        std::string font8 = "font-family:Arial;font-size:6px";
        std::string font6 = "font-family:Arial;font-size:4px";
        std::string style =  "fill:rgb(0,0,255);" + font8;
        if (self_turn)
        {
            if (turn.discarded)
            {
                style =  "fill:rgb(128,28,128);" + font6;
            }
            else
            {
                style =  "fill:rgb(255,0,255);" + font8;
            }
        }
        else if (turn.discarded)
        {
            style =  "fill:rgb(92,92,92);" + font6;
        }
        else if (turn.cluster_id != -1)
        {
            style =  "fill:rgb(0,0,255);" + font8;
        }
        else if (! lab1 || ! lab2)
        {
            style =  "fill:rgb(0,0,255);" + font6;
        }

        add_text(turn, out.str(), style);
    }

    template <typename Turn>
    void add_text(Turn const& turn, std::string const& text, std::string const& style)
    {
        int const margin = 5;
        int const lineheight = 6;
        double const half = 0.5;
        double const ten = 10;

        // Map characteristics
        // Create a rounded off point
        std::pair<int, int> p
            = std::make_pair(
                boost::numeric_cast<int>(half
                    + ten * bg::get<0>(turn.point)),
                boost::numeric_cast<int>(half
                    + ten * bg::get<1>(turn.point))
                );
        m_mapper.text(turn.point, text, style, margin, m_offsets[p], lineheight);
        m_offsets[p] += lineheight;
    }


    Mapper& m_mapper;
    std::map<std::pair<int, int>, int> m_offsets;
    int m_traverse_seq;
    bool m_do_output;

};
#endif

template <typename Geometry, bg::overlay_type OverlayType>
void test_overlay(std::string const& caseid,
        std::string const& wkt1, std::string const& wkt2,
        double expected_area,
        std::size_t expected_clip_count,
        std::size_t expected_hole_count)
{
    Geometry g1;
    bg::read_wkt(wkt1, g1);

    Geometry g2;
    bg::read_wkt(wkt2, g2);

    // Reverse if necessary
    bg::correct(g1);
    bg::correct(g2);

#if defined(TEST_WITH_SVG)
    bool const ccw = bg::point_order<Geometry>::value == bg::counterclockwise;
    bool const open = bg::closure<Geometry>::value == bg::open;

    std::ostringstream filename;
    filename << "overlay"
        << "_" << caseid
        << "_" << string_from_type<typename bg::coordinate_type<Geometry>::type>::name()
        << (ccw ? "_ccw" : "")
        << (open ? "_open" : "")
#ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS
        << "_self"
#endif
#if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
        << "_no_rob"
#endif
        << ".svg";

    std::ofstream svg(filename.str().c_str());

    typedef bg::svg_mapper<typename bg::point_type<Geometry>::type> svg_mapper;

    svg_mapper mapper(svg, 500, 500);
    mapper.add(g1);
    mapper.add(g2);

    // Input shapes in green (src=0) / blue (src=1)
    mapper.map(g1, "fill-opacity:0.5;fill:rgb(153,204,0);"
            "stroke:rgb(153,204,0);stroke-width:3");
    mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
            "stroke:rgb(51,51,153);stroke-width:3");
#endif


    typedef typename boost::range_value<Geometry>::type geometry_out;
    typedef bg::detail::overlay::overlay
        <
            Geometry, Geometry,
            bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
            OverlayType == bg::overlay_difference
            ? ! bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value
            : bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
            bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
            geometry_out,
            OverlayType
        > overlay;

    typedef typename bg::strategy::intersection::services::default_strategy
        <
            typename bg::cs_tag<Geometry>::type
        >::type strategy_type;

    strategy_type strategy;

    typedef typename bg::rescale_overlay_policy_type
    <
        Geometry,
        Geometry
    >::type rescale_policy_type;

    rescale_policy_type robust_policy
        = bg::get_rescale_policy<rescale_policy_type>(g1, g2);

#if defined(TEST_WITH_SVG)
    map_visitor<svg_mapper> visitor(mapper);
#else
    bg::detail::overlay::overlay_null_visitor visitor;
#endif

    Geometry result;
    overlay::apply(g1, g2, robust_policy, std::back_inserter(result),
                   strategy, visitor);

    BOOST_CHECK_CLOSE(bg::area(result), expected_area, 0.001);
    BOOST_CHECK_MESSAGE((bg::num_interior_rings(result) == expected_hole_count),
                        caseid
                        << " hole count: detected: " << bg::num_interior_rings(result)
                        << " expected: "  << expected_hole_count);
    BOOST_CHECK_MESSAGE((result.size() == expected_clip_count),
                        caseid
                        << " clip count: detected: " << result.size()
                        << " expected: "  << expected_clip_count);

#if defined(TEST_WITH_SVG)
    mapper.map(result, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
                        "stroke:rgb(255,0,255);stroke-width:8");

#endif
}

#define TEST_INTERSECTION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
    ( #caseid "_int", caseid[0], caseid[1], area, clips, holes)
#define TEST_UNION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
    ( #caseid "_union", caseid[0], caseid[1], area, clips, holes)
#define TEST_DIFFERENCE_A(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
    ( #caseid "_diff_a", caseid[0], caseid[1], area, clips, holes)
#define TEST_DIFFERENCE_B(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
    ( #caseid "_diff_b", caseid[1], caseid[0], area, clips, holes)

#define TEST_INTERSECTION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
    ( #caseid "_int_" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)
#define TEST_UNION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
    ( #caseid "_union" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)

template <typename T, bool Clockwise>
void test_all()
{
    typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
    typedef bg::model::polygon<point_type, Clockwise> polygon;
    typedef bg::model::multi_polygon<polygon> multi_polygon;

    TEST_UNION(case_multi_simplex, 14.58, 1, 0);
    TEST_INTERSECTION(case_multi_simplex, 6.42, 2, 0);

    TEST_DIFFERENCE_A(case_multi_simplex, 5.58, 5, 0);
    TEST_DIFFERENCE_B(case_multi_simplex, 2.58, 4, 0);

    // Contains 5 clusters, needing immediate selection of next turn
    TEST_UNION_WITH(case_58_multi, 0, 3, 19.8333333, 2, 0);

    // Contains many clusters, needing to exclude u/u turns
    TEST_UNION(case_recursive_boxes_3, 56.5, 17, 6);

    // Contains 4 clusters, one of which having 4 turns
    TEST_UNION(case_recursive_boxes_7, 7.0, 2, 0);

    // Contains 5 clusters, needing immediate selection of next turn
    TEST_UNION(case_89_multi, 6.0, 1, 0);

    // Needs ux/next_turn_index==-1 to be filtered out
    TEST_INTERSECTION(case_77_multi, 9.0, 5, 0);
    TEST_UNION(case_101_multi, 22.25, 1, 3);
    TEST_INTERSECTION(case_101_multi, 4.75, 4, 0);

    TEST_INTERSECTION(case_recursive_boxes_11, 1.0, 2, 0);
    TEST_INTERSECTION(case_recursive_boxes_30, 6.0, 4, 0);

    TEST_UNION(case_recursive_boxes_4, 96.75, 1, 2);
    TEST_INTERSECTION_WITH(case_58_multi, 2, 6, 13.25, 1, 1);
    TEST_INTERSECTION_WITH(case_72_multi, 1, 2, 6.15, 3, 1);
    TEST_UNION(case_recursive_boxes_12, 6.0, 6, 0);
    TEST_UNION(case_recursive_boxes_13, 10.25, 3, 0);


//    std::cout
//        << "    \""
//        << bg::inverse<multi_polygon>(case_65_multi[0], 1.0)
//        << "\"" << std::endl;
}

int test_main(int, char* [])
{
    test_all<double, true>();
//    test_all<double, false>();
    return 0;
 }
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2	// Unit Test
	3
	4	// Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
	5
b32b8144 FG	6	// This file was modified by Oracle on 2017.
	7	// Modifications copyright (c) 2017, Oracle and/or its affiliates.
	8	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	9
7c673cae FG	10	// Use, modification and distribution is subject to the Boost Software License,
	11	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	12	// http://www.boost.org/LICENSE_1_0.txt)
	13
	14
	15	#include <iostream>
	16	#include <iomanip>
	17	#include <fstream>
	18	#include <sstream>
	19	#include <string>
	20
	21	#include <boost/type_traits/is_same.hpp>
	22
	23	#if defined(TEST_WITH_SVG)
	24	# include <boost/geometry/io/svg/svg_mapper.hpp>
	25	#endif
	26
	27	#include <geometry_test_common.hpp>
	28
	29
	30	#include <boost/geometry.hpp>
	31	#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
	32	#include <boost/geometry/geometries/geometries.hpp>
	33
	34	//#include <boost/geometry/extensions/algorithms/inverse.hpp>
	35
	36	#if defined(TEST_WITH_SVG)
	37	# include <boost/geometry/io/svg/svg_mapper.hpp>
	38	#endif
	39
	40	#include "multi_overlay_cases.hpp"
	41
	42
	43	#if defined(TEST_WITH_SVG)
	44	template <typename Mapper>
	45	struct map_visitor
	46	{
	47	map_visitor(Mapper& mapper)
	48	: m_mapper(mapper)
	49	, m_traverse_seq(0)
	50	, m_do_output(true)
	51	{}
	52
	53	void print(char const* header)
	54	{}
	55
	56	template <typename Turns>
	57	void print(char const* header, Turns const& turns, int turn_index)
	58	{
	59	std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
	60	stream(turns, turns[turn_index], turns[turn_index].operations[0], header, style);
	61	}
	62
	63	template <typename Turns>
	64	void print(char const* header, Turns const& turns, int turn_index, int op_index)
	65	{
	66	std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
	67	stream(turns, turns[turn_index], turns[turn_index].operations[op_index], header, style);
	68	}
	69
	70	template <typename Turns>
	71	void visit_turns(int phase, Turns const& turns)
	72	{
	73	typedef typename boost::range_value<Turns>::type turn_type;
74	int index = 0;
75	BOOST_FOREACH(turn_type const& turn, turns)
76	{
77	switch (phase)
78	{
79	case 1 :
80	m_mapper.map(turn.point, "fill:rgb(255,128,0);"
81	"stroke:rgb(0,0,0);stroke-width:1", 3);
82	break;
b32b8144 FG	83	case 11 :
	84	m_mapper.map(turn.point, "fill:rgb(92,255,0);" // Greenish
	85	"stroke:rgb(0,0,0);stroke-width:1", 3);
	86	break;
	87	case 21 :
	88	m_mapper.map(turn.point, "fill:rgb(0,128,255);" // Blueish
	89	"stroke:rgb(0,0,0);stroke-width:1", 3);
	90	break;
	91	case 3 :
7c673cae FG	92	label_turn(index, turn);
	93	break;
	94	}
	95	index++;
	96	}
	97	}
	98
	99	template <typename Turns, typename Turn, typename Operation>
	100	std::string stream_turn_index(Turns const& turns, Turn const& turn, Operation const& op)
	101	{
	102	std::ostringstream out;
	103
	104	if (turn.cluster_id >= 0)
	105	{
	106	out << "cl=" << turn.cluster_id << " ";
	107	}
	108
	109	// Because turn index is unknown here, and still useful for debugging,
	110	std::size_t index = 0;
	111	for (typename Turns::const_iterator it = turns.begin();
	112	it != turns.end(); ++it, ++index)
	113	{
	114	Turn const& t = *it;
	115	if (&t == &turn)
	116	{
	117	out << index;
	118	break;
	119	}
	120	}
	121
	122	if (&op == &turn.operations[0]) { out << "[0]"; }
	123	if (&op == &turn.operations[1]) { out << "[1]"; }
	124	return out.str();
	125	}
	126
	127	template <typename Clusters, typename Turns>
	128	void visit_clusters(Clusters const& clusters, Turns const& turns)
	129	{
	130	typedef typename boost::range_value<Turns>::type turn_type;
	131	int index = 0;
	132	BOOST_FOREACH(turn_type const& turn, turns)
	133	{
	134	if (turn.cluster_id >= 0)
	135	{
	136	std::cout << " TURN: " << index << " part of cluster " << turn.cluster_id << std::endl;
	137	}
	138	index++;
	139	}
	140
	141	for (typename Clusters::const_iterator it = clusters.begin(); it != clusters.end(); ++it)
	142	{
	143	std::cout << " CLUSTER " << it->first << ": ";
	144	for (typename std::set<bg::signed_size_type>::const_iterator sit
	145	= it->second.turn_indices.begin();
	146	sit != it->second.turn_indices.end(); ++sit)
	147	{
	148	std::cout << " " << *sit;
	149	}
	150	std::cout << std::endl;
	151	}
	152
	153	std::cout << std::endl;
	154
	155	}
156
157	template <typename Turns, typename Turn, typename Operation>
158	void visit_traverse(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header)
159	{
160	typedef typename boost::range_value<Turns>::type turn_type;
161
162	if (! m_do_output)
163	{
164	return;
165	}
166
167	std::cout << "Visit turn " << stream_turn_index(turns, turn, op)
168	<< " " << bg::operation_char(turn.operations[0].operation)
169	<< bg::operation_char(turn.operations[1].operation)
170	<< " (" << bg::operation_char(op.operation) << ")"
171	<< " " << header << std::endl;
172
173	// Uncomment for more detailed debug info in SVG on traversal
174	std::string style
175	= header == "Visit" ? "fill:rgb(80,80,80)" : "fill:rgb(0,0,0)";
176
177	style += ";font-family:Arial;font-size:6px";
178
179	stream(turns, turn, op, header.substr(0, 1), style);
180	}
181
182	template <typename Turns, typename Turn, typename Operation>
183	void visit_traverse_reject(Turns const& turns, Turn const& turn, Operation const& op,
184	bg::detail::overlay::traverse_error_type error)
185	{
186	if (! m_do_output)
187	{
188	return;
189	}
190	std::cout << "Reject turn " << stream_turn_index(turns, turn, op)
191	<< bg::operation_char(turn.operations[0].operation)
192	<< bg::operation_char(turn.operations[1].operation)
193	<< " (" << bg::operation_char(op.operation) << ")"
194	<< " " << bg::detail::overlay::traverse_error_string(error) << std::endl;
195	//return;
196
197	std::string style = "fill:rgb(255,0,0);font-family:Arial;font-size:7px";
198	stream(turns, turn, op, bg::detail::overlay::traverse_error_string(error), style);
199
200	m_do_output = false;
201	}
202
203	template <typename Turns, typename Turn, typename Operation>
204	void visit_traverse_select_turn_from_cluster(Turns const& turns, Turn const& turn, Operation const& op)
205	{
206	std::cout << "Visit turn from cluster " << stream_turn_index(turns, turn, op)
207	<< " " << bg::operation_char(turn.operations[0].operation)
208	<< bg::operation_char(turn.operations[1].operation)
209	<< " (" << bg::operation_char(op.operation) << ")"
210	<< std::endl;
211	return;
212	}
213
214	template <typename Turns, typename Turn, typename Operation>
215	void stream(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header, const std::string& style)
216	{
217	std::ostringstream out;
218	out << m_traverse_seq++ << " " << header
219	<< " " << stream_turn_index(turns, turn, op);
220
221	out << " " << bg::visited_char(op.visited);
222
223	add_text(turn, out.str(), style);
224	}
225
226	template <typename Turn>
227	bool label_operation(Turn const& turn, int index, std::ostream& os)
228	{
229	os << bg::operation_char(turn.operations[index].operation);
230	bool result = false;
231	if (! turn.discarded)
232	{
233	if (turn.operations[index].enriched.next_ip_index != -1)
234	{
235	os << "->" << turn.operations[index].enriched.next_ip_index;
236	if (turn.operations[index].enriched.next_ip_index != -1)
237	{
238	result = true;
239	}
240	}
241	else
242	{
243	os << "->" << turn.operations[index].enriched.travels_to_ip_index;
244	if (turn.operations[index].enriched.travels_to_ip_index != -1)
245	{
246	result = true;
247	}
248	}
b32b8144 FG	249
	250	os << " {" << turn.operations[index].enriched.region_id
	251	<< (turn.operations[index].enriched.isolated ? " ISO" : "")
	252	<< "}";
	253
	254	if (! turn.operations[index].enriched.startable)
	255	{
	256	os << "$";
	257	}
7c673cae FG	258	}
	259
	260	return result;
	261	}
	262
	263	template <typename Turn>
	264	void label_turn(int index, Turn const& turn)
	265	{
	266	std::ostringstream out;
	267	out << index << " ";
	268	if (turn.cluster_id != -1)
	269	{
	270	out << " c=" << turn.cluster_id << " ";
	271	}
	272	bool lab1 = label_operation(turn, 0, out);
	273	out << " / ";
	274	bool lab2 = label_operation(turn, 1, out);
	275	if (turn.switch_source)
	276	{
	277	out << "#";
	278	}
b32b8144 FG	279	if (turn.discarded)
	280	{
	281	out << "!";
	282	}
	283	if (turn.has_colocated_both)
	284	{
	285	out << "+";
	286	}
	287	bool const self_turn = bg::detail::overlay::is_self_turn<bg::overlay_union>(turn);
	288	if (self_turn)
	289	{
	290	out << "@";
	291	}
7c673cae	292
b32b8144 FG	293	std::string font8 = "font-family:Arial;font-size:6px";
	294	std::string font6 = "font-family:Arial;font-size:4px";
	295	std::string style = "fill:rgb(0,0,255);" + font8;
	296	if (self_turn)
7c673cae	297	{
b32b8144 FG	298	if (turn.discarded)
	299	{
	300	style = "fill:rgb(128,28,128);" + font6;
	301	}
	302	else
	303	{
	304	style = "fill:rgb(255,0,255);" + font8;
	305	}
7c673cae FG	306	}
	307	else if (turn.discarded)
	308	{
b32b8144	309	style = "fill:rgb(92,92,92);" + font6;
7c673cae FG	310	}
	311	else if (turn.cluster_id != -1)
	312	{
b32b8144	313	style = "fill:rgb(0,0,255);" + font8;
7c673cae FG	314	}
	315	else if (! lab1 \|\| ! lab2)
	316	{
b32b8144	317	style = "fill:rgb(0,0,255);" + font6;
7c673cae FG	318	}
	319
	320	add_text(turn, out.str(), style);
	321	}
	322
	323	template <typename Turn>
	324	void add_text(Turn const& turn, std::string const& text, std::string const& style)
	325	{
	326	int const margin = 5;
b32b8144	327	int const lineheight = 6;
7c673cae FG	328	double const half = 0.5;
	329	double const ten = 10;
	330
	331	// Map characteristics
	332	// Create a rounded off point
	333	std::pair<int, int> p
	334	= std::make_pair(
	335	boost::numeric_cast<int>(half
	336	+ ten * bg::get<0>(turn.point)),
	337	boost::numeric_cast<int>(half
	338	+ ten * bg::get<1>(turn.point))
	339	);
	340	m_mapper.text(turn.point, text, style, margin, m_offsets[p], lineheight);
	341	m_offsets[p] += lineheight;
	342	}
	343
	344
	345	Mapper& m_mapper;
	346	std::map<std::pair<int, int>, int> m_offsets;
	347	int m_traverse_seq;
	348	bool m_do_output;
	349
	350	};
	351	#endif
	352
	353	template <typename Geometry, bg::overlay_type OverlayType>
	354	void test_overlay(std::string const& caseid,
	355	std::string const& wkt1, std::string const& wkt2,
b32b8144 FG	356	double expected_area,
	357	std::size_t expected_clip_count,
	358	std::size_t expected_hole_count)
7c673cae FG	359	{
	360	Geometry g1;
	361	bg::read_wkt(wkt1, g1);
	362
	363	Geometry g2;
	364	bg::read_wkt(wkt2, g2);
	365
	366	// Reverse if necessary
	367	bg::correct(g1);
	368	bg::correct(g2);
	369
	370	#if defined(TEST_WITH_SVG)
b32b8144 FG	371	bool const ccw = bg::point_order<Geometry>::value == bg::counterclockwise;
	372	bool const open = bg::closure<Geometry>::value == bg::open;
	373
7c673cae FG	374	std::ostringstream filename;
	375	filename << "overlay"
	376	<< "_" << caseid
	377	<< "_" << string_from_type<typename bg::coordinate_type<Geometry>::type>::name()
b32b8144 FG	378	<< (ccw ? "_ccw" : "")
	379	<< (open ? "_open" : "")
	380	#ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS
	381	<< "_self"
	382	#endif
	383	#if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
	384	<< "_no_rob"
	385	#endif
7c673cae FG	386	<< ".svg";
	387
	388	std::ofstream svg(filename.str().c_str());
	389
	390	typedef bg::svg_mapper<typename bg::point_type<Geometry>::type> svg_mapper;
	391
	392	svg_mapper mapper(svg, 500, 500);
	393	mapper.add(g1);
	394	mapper.add(g2);
	395
	396	// Input shapes in green (src=0) / blue (src=1)
	397	mapper.map(g1, "fill-opacity:0.5;fill:rgb(153,204,0);"
	398	"stroke:rgb(153,204,0);stroke-width:3");
	399	mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
	400	"stroke:rgb(51,51,153);stroke-width:3");
	401	#endif
	402
	403
	404	typedef typename boost::range_value<Geometry>::type geometry_out;
	405	typedef bg::detail::overlay::overlay
	406	<
b32b8144 FG	407	Geometry, Geometry,
	408	bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
	409	OverlayType == bg::overlay_difference
	410	? ! bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value
	411	: bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
	412	bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
	413	geometry_out,
7c673cae FG	414	OverlayType
	415	> overlay;
	416
b32b8144 FG	417	typedef typename bg::strategy::intersection::services::default_strategy
	418	<
	419	typename bg::cs_tag<Geometry>::type
	420	>::type strategy_type;
	421
	422	strategy_type strategy;
	423
7c673cae FG	424	typedef typename bg::rescale_overlay_policy_type
	425	<
	426	Geometry,
	427	Geometry
	428	>::type rescale_policy_type;
	429
	430	rescale_policy_type robust_policy
	431	= bg::get_rescale_policy<rescale_policy_type>(g1, g2);
	432
7c673cae FG	433	#if defined(TEST_WITH_SVG)
	434	map_visitor<svg_mapper> visitor(mapper);
	435	#else
	436	bg::detail::overlay::overlay_null_visitor visitor;
	437	#endif
	438
	439	Geometry result;
	440	overlay::apply(g1, g2, robust_policy, std::back_inserter(result),
b32b8144	441	strategy, visitor);
7c673cae FG	442
7c673cae FG	443	BOOST_CHECK_CLOSE(bg::area(result), expected_area, 0.001);
b32b8144 FG	444	BOOST_CHECK_MESSAGE((bg::num_interior_rings(result) == expected_hole_count),
	445	caseid
	446	<< " hole count: detected: " << bg::num_interior_rings(result)
	447	<< " expected: " << expected_hole_count);
	448	BOOST_CHECK_MESSAGE((result.size() == expected_clip_count),
	449	caseid
	450	<< " clip count: detected: " << result.size()
	451	<< " expected: " << expected_clip_count);
7c673cae FG	452
	453	#if defined(TEST_WITH_SVG)
	454	mapper.map(result, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
	455	"stroke:rgb(255,0,255);stroke-width:8");
	456
	457	#endif
	458	}
	459
b32b8144 FG	460	#define TEST_INTERSECTION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
	461	( #caseid "_int", caseid[0], caseid[1], area, clips, holes)
	462	#define TEST_UNION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
	463	( #caseid "_union", caseid[0], caseid[1], area, clips, holes)
	464	#define TEST_DIFFERENCE_A(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
	465	( #caseid "_diff_a", caseid[0], caseid[1], area, clips, holes)
	466	#define TEST_DIFFERENCE_B(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
	467	( #caseid "_diff_b", caseid[1], caseid[0], area, clips, holes)
	468
	469	#define TEST_INTERSECTION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
	470	( #caseid "_int_" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)
	471	#define TEST_UNION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
	472	( #caseid "_union" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)
	473
	474	template <typename T, bool Clockwise>
7c673cae FG	475	void test_all()
	476	{
	477	typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
b32b8144	478	typedef bg::model::polygon<point_type, Clockwise> polygon;
7c673cae FG	479	typedef bg::model::multi_polygon<polygon> multi_polygon;
7c673cae FG	480
b32b8144 FG	481	TEST_UNION(case_multi_simplex, 14.58, 1, 0);
	482	TEST_INTERSECTION(case_multi_simplex, 6.42, 2, 0);
	483
	484	TEST_DIFFERENCE_A(case_multi_simplex, 5.58, 5, 0);
	485	TEST_DIFFERENCE_B(case_multi_simplex, 2.58, 4, 0);
7c673cae FG	486
7c673cae FG	487	// Contains 5 clusters, needing immediate selection of next turn
b32b8144	488	TEST_UNION_WITH(case_58_multi, 0, 3, 19.8333333, 2, 0);
7c673cae FG	489
7c673cae FG	490	// Contains many clusters, needing to exclude u/u turns
b32b8144 FG	491	TEST_UNION(case_recursive_boxes_3, 56.5, 17, 6);
b32b8144 FG	492
7c673cae	493	// Contains 4 clusters, one of which having 4 turns
b32b8144	494	TEST_UNION(case_recursive_boxes_7, 7.0, 2, 0);
7c673cae FG	495
7c673cae FG	496	// Contains 5 clusters, needing immediate selection of next turn
b32b8144	497	TEST_UNION(case_89_multi, 6.0, 1, 0);
7c673cae FG	498
7c673cae FG	499	// Needs ux/next_turn_index==-1 to be filtered out
b32b8144 FG	500	TEST_INTERSECTION(case_77_multi, 9.0, 5, 0);
	501	TEST_UNION(case_101_multi, 22.25, 1, 3);
	502	TEST_INTERSECTION(case_101_multi, 4.75, 4, 0);
	503
	504	TEST_INTERSECTION(case_recursive_boxes_11, 1.0, 2, 0);
	505	TEST_INTERSECTION(case_recursive_boxes_30, 6.0, 4, 0);
	506
	507	TEST_UNION(case_recursive_boxes_4, 96.75, 1, 2);
	508	TEST_INTERSECTION_WITH(case_58_multi, 2, 6, 13.25, 1, 1);
	509	TEST_INTERSECTION_WITH(case_72_multi, 1, 2, 6.15, 3, 1);
	510	TEST_UNION(case_recursive_boxes_12, 6.0, 6, 0);
	511	TEST_UNION(case_recursive_boxes_13, 10.25, 3, 0);
7c673cae FG	512
	513
	514	// std::cout
	515	// << " \""
	516	// << bg::inverse<multi_polygon>(case_65_multi[0], 1.0)
	517	// << "\"" << std::endl;
	518	}
	519
	520	int test_main(int, char* [])
	521	{
b32b8144 FG	522	test_all<double, true>();
b32b8144 FG	523	// test_all<double, false>();
7c673cae FG	524	return 0;
7c673cae FG	525	}