[ceph.git] / ceph / src / boost / libs / geometry / test / strategies / segment_intersection_collinear.cpp

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

// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.

// Copyright (c) 2017-2020, Oracle and/or its affiliates.
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle

// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
// (geolib/GGL), copyright (c) 1995-2010 Geodan, 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)

#define BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO

#include <geometry_test_common.hpp>

#include <boost/geometry/algorithms/assign.hpp>

#include <boost/geometry/strategies/cartesian/intersection.hpp>
#include <boost/geometry/strategies/intersection_result.hpp>

#include <boost/geometry/policies/relate/intersection_policy.hpp>

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

#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/segment.hpp>


template <typename IntersectionPoints>
static int check(IntersectionPoints const& is,
                std::size_t index, double expected_x, double expected_y)
{
    if (expected_x != -99 && expected_y != -99 && is.count > index)
    {
        double x = bg::get<0>(is.intersections[index]);
        double y = bg::get<1>(is.intersections[index]);

        BOOST_CHECK_CLOSE(x, expected_x, 0.001);
        BOOST_CHECK_CLOSE(y, expected_y, 0.001);
        return 1;
    }
    return 0;
}


template <typename P>
static void test_segment_intersection(std::string const& case_id,
                int x1, int y1, int x2, int y2,
                int x3, int y3, int x4, int y4,
                char expected_how, bool expected_opposite,
                int expected_arrival1, int expected_arrival2,
                int expected_x1, int expected_y1,
                int expected_x2 = -99, int expected_y2 = -99)

{
    boost::ignore_unused(case_id);

    typedef bg::model::referring_segment<const P> segment_type;

    P p1, p2, p3, p4;
    bg::assign_values(p1, x1, y1);
    bg::assign_values(p2, x2, y2);
    bg::assign_values(p3, x3, y3);
    bg::assign_values(p4, x4, y4);

    segment_type s12(p1, p2);
    segment_type s34(p3, p4);

    bg::detail::segment_as_subrange<segment_type> sr12(s12);
    bg::detail::segment_as_subrange<segment_type> sr34(s34);

    typedef bg::segment_intersection_points<P> result_type;

    typedef bg::policies::relate::segments_intersection_points
        <
            result_type
        > points_policy_type;

    // Get the intersection point (or two points)
    result_type is
        = bg::strategy::intersection::cartesian_segments<>
            ::apply(sr12, sr34, points_policy_type());

    // Get just a character for Left/Right/intersects/etc, purpose is more for debugging
    bg::policies::relate::direction_type dir
        = bg::strategy::intersection::cartesian_segments<>
            ::apply(sr12, sr34, bg::policies::relate::segments_direction());

    std::size_t expected_count =
        check(is, 0, expected_x1, expected_y1)
        + check(is, 1, expected_x2, expected_y2);

    BOOST_CHECK_EQUAL(is.count, expected_count);
    BOOST_CHECK_EQUAL(dir.how, expected_how);
    BOOST_CHECK_EQUAL(dir.opposite, expected_opposite);
    BOOST_CHECK_EQUAL(dir.arrival[0], expected_arrival1);
    BOOST_CHECK_EQUAL(dir.arrival[1], expected_arrival2);
}

template <typename P, typename Pair>
static void test_segment_ratio(std::string const& case_id,
                int x1, int y1, int x2, int y2,
                int x3, int y3, int x4, int y4,
                Pair expected_pair_a1, Pair expected_pair_a2,
                Pair expected_pair_b1, Pair expected_pair_b2,
                int exp_ax1, int exp_ay1, int exp_ax2, int exp_ay2,
                std::size_t expected_count = 2)

{
    boost::ignore_unused(case_id);

    typedef bg::model::referring_segment<const P> segment_type;

    P p1, p2, p3, p4;
    bg::assign_values(p1, x1, y1);
    bg::assign_values(p2, x2, y2);
    bg::assign_values(p3, x3, y3);
    bg::assign_values(p4, x4, y4);

    segment_type s12(p1, p2);
    segment_type s34(p3, p4);

    bg::detail::segment_as_subrange<segment_type> sr12(s12);
    bg::detail::segment_as_subrange<segment_type> sr34(s34);

    typedef bg::segment_intersection_points<P> result_type;

    typedef bg::policies::relate::segments_intersection_points
        <
            result_type
        > points_policy_type;

    // Get the intersection point (or two points)
    result_type is
        = bg::strategy::intersection::cartesian_segments<>
            ::apply(sr12, sr34, points_policy_type());

    typedef bg::segment_ratio<typename bg::coordinate_type<P>::type> ratio_type;

    ratio_type expected_a1(expected_pair_a1.first, expected_pair_a1.second);
    ratio_type expected_a2(expected_pair_a2.first, expected_pair_a2.second);
    ratio_type expected_b1(expected_pair_b1.first, expected_pair_b1.second);
    ratio_type expected_b2(expected_pair_b2.first, expected_pair_b2.second);

    BOOST_CHECK_EQUAL(is.count, expected_count);

    BOOST_CHECK_EQUAL(is.fractions[0].robust_ra, expected_a1);
    BOOST_CHECK_EQUAL(is.fractions[0].robust_rb, expected_b1);
    BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[0]), exp_ax1);
    BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[0]), exp_ay1);

    if (expected_count == 2)
    {
        BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[1]), exp_ax2);
        BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[1]), exp_ay2);
        BOOST_CHECK_EQUAL(is.fractions[1].robust_ra, expected_a2);
        BOOST_CHECK_EQUAL(is.fractions[1].robust_rb, expected_b2);
    }
}


template <typename P>
void test_all()
{
    // Collinear - non opposite

    //       a1---------->a2
    // b1--->b2
    test_segment_intersection<P>("n1",
        2, 0, 6, 0,
        0, 0, 2, 0,
        'a', false, -1, 0,
        2, 0);

    //       a1---------->a2
    //    b1--->b2
    test_segment_intersection<P>("n2",
        2, 0, 6, 0,
        1, 0, 3, 0,
        'c', false, -1, 1,
        2, 0, 3, 0);

    //       a1---------->a2
    //       b1--->b2
    test_segment_intersection<P>("n3",
        2, 0, 6, 0,
        2, 0, 4, 0,
        'c', false, -1, 1,
        2, 0, 4, 0);

    //       a1---------->a2
    //          b1--->b2
    test_segment_intersection<P>("n4",
        2, 0, 6, 0,
        3, 0, 5, 0,
        'c', false, -1, 1,
        3, 0, 5, 0);

    //       a1---------->a2
    //              b1--->b2
    test_segment_intersection<P>("n5",
        2, 0, 6, 0,
        4, 0, 6, 0,
        'c', false, 0, 0,
        4, 0, 6, 0);

    //       a1---------->a2
    //                 b1--->b2
    test_segment_intersection<P>("n6",
        2, 0, 6, 0,
        5, 0, 7, 0,
        'c', false, 1, -1,
        5, 0, 6, 0);

    //       a1---------->a2
    //                    b1--->b2
    test_segment_intersection<P>("n7",
        2, 0, 6, 0,
        6, 0, 8, 0,
        'a', false, 0, -1,
        6, 0);

    // Collinear - opposite
    //       a1---------->a2
    // b2<---b1
    test_segment_intersection<P>("o1",
        2, 0, 6, 0,
        2, 0, 0, 0,
        'f', true, -1, -1,
        2, 0);

    //       a1---------->a2
    //    b2<---b1
    test_segment_intersection<P>("o2",
        2, 0, 6, 0,
        3, 0, 1, 0,
        'c', true, -1, -1,
        2, 0, 3, 0);

    //       a1---------->a2
    //       b2<---b1
    test_segment_intersection<P>("o3",
        2, 0, 6, 0,
        4, 0, 2, 0,
        'c', true, -1, 0,
        2, 0, 4, 0);

    //       a1---------->a2
    //           b2<---b1
    test_segment_intersection<P>("o4",
        2, 0, 6, 0,
        5, 0, 3, 0,
        'c', true, -1, 1,
        3, 0, 5, 0);

    //       a1---------->a2
    //              b2<---b1
    test_segment_intersection<P>("o5",
        2, 0, 6, 0,
        6, 0, 4, 0,
        'c', true, 0, 1,
        4, 0, 6, 0);

    //       a1---------->a2
    //                b2<---b1
    test_segment_intersection<P>("o6",
        2, 0, 6, 0,
        7, 0, 5, 0,
        'c', true, 1, 1,
        5, 0, 6, 0);

    //       a1---------->a2
    //                    b2<---b1
    test_segment_intersection<P>("o7",
        2, 0, 6, 0,
        8, 0, 6, 0,
        't', true, 0, 0,
        6, 0);

    //   a1---------->a2
    //   b1---------->b2
    test_segment_intersection<P>("e1",
        2, 0, 6, 0,
        2, 0, 6, 0,
        'e', false, 0, 0,
        2, 0, 6, 0);

    //   a1---------->a2
    //   b2<----------b1
    test_segment_intersection<P>("e1",
        2, 0, 6, 0,
        6, 0, 2, 0,
        'e', true, 0, 0,
        2, 0, 6, 0);

    // Disjoint (in vertical direction, picture still horizontal)
    //   a2<---a1
    //                      b2<---b1
    test_segment_intersection<P>("case_recursive_boxes_1",
        10, 7, 10, 6,
        10, 10, 10, 9,
        'd', false, 0, 0,
        -1, -1, -1, -1);

}


template <typename P>
void test_ratios()
{
    // B inside A
    //       a1------------>a2
    //          b1--->b2
    test_segment_ratio<P>("n4",
        2, 0, 7, 0,
        3, 0, 5, 0,
        std::make_pair(1, 5), std::make_pair(3, 5), // IP located on 1/5, 3/5 w.r.t A
        std::make_pair(0, 1), std::make_pair(1, 1), // IP located on 0, 1 w.r.t. B
        // IP's are ordered as in A (currently)
        3, 0, 5, 0);

    //       a1------------>a2
    //           b2<---b1
    test_segment_ratio<P>("o4",
        2, 0, 7, 0,
        5, 0, 3, 0,
        std::make_pair(1, 5), std::make_pair(3, 5),
        std::make_pair(1, 1), std::make_pair(0, 1),
        3, 0, 5, 0);

    //       a2<------------a1
    //           b2<---b1
    test_segment_ratio<P>("o4b",
        7, 0, 2, 0,
        5, 0, 3, 0,
        std::make_pair(2, 5), std::make_pair(4, 5),
        std::make_pair(0, 1), std::make_pair(1, 1),
        5, 0, 3, 0);

    //       a2<------------a1
    //          b1--->b2
    test_segment_ratio<P>("o4c",
        7, 0, 2, 0,
        3, 0, 5, 0,
        std::make_pair(2, 5), std::make_pair(4, 5),
        std::make_pair(1, 1), std::make_pair(0, 1),
        5, 0, 3, 0);

    // Touch-interior
    //       a1---------->a2
    //       b1--->b2
    test_segment_ratio<P>("n3",
        2, 0, 7, 0,
        2, 0, 4, 0,
        std::make_pair(0, 1), std::make_pair(2, 5),
        std::make_pair(0, 1), std::make_pair(1, 1),
        2, 0, 4, 0);

    //    a2<-------------a1
    //             b2<----b1
    test_segment_ratio<P>("n3b",
        7, 0, 2, 0,
        7, 0, 5, 0,
        std::make_pair(0, 1), std::make_pair(2, 5),
        std::make_pair(0, 1), std::make_pair(1, 1),
        7, 0, 5, 0);


    // A inside B
    //          a1--->a2
    //       b1------------>b2
    test_segment_ratio<P>("rn4",
        3, 0, 5, 0,
        2, 0, 7, 0,
        std::make_pair(0, 1), std::make_pair(1, 1),
        std::make_pair(1, 5), std::make_pair(3, 5),
        3, 0, 5, 0);

    //           a2<---a1
    //       b1------------>b2
    test_segment_ratio<P>("ro4",
        5, 0, 3, 0,
        2, 0, 7, 0,
        std::make_pair(0, 1), std::make_pair(1, 1),
        std::make_pair(3, 5), std::make_pair(1, 5),
        5, 0, 3, 0);

    //           a2<---a1
    //       b2<------------b1
    test_segment_ratio<P>("ro4b",
        5, 0, 3, 0,
        7, 0, 2, 0,
        std::make_pair(0, 1), std::make_pair(1, 1),
        std::make_pair(2, 5), std::make_pair(4, 5),
        5, 0, 3, 0);

    //          a1--->a2
    //       b2<------------b1
    test_segment_ratio<P>("ro4c",
        3, 0, 5, 0,
        7, 0, 2, 0,
        std::make_pair(0, 1), std::make_pair(1, 1),
        std::make_pair(4, 5), std::make_pair(2, 5),
        3, 0, 5, 0);

    // B inside A, boundaries intersect
    // We change the coordinates a bit (w.r.t. n3 above) to have it asymmetrical
    //       a1---------->a2
    //       b1--->b2
    test_segment_ratio<P>("n3",
        2, 0, 7, 0,
        2, 0, 4, 0,
        std::make_pair(0, 1), std::make_pair(2, 5),
        std::make_pair(0, 1), std::make_pair(1, 1),
        2, 0, 4, 0);

    //       a1---------->a2
    //       b2<---b1
    test_segment_ratio<P>("o3",
        2, 0, 7, 0,
        4, 0, 2, 0,
        std::make_pair(0, 1), std::make_pair(2, 5),
        std::make_pair(1, 1), std::make_pair(0, 1),
        2, 0, 4, 0);

    //       a1---------->a2
    //              b1--->b2
    test_segment_ratio<P>("n5",
        2, 0, 7, 0,
        5, 0, 7, 0,
        std::make_pair(3, 5), std::make_pair(1, 1),
        std::make_pair(0, 1), std::make_pair(1, 1),
        5, 0, 7, 0);

    //       a1---------->a2
    //              b2<---b1
    test_segment_ratio<P>("o5",
        2, 0, 7, 0,
        7, 0, 5, 0,
        std::make_pair(3, 5), std::make_pair(1, 1),
        std::make_pair(1, 1), std::make_pair(0, 1),
        5, 0, 7, 0);

    // Generic (overlaps)
    //       a1---------->a2
    //    b1----->b2
    test_segment_ratio<P>("n2",
        2, 0, 7, 0,
        1, 0, 4, 0,
        std::make_pair(0, 1), std::make_pair(2, 5),
        std::make_pair(1, 3), std::make_pair(1, 1),
        2, 0, 4, 0);

    // Same, b reversed
    test_segment_ratio<P>("n2_b",
        2, 0, 7, 0,
        4, 0, 1, 0,
        std::make_pair(0, 1), std::make_pair(2, 5),
        std::make_pair(2, 3), std::make_pair(0, 1),
        2, 0, 4, 0);

    // Same, both reversed
    test_segment_ratio<P>("n2_c",
        7, 0, 2, 0,
        4, 0, 1, 0,
        std::make_pair(3, 5), std::make_pair(1, 1),
        std::make_pair(0, 1), std::make_pair(2, 3),
        4, 0, 2, 0);

    //       a1---------->a2
    //                 b1----->b2
    test_segment_ratio<P>("n6",
        2, 0, 6, 0,
        5, 0, 8, 0,
        std::make_pair(3, 4), std::make_pair(1, 1),
        std::make_pair(0, 1), std::make_pair(1, 3),
        5, 0, 6, 0);

    // Degenerated one
    //       a1---------->a2
    //             b1/b2
    const int ignored = 99;
    test_segment_ratio<P>("degenerated1",
        2, 0, 6, 0,
        5, 0, 5, 0,
        std::make_pair(3, 4), // IP located on 3/4 w.r.t A
        std::make_pair(ignored, 1), // not checked
        std::make_pair(0, 1), // IP located at any place w.r.t B, so 0
        std::make_pair(ignored, 1), // not checked
        5, 0,
        ignored, ignored,
        1);

    test_segment_ratio<P>("degenerated2",
        5, 0, 5, 0,
        2, 0, 6, 0,
        std::make_pair(0, 1), std::make_pair(ignored, 1),
        std::make_pair(3, 4), std::make_pair(ignored, 1),
        5, 0,
        ignored, ignored,
        1);

    // Vertical one like in box_poly5 but in integer
    test_segment_ratio<P>("box_poly5",
        45, 25, 45, 15,
        45, 22, 45, 19,
        std::make_pair(3, 10), std::make_pair(6, 10),
        std::make_pair(0, 1), std::make_pair(1, 1),
        45, 22, 45, 19);
}

int test_main(int, char* [])
{
    // We don't rescale but use integer points as, by nature, robust points
    test_all<bg::model::point<int, 2, bg::cs::cartesian> >();
    test_ratios<bg::model::point<int, 2, bg::cs::cartesian> >();
    return 0;
}
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2	// Unit Test
	3
	4	// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
	5	// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
	6	// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
	7
20effc67	8	// Copyright (c) 2017-2020, Oracle and/or its affiliates.
b32b8144 FG	9	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
b32b8144 FG	10
7c673cae FG	11	// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
	12	// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
	13
	14	// Use, modification and distribution is subject to the Boost Software License,
	15	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	16	// http://www.boost.org/LICENSE_1_0.txt)
	17
	18	#define BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO
	19
	20	#include <geometry_test_common.hpp>
	21
	22	#include <boost/geometry/algorithms/assign.hpp>
	23
b32b8144	24	#include <boost/geometry/strategies/cartesian/intersection.hpp>
7c673cae FG	25	#include <boost/geometry/strategies/intersection_result.hpp>
7c673cae FG	26
20effc67	27	#include <boost/geometry/policies/relate/intersection_policy.hpp>
7c673cae FG	28
7c673cae FG	29	#include <boost/geometry/algorithms/intersection.hpp>
92f5a8d4	30	#include <boost/geometry/algorithms/detail/overlay/segment_as_subrange.hpp>
7c673cae FG	31
	32	#include <boost/geometry/geometries/point.hpp>
	33	#include <boost/geometry/geometries/segment.hpp>
	34
	35
	36	template <typename IntersectionPoints>
	37	static int check(IntersectionPoints const& is,
	38	std::size_t index, double expected_x, double expected_y)
	39	{
	40	if (expected_x != -99 && expected_y != -99 && is.count > index)
	41	{
	42	double x = bg::get<0>(is.intersections[index]);
	43	double y = bg::get<1>(is.intersections[index]);
	44
	45	BOOST_CHECK_CLOSE(x, expected_x, 0.001);
	46	BOOST_CHECK_CLOSE(y, expected_y, 0.001);
	47	return 1;
	48	}
	49	return 0;
	50	}
	51
	52
	53	template <typename P>
	54	static void test_segment_intersection(std::string const& case_id,
	55	int x1, int y1, int x2, int y2,
	56	int x3, int y3, int x4, int y4,
	57	char expected_how, bool expected_opposite,
	58	int expected_arrival1, int expected_arrival2,
	59	int expected_x1, int expected_y1,
	60	int expected_x2 = -99, int expected_y2 = -99)
	61
	62	{
92f5a8d4	63	boost::ignore_unused(case_id);
7c673cae FG	64
	65	typedef bg::model::referring_segment<const P> segment_type;
	66
	67	P p1, p2, p3, p4;
	68	bg::assign_values(p1, x1, y1);
	69	bg::assign_values(p2, x2, y2);
	70	bg::assign_values(p3, x3, y3);
	71	bg::assign_values(p4, x4, y4);
	72
92f5a8d4 TL	73	segment_type s12(p1, p2);
92f5a8d4 TL	74	segment_type s34(p3, p4);
7c673cae	75
92f5a8d4 TL	76	bg::detail::segment_as_subrange<segment_type> sr12(s12);
92f5a8d4 TL	77	bg::detail::segment_as_subrange<segment_type> sr34(s34);
7c673cae	78
92f5a8d4	79	typedef bg::segment_intersection_points<P> result_type;
7c673cae	80
b32b8144 FG	81	typedef bg::policies::relate::segments_intersection_points
	82	<
	83	result_type
	84	> points_policy_type;
	85
7c673cae FG	86	// Get the intersection point (or two points)
7c673cae FG	87	result_type is
b32b8144	88	= bg::strategy::intersection::cartesian_segments<>
92f5a8d4	89	::apply(sr12, sr34, points_policy_type());
7c673cae FG	90
	91	// Get just a character for Left/Right/intersects/etc, purpose is more for debugging
	92	bg::policies::relate::direction_type dir
b32b8144	93	= bg::strategy::intersection::cartesian_segments<>
92f5a8d4	94	::apply(sr12, sr34, bg::policies::relate::segments_direction());
7c673cae FG	95
	96	std::size_t expected_count =
	97	check(is, 0, expected_x1, expected_y1)
	98	+ check(is, 1, expected_x2, expected_y2);
	99
	100	BOOST_CHECK_EQUAL(is.count, expected_count);
	101	BOOST_CHECK_EQUAL(dir.how, expected_how);
	102	BOOST_CHECK_EQUAL(dir.opposite, expected_opposite);
	103	BOOST_CHECK_EQUAL(dir.arrival[0], expected_arrival1);
	104	BOOST_CHECK_EQUAL(dir.arrival[1], expected_arrival2);
	105	}
	106
	107	template <typename P, typename Pair>
	108	static void test_segment_ratio(std::string const& case_id,
	109	int x1, int y1, int x2, int y2,
	110	int x3, int y3, int x4, int y4,
	111	Pair expected_pair_a1, Pair expected_pair_a2,
	112	Pair expected_pair_b1, Pair expected_pair_b2,
	113	int exp_ax1, int exp_ay1, int exp_ax2, int exp_ay2,
	114	std::size_t expected_count = 2)
	115
	116	{
92f5a8d4	117	boost::ignore_unused(case_id);
7c673cae FG	118
	119	typedef bg::model::referring_segment<const P> segment_type;
	120
	121	P p1, p2, p3, p4;
	122	bg::assign_values(p1, x1, y1);
	123	bg::assign_values(p2, x2, y2);
	124	bg::assign_values(p3, x3, y3);
	125	bg::assign_values(p4, x4, y4);
	126
	127	segment_type s12(p1, p2);
	128	segment_type s34(p3, p4);
	129
92f5a8d4 TL	130	bg::detail::segment_as_subrange<segment_type> sr12(s12);
92f5a8d4 TL	131	bg::detail::segment_as_subrange<segment_type> sr34(s34);
7c673cae	132
92f5a8d4	133	typedef bg::segment_intersection_points<P> result_type;
7c673cae	134
b32b8144 FG	135	typedef bg::policies::relate::segments_intersection_points
	136	<
	137	result_type
	138	> points_policy_type;
	139
7c673cae FG	140	// Get the intersection point (or two points)
7c673cae FG	141	result_type is
b32b8144	142	= bg::strategy::intersection::cartesian_segments<>
92f5a8d4 TL	143	::apply(sr12, sr34, points_policy_type());
	144
	145	typedef bg::segment_ratio<typename bg::coordinate_type<P>::type> ratio_type;
7c673cae FG	146
	147	ratio_type expected_a1(expected_pair_a1.first, expected_pair_a1.second);
	148	ratio_type expected_a2(expected_pair_a2.first, expected_pair_a2.second);
	149	ratio_type expected_b1(expected_pair_b1.first, expected_pair_b1.second);
	150	ratio_type expected_b2(expected_pair_b2.first, expected_pair_b2.second);
	151
	152	BOOST_CHECK_EQUAL(is.count, expected_count);
	153
	154	BOOST_CHECK_EQUAL(is.fractions[0].robust_ra, expected_a1);
	155	BOOST_CHECK_EQUAL(is.fractions[0].robust_rb, expected_b1);
	156	BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[0]), exp_ax1);
	157	BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[0]), exp_ay1);
	158
	159	if (expected_count == 2)
	160	{
	161	BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[1]), exp_ax2);
	162	BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[1]), exp_ay2);
	163	BOOST_CHECK_EQUAL(is.fractions[1].robust_ra, expected_a2);
	164	BOOST_CHECK_EQUAL(is.fractions[1].robust_rb, expected_b2);
	165	}
	166	}
	167
	168
	169	template <typename P>
	170	void test_all()
	171	{
	172	// Collinear - non opposite
	173
	174	// a1---------->a2
	175	// b1--->b2
	176	test_segment_intersection<P>("n1",
	177	2, 0, 6, 0,
	178	0, 0, 2, 0,
	179	'a', false, -1, 0,
	180	2, 0);
	181
	182	// a1---------->a2
	183	// b1--->b2
	184	test_segment_intersection<P>("n2",
	185	2, 0, 6, 0,
	186	1, 0, 3, 0,
	187	'c', false, -1, 1,
	188	2, 0, 3, 0);
	189
	190	// a1---------->a2
	191	// b1--->b2
	192	test_segment_intersection<P>("n3",
	193	2, 0, 6, 0,
	194	2, 0, 4, 0,
	195	'c', false, -1, 1,
	196	2, 0, 4, 0);
	197
	198	// a1---------->a2
	199	// b1--->b2
	200	test_segment_intersection<P>("n4",
	201	2, 0, 6, 0,
	202	3, 0, 5, 0,
	203	'c', false, -1, 1,
	204	3, 0, 5, 0);
	205
	206	// a1---------->a2
	207	// b1--->b2
	208	test_segment_intersection<P>("n5",
	209	2, 0, 6, 0,
210	4, 0, 6, 0,
211	'c', false, 0, 0,
212	4, 0, 6, 0);
213
214	// a1---------->a2
215	// b1--->b2
216	test_segment_intersection<P>("n6",
217	2, 0, 6, 0,
218	5, 0, 7, 0,
219	'c', false, 1, -1,
220	5, 0, 6, 0);
221
222	// a1---------->a2
223	// b1--->b2
224	test_segment_intersection<P>("n7",
225	2, 0, 6, 0,
226	6, 0, 8, 0,
227	'a', false, 0, -1,
228	6, 0);
229
230	// Collinear - opposite
231	// a1---------->a2
232	// b2<---b1
233	test_segment_intersection<P>("o1",
234	2, 0, 6, 0,
235	2, 0, 0, 0,
236	'f', true, -1, -1,
237	2, 0);
238
239	// a1---------->a2
240	// b2<---b1
241	test_segment_intersection<P>("o2",
242	2, 0, 6, 0,
243	3, 0, 1, 0,
244	'c', true, -1, -1,
245	2, 0, 3, 0);
246
247	// a1---------->a2
248	// b2<---b1
249	test_segment_intersection<P>("o3",
250	2, 0, 6, 0,
251	4, 0, 2, 0,
252	'c', true, -1, 0,
253	2, 0, 4, 0);
254
255	// a1---------->a2
256	// b2<---b1
257	test_segment_intersection<P>("o4",
258	2, 0, 6, 0,
259	5, 0, 3, 0,
260	'c', true, -1, 1,
261	3, 0, 5, 0);
262
263	// a1---------->a2
264	// b2<---b1
265	test_segment_intersection<P>("o5",
266	2, 0, 6, 0,
267	6, 0, 4, 0,
268	'c', true, 0, 1,
269	4, 0, 6, 0);
270
271	// a1---------->a2
272	// b2<---b1
273	test_segment_intersection<P>("o6",
274	2, 0, 6, 0,
275	7, 0, 5, 0,
276	'c', true, 1, 1,
277	5, 0, 6, 0);
278
279	// a1---------->a2
280	// b2<---b1
281	test_segment_intersection<P>("o7",
282	2, 0, 6, 0,
283	8, 0, 6, 0,
284	't', true, 0, 0,
285	6, 0);
286
287	// a1---------->a2
288	// b1---------->b2
289	test_segment_intersection<P>("e1",
290	2, 0, 6, 0,
291	2, 0, 6, 0,
292	'e', false, 0, 0,
293	2, 0, 6, 0);
294
295	// a1---------->a2
296	// b2<----------b1
297	test_segment_intersection<P>("e1",
298	2, 0, 6, 0,
299	6, 0, 2, 0,
300	'e', true, 0, 0,
301	2, 0, 6, 0);
302
303	// Disjoint (in vertical direction, picture still horizontal)
304	// a2<---a1
305	// b2<---b1
306	test_segment_intersection<P>("case_recursive_boxes_1",
307	10, 7, 10, 6,
308	10, 10, 10, 9,
309	'd', false, 0, 0,
310	-1, -1, -1, -1);
311
312	}
313
314
315	template <typename P>
316	void test_ratios()
317	{
318	// B inside A
319	// a1------------>a2
320	// b1--->b2
321	test_segment_ratio<P>("n4",
322	2, 0, 7, 0,
323	3, 0, 5, 0,
324	std::make_pair(1, 5), std::make_pair(3, 5), // IP located on 1/5, 3/5 w.r.t A
325	std::make_pair(0, 1), std::make_pair(1, 1), // IP located on 0, 1 w.r.t. B
326	// IP's are ordered as in A (currently)
327	3, 0, 5, 0);
328
329	// a1------------>a2
330	// b2<---b1
331	test_segment_ratio<P>("o4",
332	2, 0, 7, 0,
333	5, 0, 3, 0,
334	std::make_pair(1, 5), std::make_pair(3, 5),
335	std::make_pair(1, 1), std::make_pair(0, 1),
336	3, 0, 5, 0);
337
338	// a2<------------a1
339	// b2<---b1
340	test_segment_ratio<P>("o4b",
341	7, 0, 2, 0,
342	5, 0, 3, 0,
343	std::make_pair(2, 5), std::make_pair(4, 5),
344	std::make_pair(0, 1), std::make_pair(1, 1),
345	5, 0, 3, 0);
346
347	// a2<------------a1
348	// b1--->b2
349	test_segment_ratio<P>("o4c",
350	7, 0, 2, 0,
351	3, 0, 5, 0,
352	std::make_pair(2, 5), std::make_pair(4, 5),
353	std::make_pair(1, 1), std::make_pair(0, 1),
354	5, 0, 3, 0);
355
356	// Touch-interior
357	// a1---------->a2
358	// b1--->b2
359	test_segment_ratio<P>("n3",
360	2, 0, 7, 0,
361	2, 0, 4, 0,
362	std::make_pair(0, 1), std::make_pair(2, 5),
363	std::make_pair(0, 1), std::make_pair(1, 1),
364	2, 0, 4, 0);
365
366	// a2<-------------a1
367	// b2<----b1
368	test_segment_ratio<P>("n3b",
369	7, 0, 2, 0,
370	7, 0, 5, 0,
371	std::make_pair(0, 1), std::make_pair(2, 5),
372	std::make_pair(0, 1), std::make_pair(1, 1),
373	7, 0, 5, 0);
374
375
376	// A inside B
377	// a1--->a2
378	// b1------------>b2
379	test_segment_ratio<P>("rn4",
380	3, 0, 5, 0,
381	2, 0, 7, 0,
382	std::make_pair(0, 1), std::make_pair(1, 1),
383	std::make_pair(1, 5), std::make_pair(3, 5),
384	3, 0, 5, 0);
385
386	// a2<---a1
387	// b1------------>b2
388	test_segment_ratio<P>("ro4",
389	5, 0, 3, 0,
390	2, 0, 7, 0,
391	std::make_pair(0, 1), std::make_pair(1, 1),
392	std::make_pair(3, 5), std::make_pair(1, 5),
393	5, 0, 3, 0);
394
395	// a2<---a1
396	// b2<------------b1
397	test_segment_ratio<P>("ro4b",
398	5, 0, 3, 0,
399	7, 0, 2, 0,
400	std::make_pair(0, 1), std::make_pair(1, 1),
401	std::make_pair(2, 5), std::make_pair(4, 5),
402	5, 0, 3, 0);
403
404	// a1--->a2
405	// b2<------------b1
406	test_segment_ratio<P>("ro4c",
407	3, 0, 5, 0,
408	7, 0, 2, 0,
409	std::make_pair(0, 1), std::make_pair(1, 1),
410	std::make_pair(4, 5), std::make_pair(2, 5),
411	3, 0, 5, 0);
412
413	// B inside A, boundaries intersect
414	// We change the coordinates a bit (w.r.t. n3 above) to have it asymmetrical
415	// a1---------->a2
416	// b1--->b2
417	test_segment_ratio<P>("n3",
418	2, 0, 7, 0,
419	2, 0, 4, 0,
420	std::make_pair(0, 1), std::make_pair(2, 5),
421	std::make_pair(0, 1), std::make_pair(1, 1),
422	2, 0, 4, 0);
423
424	// a1---------->a2
425	// b2<---b1
426	test_segment_ratio<P>("o3",
427	2, 0, 7, 0,
428	4, 0, 2, 0,
429	std::make_pair(0, 1), std::make_pair(2, 5),
430	std::make_pair(1, 1), std::make_pair(0, 1),
431	2, 0, 4, 0);
432
433	// a1---------->a2
434	// b1--->b2
435	test_segment_ratio<P>("n5",
436	2, 0, 7, 0,
437	5, 0, 7, 0,
438	std::make_pair(3, 5), std::make_pair(1, 1),
439	std::make_pair(0, 1), std::make_pair(1, 1),
440	5, 0, 7, 0);
441
442	// a1---------->a2
443	// b2<---b1
444	test_segment_ratio<P>("o5",
445	2, 0, 7, 0,
446	7, 0, 5, 0,
447	std::make_pair(3, 5), std::make_pair(1, 1),
448	std::make_pair(1, 1), std::make_pair(0, 1),
449	5, 0, 7, 0);
450
451	// Generic (overlaps)
452	// a1---------->a2
453	// b1----->b2
454	test_segment_ratio<P>("n2",
455	2, 0, 7, 0,
456	1, 0, 4, 0,
457	std::make_pair(0, 1), std::make_pair(2, 5),
458	std::make_pair(1, 3), std::make_pair(1, 1),
459	2, 0, 4, 0);
460
461	// Same, b reversed
462	test_segment_ratio<P>("n2_b",
463	2, 0, 7, 0,
464	4, 0, 1, 0,
465	std::make_pair(0, 1), std::make_pair(2, 5),
466	std::make_pair(2, 3), std::make_pair(0, 1),
467	2, 0, 4, 0);
468
469	// Same, both reversed
470	test_segment_ratio<P>("n2_c",
471	7, 0, 2, 0,
472	4, 0, 1, 0,
473	std::make_pair(3, 5), std::make_pair(1, 1),
474	std::make_pair(0, 1), std::make_pair(2, 3),
475	4, 0, 2, 0);
476
477	// a1---------->a2
478	// b1----->b2
479	test_segment_ratio<P>("n6",
480	2, 0, 6, 0,
481	5, 0, 8, 0,
482	std::make_pair(3, 4), std::make_pair(1, 1),
483	std::make_pair(0, 1), std::make_pair(1, 3),
484	5, 0, 6, 0);
485
486	// Degenerated one
487	// a1---------->a2
488	// b1/b2
489	const int ignored = 99;
490	test_segment_ratio<P>("degenerated1",
491	2, 0, 6, 0,
492	5, 0, 5, 0,
493	std::make_pair(3, 4), // IP located on 3/4 w.r.t A
494	std::make_pair(ignored, 1), // not checked
495	std::make_pair(0, 1), // IP located at any place w.r.t B, so 0
496	std::make_pair(ignored, 1), // not checked
497	5, 0,
498	ignored, ignored,
499	1);
500
501	test_segment_ratio<P>("degenerated2",
502	5, 0, 5, 0,
503	2, 0, 6, 0,
504	std::make_pair(0, 1), std::make_pair(ignored, 1),
505	std::make_pair(3, 4), std::make_pair(ignored, 1),
506	5, 0,
507	ignored, ignored,
508	1);
509
510	// Vertical one like in box_poly5 but in integer
511	test_segment_ratio<P>("box_poly5",
512	45, 25, 45, 15,
513	45, 22, 45, 19,
514	std::make_pair(3, 10), std::make_pair(6, 10),
515	std::make_pair(0, 1), std::make_pair(1, 1),
516	45, 22, 45, 19);
517	}
518
519	int test_main(int, char* [])
520	{
521	// We don't rescale but use integer points as, by nature, robust points
522	test_all<bg::model::point<int, 2, bg::cs::cartesian> >();
523	test_ratios<bg::model::point<int, 2, bg::cs::cartesian> >();
524	return 0;
525	}