123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527 |
- // 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, 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_points.hpp>
- #include <boost/geometry/policies/relate/direction.hpp>
- #include <boost/geometry/policies/relate/tupled.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;
- }
|