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

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

// Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.

// 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 <geometry_test_common.hpp>

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

#include <boost/geometry/strategies/strategies.hpp>  // for equals/within
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
#include <boost/geometry/algorithms/correct.hpp>
#include <boost/geometry/algorithms/equals.hpp>
#include <boost/geometry/io/wkt/wkt.hpp>
#include <boost/geometry/geometries/geometries.hpp>

#include <boost/assign/list_of.hpp>
#include <boost/foreach.hpp>

#if defined(TEST_WITH_SVG)
#include "debug_sort_by_side_svg.hpp"
#endif

namespace
{


template <typename T>
std::string as_string(std::vector<T> const& v)
{
    std::stringstream out;
    bool first = true;
    BOOST_FOREACH(T const& value, v)
    {
        out << (first ? "[" : " , ") << value;
        first = false;
    }
    out << (first ? "" : "]");
    return out.str();
}

}

template
<
    typename Geometry, typename Point,
    typename RobustPolicy, typename Strategy
>
std::vector<std::size_t> apply_get_turns(std::string const& case_id,
            Geometry const& geometry1, Geometry const& geometry2,
            Point const& turn_point, Point const& origin_point,
            RobustPolicy const& robust_policy,
            Strategy const& strategy,
            std::size_t expected_open_count,
            std::size_t expected_max_rank,
            std::vector<bg::signed_size_type> const& expected_right_count)
{
    using namespace boost::geometry;

    std::vector<std::size_t> result;

//todo: maybe should be enriched to count left/right - but can also be counted from ranks
    typedef typename bg::point_type<Geometry>::type point_type;
    typedef bg::detail::overlay::turn_info
    <
        point_type,
        typename bg::detail::segment_ratio_type<point_type, RobustPolicy>::type
    > turn_info;
    typedef std::deque<turn_info> turn_container_type;

    turn_container_type turns;

    detail::get_turns::no_interrupt_policy policy;
    bg::get_turns
        <
            false, false,
            detail::overlay::assign_null_policy
        >(geometry1, geometry2, strategy, robust_policy, turns, policy);


    // Define sorter, sorting counter-clockwise such that polygons are on the
    // right side
    typedef typename Strategy::side_strategy_type side_strategy;
    typedef bg::detail::overlay::sort_by_side::side_sorter
        <
            false, false, overlay_union,
            point_type, side_strategy, std::less<int>
        > sbs_type;

    sbs_type sbs(strategy.get_side_strategy());

    std::cout << "Case: " << case_id << std::endl;

    bool has_origin = false;
    for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
    {
        turn_info const& turn = turns[turn_index];

        if (bg::equals(turn.point, turn_point))
        {
//            std::cout << "Found turn: " << turn_index << std::endl;
            for (int i = 0; i < 2; i++)
            {
                Point point1, point2, point3;
                bg::copy_segment_points<false, false>(geometry1, geometry2,
                        turn.operations[i].seg_id, point1, point2, point3);
                bool const is_origin = ! has_origin && bg::equals(point1, origin_point);
                if (is_origin)
                {
                    has_origin = true;
                }

                sbs.add(turn.operations[i], turn_index, i,
                        geometry1, geometry2, is_origin);

            }
        }
    }

    BOOST_CHECK_MESSAGE(has_origin,
                        "  caseid="  << case_id
                        << " origin not found");

    if (!has_origin)
    {
        for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
        {
            turn_info const& turn = turns[turn_index];
            if (bg::equals(turn.point, turn_point))
            {
                for (int i = 0; i < 2; i++)
                {
                    Point point1, point2, point3;
                    bg::copy_segment_points<false, false>(geometry1, geometry2,
                            turn.operations[i].seg_id, point1, point2, point3);
//                    std::cout << "Turn " << turn_index << " op " << i << " point1=" << bg::wkt(point1) << std::endl;
                }
            }
        }
        return result;
    }


    sbs.apply(turn_point);

    sbs.find_open();
    sbs.assign_zones(detail::overlay::operation_union);

    std::size_t const open_count = sbs.open_count(detail::overlay::operation_union);
    std::size_t const max_rank = sbs.m_ranked_points.back().rank;
    std::vector<bg::signed_size_type> right_count(max_rank + 1, -1);

    int previous_rank = -1;
    int previous_to_rank = -1;
    for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
    {
        typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];

        int const rank = static_cast<int>(ranked_point.rank);
        bool const set_right = rank != previous_to_rank;
        if (rank != previous_rank)
        {
            BOOST_CHECK_MESSAGE(rank == previous_rank + 1,
                                "  caseid="  << case_id
                                << " ranks: conflict in ranks="  << ranked_point.rank
                                << " vs " << previous_rank + 1);
            previous_rank = rank;
        }

        if (ranked_point.direction != bg::detail::overlay::sort_by_side::dir_to)
        {
            continue;
        }

        previous_to_rank = rank;
        if (set_right)
        {
            right_count[rank] = ranked_point.count_right;
        }
        else
        {
            BOOST_CHECK_MESSAGE(right_count[rank] == int(ranked_point.count_right),
                                "  caseid="  << case_id
                                << " ranks: conflict in right_count="  << ranked_point.count_right
                                << " vs " << right_count[rank]);
        }

    }
    BOOST_CHECK_MESSAGE(open_count == expected_open_count,
                        "  caseid="  << case_id
                        << " open_count: expected="  << expected_open_count
                        << " detected="  << open_count);

    BOOST_CHECK_MESSAGE(max_rank == expected_max_rank,
                        "  caseid="  << case_id
                        << " max_rank: expected="  << expected_max_rank
                        << " detected="  << max_rank);

    BOOST_CHECK_MESSAGE(right_count == expected_right_count,
                        "  caseid="  << case_id
                        << " right count: expected="  << as_string(expected_right_count)
                        << " detected="  << as_string(right_count));

#if defined(TEST_WITH_SVG)
    debug::sorted_side_map(case_id, sbs, turn_point, geometry1, geometry2);
#endif

    return result;
}


template <typename T>
void test_basic(std::string const& case_id,
                std::string const& wkt1,
                std::string const& wkt2,
                std::string const& wkt_turn_point,
                std::string const& wkt_origin_point,
                std::size_t expected_open_count,
                std::size_t expected_max_rank,
                std::vector<bg::signed_size_type> const& expected_right_count)
{
    typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
    typedef bg::model::polygon<point_type> polygon;
    typedef bg::model::multi_polygon<polygon> multi_polygon;

    multi_polygon g1;
    bg::read_wkt(wkt1, g1);

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

    point_type turn_point, origin_point;
    bg::read_wkt(wkt_turn_point, turn_point);
    bg::read_wkt(wkt_origin_point, origin_point);

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

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

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

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

    strategy_type strategy;

    apply_get_turns(case_id, g1, g2, turn_point, origin_point,
        robust_policy, strategy,
        expected_open_count, expected_max_rank, expected_right_count);
}

using boost::assign::list_of;

template <typename T>
void test_all()
{
    test_basic<T>("simplex",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
      "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
      "POINT(1 1)", "POINT(1 0)",
      2, 3, list_of(-1)(1)(-1)(1));

    test_basic<T>("dup1",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
      "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
      "POINT(1 1)", "POINT(1 0)",
      2, 3, list_of(-1)(1)(-1)(2));

    test_basic<T>("dup2",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
      "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
      "POINT(1 1)", "POINT(1 0)",
      2, 3, list_of(-1)(2)(-1)(1));

    test_basic<T>("dup3",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
      "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
      "POINT(1 1)", "POINT(1 0)",
      2, 3, list_of(-1)(2)(-1)(2));

    test_basic<T>("threequart1",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
      "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)))",
      "POINT(1 1)", "POINT(1 0)",
      1, 3, list_of(-1)(1)(1)(1));

    test_basic<T>("threequart2",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
      "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)))",
      "POINT(1 1)", "POINT(1 0)",
      1, 4, list_of(-1)(2)(1)(1)(1));

    test_basic<T>("threequart3",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
      "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)),((0 1,0 2,1 1,0 1)))",
      "POINT(1 1)", "POINT(1 0)",
      1, 5, list_of(-1)(2)(1)(1)(-1)(2));

    test_basic<T>("full1",
      "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
      "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((0 0,0 1,1 1,1 0,0 0)))",
      "POINT(1 1)", "POINT(1 0)",
      0, 3, list_of(1)(1)(1)(1));

    test_basic<T>("hole1",
      "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
      "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
      "POINT(1 2)", "POINT(2 2)",
      1, 2, list_of(-1)(2)(1));

    test_basic<T>("hole2",
      "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
      "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
      "POINT(2 2)", "POINT(2 1)",
      2, 3, list_of(-1)(2)(-1)(2));

    test_basic<T>("hole3",
      "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
      "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
      "POINT(3 2)", "POINT(2 2)",
      1, 3, list_of(-1)(2)(-1)(2));
}


int test_main(int, char* [])
{
    test_all<double>();
    return 0;
}
Commit	Line	Data
b32b8144 FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2	// Unit Test
	3
	4	// Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
11fdf7f2	5	// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
b32b8144 FG	6
	7	// This file was modified by Oracle on 2017.
	8	// Modifications copyright (c) 2017, Oracle and/or its affiliates.
	9	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	10
	11	// Use, modification and distribution is subject to the Boost Software License,
	12	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	13	// http://www.boost.org/LICENSE_1_0.txt)
	14
	15	#include <geometry_test_common.hpp>
	16
	17	#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
	18
	19	#include <boost/geometry/strategies/strategies.hpp> // for equals/within
	20	#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
	21	#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
	22	#include <boost/geometry/algorithms/correct.hpp>
	23	#include <boost/geometry/algorithms/equals.hpp>
	24	#include <boost/geometry/io/wkt/wkt.hpp>
	25	#include <boost/geometry/geometries/geometries.hpp>
	26
	27	#include <boost/assign/list_of.hpp>
	28	#include <boost/foreach.hpp>
	29
	30	#if defined(TEST_WITH_SVG)
	31	#include "debug_sort_by_side_svg.hpp"
	32	#endif
	33
	34	namespace
	35	{
	36
	37
	38	template <typename T>
	39	std::string as_string(std::vector<T> const& v)
	40	{
	41	std::stringstream out;
	42	bool first = true;
	43	BOOST_FOREACH(T const& value, v)
	44	{
	45	out << (first ? "[" : " , ") << value;
	46	first = false;
	47	}
	48	out << (first ? "" : "]");
	49	return out.str();
	50	}
	51
	52	}
	53
	54	template
	55	<
	56	typename Geometry, typename Point,
	57	typename RobustPolicy, typename Strategy
	58	>
	59	std::vector<std::size_t> apply_get_turns(std::string const& case_id,
	60	Geometry const& geometry1, Geometry const& geometry2,
	61	Point const& turn_point, Point const& origin_point,
	62	RobustPolicy const& robust_policy,
	63	Strategy const& strategy,
	64	std::size_t expected_open_count,
	65	std::size_t expected_max_rank,
11fdf7f2	66	std::vector<bg::signed_size_type> const& expected_right_count)
b32b8144 FG	67	{
	68	using namespace boost::geometry;
	69
	70	std::vector<std::size_t> result;
	71
	72	//todo: maybe should be enriched to count left/right - but can also be counted from ranks
	73	typedef typename bg::point_type<Geometry>::type point_type;
	74	typedef bg::detail::overlay::turn_info
	75	<
	76	point_type,
92f5a8d4	77	typename bg::detail::segment_ratio_type<point_type, RobustPolicy>::type
b32b8144 FG	78	> turn_info;
	79	typedef std::deque<turn_info> turn_container_type;
	80
	81	turn_container_type turns;
	82
	83	detail::get_turns::no_interrupt_policy policy;
	84	bg::get_turns
	85	<
	86	false, false,
	87	detail::overlay::assign_null_policy
	88	>(geometry1, geometry2, strategy, robust_policy, turns, policy);
	89
	90
	91	// Define sorter, sorting counter-clockwise such that polygons are on the
	92	// right side
	93	typedef typename Strategy::side_strategy_type side_strategy;
	94	typedef bg::detail::overlay::sort_by_side::side_sorter
	95	<
	96	false, false, overlay_union,
	97	point_type, side_strategy, std::less<int>
	98	> sbs_type;
	99
	100	sbs_type sbs(strategy.get_side_strategy());
	101
	102	std::cout << "Case: " << case_id << std::endl;
	103
	104	bool has_origin = false;
	105	for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
	106	{
	107	turn_info const& turn = turns[turn_index];
	108
	109	if (bg::equals(turn.point, turn_point))
	110	{
	111	// std::cout << "Found turn: " << turn_index << std::endl;
	112	for (int i = 0; i < 2; i++)
	113	{
	114	Point point1, point2, point3;
	115	bg::copy_segment_points<false, false>(geometry1, geometry2,
	116	turn.operations[i].seg_id, point1, point2, point3);
	117	bool const is_origin = ! has_origin && bg::equals(point1, origin_point);
	118	if (is_origin)
	119	{
	120	has_origin = true;
	121	}
	122
	123	sbs.add(turn.operations[i], turn_index, i,
	124	geometry1, geometry2, is_origin);
	125
	126	}
	127	}
	128	}
	129
	130	BOOST_CHECK_MESSAGE(has_origin,
	131	" caseid=" << case_id
	132	<< " origin not found");
	133
	134	if (!has_origin)
	135	{
	136	for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
	137	{
	138	turn_info const& turn = turns[turn_index];
	139	if (bg::equals(turn.point, turn_point))
	140	{
	141	for (int i = 0; i < 2; i++)
142	{
143	Point point1, point2, point3;
144	bg::copy_segment_points<false, false>(geometry1, geometry2,
145	turn.operations[i].seg_id, point1, point2, point3);
146	// std::cout << "Turn " << turn_index << " op " << i << " point1=" << bg::wkt(point1) << std::endl;
147	}
148	}
149	}
150	return result;
151	}
152
153
154	sbs.apply(turn_point);
155
156	sbs.find_open();
157	sbs.assign_zones(detail::overlay::operation_union);
158
159	std::size_t const open_count = sbs.open_count(detail::overlay::operation_union);
160	std::size_t const max_rank = sbs.m_ranked_points.back().rank;
11fdf7f2	161	std::vector<bg::signed_size_type> right_count(max_rank + 1, -1);
b32b8144 FG	162
	163	int previous_rank = -1;
	164	int previous_to_rank = -1;
	165	for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
	166	{
	167	typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
	168
	169	int const rank = static_cast<int>(ranked_point.rank);
	170	bool const set_right = rank != previous_to_rank;
	171	if (rank != previous_rank)
	172	{
	173	BOOST_CHECK_MESSAGE(rank == previous_rank + 1,
	174	" caseid=" << case_id
	175	<< " ranks: conflict in ranks=" << ranked_point.rank
	176	<< " vs " << previous_rank + 1);
	177	previous_rank = rank;
	178	}
	179
	180	if (ranked_point.direction != bg::detail::overlay::sort_by_side::dir_to)
	181	{
	182	continue;
	183	}
	184
	185	previous_to_rank = rank;
	186	if (set_right)
	187	{
	188	right_count[rank] = ranked_point.count_right;
	189	}
	190	else
	191	{
	192	BOOST_CHECK_MESSAGE(right_count[rank] == int(ranked_point.count_right),
	193	" caseid=" << case_id
	194	<< " ranks: conflict in right_count=" << ranked_point.count_right
	195	<< " vs " << right_count[rank]);
	196	}
	197
	198	}
	199	BOOST_CHECK_MESSAGE(open_count == expected_open_count,
	200	" caseid=" << case_id
	201	<< " open_count: expected=" << expected_open_count
	202	<< " detected=" << open_count);
	203
	204	BOOST_CHECK_MESSAGE(max_rank == expected_max_rank,
	205	" caseid=" << case_id
	206	<< " max_rank: expected=" << expected_max_rank
	207	<< " detected=" << max_rank);
	208
	209	BOOST_CHECK_MESSAGE(right_count == expected_right_count,
	210	" caseid=" << case_id
	211	<< " right count: expected=" << as_string(expected_right_count)
	212	<< " detected=" << as_string(right_count));
	213
	214	#if defined(TEST_WITH_SVG)
	215	debug::sorted_side_map(case_id, sbs, turn_point, geometry1, geometry2);
	216	#endif
	217
	218	return result;
	219	}
	220
	221
	222	template <typename T>
	223	void test_basic(std::string const& case_id,
	224	std::string const& wkt1,
	225	std::string const& wkt2,
226	std::string const& wkt_turn_point,
227	std::string const& wkt_origin_point,
228	std::size_t expected_open_count,
229	std::size_t expected_max_rank,
11fdf7f2	230	std::vector<bg::signed_size_type> const& expected_right_count)
b32b8144 FG	231	{
	232	typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
	233	typedef bg::model::polygon<point_type> polygon;
	234	typedef bg::model::multi_polygon<polygon> multi_polygon;
	235
	236	multi_polygon g1;
	237	bg::read_wkt(wkt1, g1);
	238
	239	multi_polygon g2;
	240	bg::read_wkt(wkt2, g2);
	241
	242	point_type turn_point, origin_point;
	243	bg::read_wkt(wkt_turn_point, turn_point);
	244	bg::read_wkt(wkt_origin_point, origin_point);
	245
	246	// Reverse if necessary
	247	bg::correct(g1);
	248	bg::correct(g2);
	249
	250	typedef typename bg::rescale_overlay_policy_type
	251	<
	252	multi_polygon,
	253	multi_polygon
	254	>::type rescale_policy_type;
	255
	256	rescale_policy_type robust_policy
	257	= bg::get_rescale_policy<rescale_policy_type>(g1, g2);
	258
	259	typedef typename bg::strategy::intersection::services::default_strategy
	260	<
	261	typename bg::cs_tag<point_type>::type
	262	>::type strategy_type;
	263
	264	strategy_type strategy;
	265
	266	apply_get_turns(case_id, g1, g2, turn_point, origin_point,
	267	robust_policy, strategy,
	268	expected_open_count, expected_max_rank, expected_right_count);
	269	}
	270
	271	using boost::assign::list_of;
	272
	273	template <typename T>
	274	void test_all()
	275	{
	276	test_basic<T>("simplex",
	277	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
	278	"MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
	279	"POINT(1 1)", "POINT(1 0)",
	280	2, 3, list_of(-1)(1)(-1)(1));
	281
	282	test_basic<T>("dup1",
	283	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
	284	"MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
	285	"POINT(1 1)", "POINT(1 0)",
	286	2, 3, list_of(-1)(1)(-1)(2));
	287
	288	test_basic<T>("dup2",
	289	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
	290	"MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
	291	"POINT(1 1)", "POINT(1 0)",
	292	2, 3, list_of(-1)(2)(-1)(1));
	293
	294	test_basic<T>("dup3",
295	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
296	"MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
297	"POINT(1 1)", "POINT(1 0)",
298	2, 3, list_of(-1)(2)(-1)(2));
299
300	test_basic<T>("threequart1",
301	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
302	"MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)))",
303	"POINT(1 1)", "POINT(1 0)",
304	1, 3, list_of(-1)(1)(1)(1));
305
306	test_basic<T>("threequart2",
307	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
308	"MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)))",
309	"POINT(1 1)", "POINT(1 0)",
310	1, 4, list_of(-1)(2)(1)(1)(1));
311
312	test_basic<T>("threequart3",
313	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
314	"MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)),((0 1,0 2,1 1,0 1)))",
315	"POINT(1 1)", "POINT(1 0)",
316	1, 5, list_of(-1)(2)(1)(1)(-1)(2));
317
318	test_basic<T>("full1",
319	"MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
320	"MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((0 0,0 1,1 1,1 0,0 0)))",
321	"POINT(1 1)", "POINT(1 0)",
322	0, 3, list_of(1)(1)(1)(1));
323
324	test_basic<T>("hole1",
325	"MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
326	"MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
327	"POINT(1 2)", "POINT(2 2)",
328	1, 2, list_of(-1)(2)(1));
329
330	test_basic<T>("hole2",
331	"MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
332	"MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
333	"POINT(2 2)", "POINT(2 1)",
334	2, 3, list_of(-1)(2)(-1)(2));
335
336	test_basic<T>("hole3",
337	"MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
338	"MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
339	"POINT(3 2)", "POINT(2 2)",
340	1, 3, list_of(-1)(2)(-1)(2));
341	}
342
343
344	int test_main(int, char* [])
345	{
346	test_all<double>();
347	return 0;
348	}