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

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

// Copyright (c) 2012-2019 Barend Gehrels, Amsterdam, the Netherlands.

// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include "test_buffer.hpp"

static std::string const simplex = "MULTIPOINT((5 5),(7 7))";
static std::string const three = "MULTIPOINT((5 8),(9 8),(7 11))";

// Generated error (extra polygon on top of rest) at distance 14.0:
static std::string const multipoint_a = "MULTIPOINT((39 44),(38 37),(41 29),(15 33),(58 39))";

// Just one with holes at distance ~ 15
static std::string const multipoint_b = "MULTIPOINT((5 56),(98 67),(20 7),(58 60),(10 4),(75 68),(61 68),(75 62),(92 26),(74 6),(67 54),(20 43),(63 30),(45 7))";

// Grid, U-form, generates error for square point at 0.54 (top cells to control rescale)
static std::string const grid_a = "MULTIPOINT(5 0,6 0,7 0,  5 1,7 1,  0 13,8 13)";

static std::string const mysql_report_2015_02_25_1 = "MULTIPOINT(-9 19,9 -6,-4 4,16 -14,-3 16,14 9)";
static std::string const mysql_report_2015_02_25_2 = "MULTIPOINT(-2 11,-15 3,6 4,-14 0,20 -7,-17 -1)";

static std::string const mysql_report_3 = "MULTIPOINT(0 0,0 0,0 0,0 0,0 0)";

template <bool Clockwise, typename P>
void test_all()
{
    typedef bg::model::polygon<P, Clockwise> polygon;
    typedef bg::model::multi_point<P> multi_point_type;

    bg::strategy::buffer::join_round join;
    bg::strategy::buffer::end_flat end_flat;
    typedef bg::strategy::buffer::distance_symmetric
    <
        typename bg::coordinate_type<P>::type
    > distance_strategy;
    bg::strategy::buffer::side_straight side_strategy;

    double const pi = boost::geometry::math::pi<double>();

    test_one<multi_point_type, polygon>("simplex1", simplex, join, end_flat, 2.0 * pi, 1.0);
    test_one<multi_point_type, polygon>("simplex2", simplex, join, end_flat, 22.8372, 2.0);
    test_one<multi_point_type, polygon>("simplex3", simplex, join, end_flat, 44.5692, 3.0);

    test_one<multi_point_type, polygon>("three1", three, join, end_flat, 3.0 * pi, 1.0);
#if defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
    // For no-rescaling, fails in CCW mode
    test_one<multi_point_type, polygon>("three2", three, join, end_flat, 36.7592, 2.0);
#endif
    test_one<multi_point_type, polygon>("three19", three, join, end_flat, 33.6914, 1.9);
    test_one<multi_point_type, polygon>("three21", three, join, end_flat, 39.6394, 2.1);
    test_one<multi_point_type, polygon>("three3", three, join, end_flat, 65.533, 3.0);

    test_one<multi_point_type, polygon>("multipoint_a", multipoint_a, join, end_flat, 2049.98, 14.0);
    test_one<multi_point_type, polygon>("multipoint_b", multipoint_b, join, end_flat, 7109.88, 15.0);
    test_one<multi_point_type, polygon>("multipoint_b1", multipoint_b, join, end_flat, 6911.89, 14.7);
    test_one<multi_point_type, polygon>("multipoint_b2", multipoint_b, join, end_flat, 7174.79, 15.1);

    // Grid tests
    {
        bg::strategy::buffer::point_square point_strategy;

        test_with_custom_strategies<multi_point_type, polygon>("grid_a50",
                grid_a, join, end_flat,
                distance_strategy(0.5), side_strategy, point_strategy, 7.0);

        test_with_custom_strategies<multi_point_type, polygon>("grid_a54",
                grid_a, join, end_flat,
                distance_strategy(0.54), side_strategy, point_strategy, 7.819);
    }

    test_with_custom_strategies<multi_point_type, polygon>("mysql_report_2015_02_25_1_800",
            mysql_report_2015_02_25_1, join, end_flat,
            distance_strategy(6051788), side_strategy,
            bg::strategy::buffer::point_circle(800),
            115057490003226.125, ut_settings(1.0));

    {
        typename bg::strategy::area::services::default_strategy
            <
                typename bg::cs_tag<P>::type
            >::type area_strategy;

        multi_point_type g;
        bg::read_wkt(mysql_report_3, g);
        bg::model::multi_polygon<polygon> buffered;
        test_buffer<polygon>("mysql_report_3", buffered, g,
            bg::strategy::buffer::join_round(36),
            bg::strategy::buffer::end_round(36),
            distance_strategy(1),
            side_strategy,
            bg::strategy::buffer::point_circle(36),
            area_strategy,
            1, 0, 3.12566719800474635, ut_settings(1.0));
    }
}

template <typename P>
void test_many_points_per_circle()
{
    // Tests for large distances / many points in circles.
    // Before Boost 1.58, this would (seem to) hang. It is solved by using monotonic sections in get_turns for buffer
    // This is more time consuming, only calculate this for counter clockwise
    // Reported by MySQL 2015-02-25
    //   SELECT ST_ASTEXT(ST_BUFFER(ST_GEOMFROMTEXT(''), 6051788, ST_BUFFER_STRATEGY('point_circle', 83585)));
    //   SELECT ST_ASTEXT(ST_BUFFER(ST_GEOMFROMTEXT(''), 5666962, ST_BUFFER_STRATEGY('point_circle', 46641))) ;

    typedef bg::model::polygon<P, false> polygon;
    typedef bg::model::multi_point<P> multi_point_type;

    bg::strategy::buffer::join_round join;
    bg::strategy::buffer::end_flat end_flat;
    typedef bg::strategy::buffer::distance_symmetric
    <
        typename bg::coordinate_type<P>::type
    > distance_strategy;
    bg::strategy::buffer::side_straight side_strategy;

    using bg::strategy::buffer::point_circle;

#if ! defined(BOOST_GEOMETRY_USE_RESCALING)
    double const tolerance = 1000.0;
#else
    double const tolerance = 1.0;
#endif

    // Area should be somewhat larger (~>) than pi*distance^2
    // 6051788: area ~> 115058122875258

    // Strategies with many points, which are (very) slow in debug mode
    test_with_custom_strategies<multi_point_type, polygon>(
            "mysql_report_2015_02_25_1_8000",
            mysql_report_2015_02_25_1, join, end_flat,
            distance_strategy(6051788), side_strategy, point_circle(8000),
            115058661065242.812, ut_settings(10.0 * tolerance));

    // Expectations:
    // 115058672785641.031
    // 115058672785680.281
    // 115058672785679.922
    test_with_custom_strategies<multi_point_type, polygon>(
            "mysql_report_2015_02_25_1",
            mysql_report_2015_02_25_1, join, end_flat,
            distance_strategy(6051788), side_strategy, point_circle(83585),
            115058672785660.0, ut_settings(25.0 * tolerance));

    // Takes about 7 seconds in release mode
    // Expectations:
    // 115058672880035.391
    // 115058672879944.547
    // 115058672879920.484
    test_with_custom_strategies<multi_point_type, polygon>(
            "mysql_report_2015_02_25_1_250k",
            mysql_report_2015_02_25_1, join, end_flat,
            distance_strategy(6051788), side_strategy, point_circle(250000),
            115058672879977.0, ut_settings(150.0 * tolerance));

#if defined(BOOST_GEOMETRY_BUFFER_INCLUDE_SLOW_TESTS)
    // Takes about 110 seconds in release mode
    test_with_custom_strategies<multi_point_type, polygon>(
            "mysql_report_2015_02_25_1_800k",
            mysql_report_2015_02_25_1, join, end_flat,
            distance_strategy(6051788), side_strategy, point_circle(800000),
            115058672871849.219, ut_settings(tolerance));
#endif

    // 5666962: area ~> 100890546298964
    // Expectations:
    // 100891031341796.875
    // 100891031341794.766
    // 100891031341794.078
    test_with_custom_strategies<multi_point_type, polygon>(
            "mysql_report_2015_02_25_2",
            mysql_report_2015_02_25_2, join, end_flat,
            distance_strategy(5666962), side_strategy, point_circle(46641),
            100891031341795.0, ut_settings(200.0 * tolerance));

    // Multipoint b with large distances/many points
    // Area ~> pi * 10x

    // Expectations:
    // 3141871558222.398
    // 3141871558231.5166
    // 3141871558231.48926

    test_with_custom_strategies<multi_point_type, polygon>(
            "multipoint_b_50k",
            multipoint_b, join, end_flat,
            distance_strategy(1000000), side_strategy, point_circle(50000),
            3141871558227.0, ut_settings(40.0 * tolerance));

#if defined(BOOST_GEOMETRY_BUFFER_INCLUDE_SLOW_TESTS)
    // Tests optimization min/max radius
    // Takes about 55 seconds in release mode
    test_with_custom_strategies<multi_point_type, polygon>(
            "multipoint_b_500k",
            multipoint_b, join, end_flat,
            distance_strategy(10000000), side_strategy, point_circle(500000),
            314162054419515.562, ut_settings((tolerance));
#endif
}

int test_main(int, char* [])
{
    BoostGeometryWriteTestConfiguration();

    test_all<true, bg::model::point<default_test_type, 2, bg::cs::cartesian> >();

#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_ORDER)
    test_all<false, bg::model::point<default_test_type, 2, bg::cs::cartesian> >();
#endif

#if defined(BOOST_GEOMETRY_COMPILER_MODE_RELEASE) && ! defined(BOOST_GEOMETRY_COMPILER_MODE_DEBUG)
    test_many_points_per_circle<bg::model::point<double, 2, bg::cs::cartesian> >();
#else
    std::cout << "Skipping some tests in debug or unknown mode" << std::endl;
#endif

    return 0;
}
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2	// Unit Test
	3
92f5a8d4	4	// Copyright (c) 2012-2019 Barend Gehrels, Amsterdam, the Netherlands.
7c673cae FG	5
	6	// Use, modification and distribution is subject to the Boost Software License,
	7	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	8	// http://www.boost.org/LICENSE_1_0.txt)
	9
92f5a8d4	10	#include "test_buffer.hpp"
7c673cae FG	11
	12	static std::string const simplex = "MULTIPOINT((5 5),(7 7))";
	13	static std::string const three = "MULTIPOINT((5 8),(9 8),(7 11))";
	14
	15	// Generated error (extra polygon on top of rest) at distance 14.0:
	16	static std::string const multipoint_a = "MULTIPOINT((39 44),(38 37),(41 29),(15 33),(58 39))";
	17
	18	// Just one with holes at distance ~ 15
	19	static std::string const multipoint_b = "MULTIPOINT((5 56),(98 67),(20 7),(58 60),(10 4),(75 68),(61 68),(75 62),(92 26),(74 6),(67 54),(20 43),(63 30),(45 7))";
	20
	21	// Grid, U-form, generates error for square point at 0.54 (top cells to control rescale)
	22	static std::string const grid_a = "MULTIPOINT(5 0,6 0,7 0, 5 1,7 1, 0 13,8 13)";
	23
	24	static std::string const mysql_report_2015_02_25_1 = "MULTIPOINT(-9 19,9 -6,-4 4,16 -14,-3 16,14 9)";
	25	static std::string const mysql_report_2015_02_25_2 = "MULTIPOINT(-2 11,-15 3,6 4,-14 0,20 -7,-17 -1)";
	26
b32b8144 FG	27	static std::string const mysql_report_3 = "MULTIPOINT(0 0,0 0,0 0,0 0,0 0)";
b32b8144 FG	28
7c673cae FG	29	template <bool Clockwise, typename P>
	30	void test_all()
	31	{
	32	typedef bg::model::polygon<P, Clockwise> polygon;
	33	typedef bg::model::multi_point<P> multi_point_type;
	34
	35	bg::strategy::buffer::join_round join;
	36	bg::strategy::buffer::end_flat end_flat;
	37	typedef bg::strategy::buffer::distance_symmetric
	38	<
	39	typename bg::coordinate_type<P>::type
	40	> distance_strategy;
	41	bg::strategy::buffer::side_straight side_strategy;
	42
	43	double const pi = boost::geometry::math::pi<double>();
	44
b32b8144 FG	45	test_one<multi_point_type, polygon>("simplex1", simplex, join, end_flat, 2.0 * pi, 1.0);
	46	test_one<multi_point_type, polygon>("simplex2", simplex, join, end_flat, 22.8372, 2.0);
	47	test_one<multi_point_type, polygon>("simplex3", simplex, join, end_flat, 44.5692, 3.0);
7c673cae	48
b32b8144	49	test_one<multi_point_type, polygon>("three1", three, join, end_flat, 3.0 * pi, 1.0);
92f5a8d4	50	#if defined(BOOST_GEOMETRY_USE_RESCALING) \|\| defined(BOOST_GEOMETRY_TEST_FAILURES)
7c673cae	51	// For no-rescaling, fails in CCW mode
b32b8144	52	test_one<multi_point_type, polygon>("three2", three, join, end_flat, 36.7592, 2.0);
7c673cae	53	#endif
b32b8144 FG	54	test_one<multi_point_type, polygon>("three19", three, join, end_flat, 33.6914, 1.9);
	55	test_one<multi_point_type, polygon>("three21", three, join, end_flat, 39.6394, 2.1);
	56	test_one<multi_point_type, polygon>("three3", three, join, end_flat, 65.533, 3.0);
7c673cae	57
b32b8144 FG	58	test_one<multi_point_type, polygon>("multipoint_a", multipoint_a, join, end_flat, 2049.98, 14.0);
	59	test_one<multi_point_type, polygon>("multipoint_b", multipoint_b, join, end_flat, 7109.88, 15.0);
	60	test_one<multi_point_type, polygon>("multipoint_b1", multipoint_b, join, end_flat, 6911.89, 14.7);
	61	test_one<multi_point_type, polygon>("multipoint_b2", multipoint_b, join, end_flat, 7174.79, 15.1);
7c673cae FG	62
	63	// Grid tests
	64	{
	65	bg::strategy::buffer::point_square point_strategy;
	66
	67	test_with_custom_strategies<multi_point_type, polygon>("grid_a50",
	68	grid_a, join, end_flat,
	69	distance_strategy(0.5), side_strategy, point_strategy, 7.0);
	70
7c673cae FG	71	test_with_custom_strategies<multi_point_type, polygon>("grid_a54",
	72	grid_a, join, end_flat,
	73	distance_strategy(0.54), side_strategy, point_strategy, 7.819);
7c673cae FG	74	}
	75
	76	test_with_custom_strategies<multi_point_type, polygon>("mysql_report_2015_02_25_1_800",
	77	mysql_report_2015_02_25_1, join, end_flat,
	78	distance_strategy(6051788), side_strategy,
b32b8144 FG	79	bg::strategy::buffer::point_circle(800),
	80	115057490003226.125, ut_settings(1.0));
	81
	82	{
92f5a8d4 TL	83	typename bg::strategy::area::services::default_strategy
	84	<
	85	typename bg::cs_tag<P>::type
	86	>::type area_strategy;
	87
b32b8144 FG	88	multi_point_type g;
b32b8144 FG	89	bg::read_wkt(mysql_report_3, g);
92f5a8d4 TL	90	bg::model::multi_polygon<polygon> buffered;
92f5a8d4 TL	91	test_buffer<polygon>("mysql_report_3", buffered, g,
b32b8144 FG	92	bg::strategy::buffer::join_round(36),
	93	bg::strategy::buffer::end_round(36),
	94	distance_strategy(1),
	95	side_strategy,
	96	bg::strategy::buffer::point_circle(36),
92f5a8d4	97	area_strategy,
b32b8144 FG	98	1, 0, 3.12566719800474635, ut_settings(1.0));
b32b8144 FG	99	}
7c673cae FG	100	}
	101
	102	template <typename P>
	103	void test_many_points_per_circle()
	104	{
	105	// Tests for large distances / many points in circles.
	106	// Before Boost 1.58, this would (seem to) hang. It is solved by using monotonic sections in get_turns for buffer
	107	// This is more time consuming, only calculate this for counter clockwise
	108	// Reported by MySQL 2015-02-25
	109	// SELECT ST_ASTEXT(ST_BUFFER(ST_GEOMFROMTEXT(''), 6051788, ST_BUFFER_STRATEGY('point_circle', 83585)));
	110	// SELECT ST_ASTEXT(ST_BUFFER(ST_GEOMFROMTEXT(''), 5666962, ST_BUFFER_STRATEGY('point_circle', 46641))) ;
	111
	112	typedef bg::model::polygon<P, false> polygon;
	113	typedef bg::model::multi_point<P> multi_point_type;
	114
	115	bg::strategy::buffer::join_round join;
	116	bg::strategy::buffer::end_flat end_flat;
	117	typedef bg::strategy::buffer::distance_symmetric
	118	<
	119	typename bg::coordinate_type<P>::type
	120	> distance_strategy;
	121	bg::strategy::buffer::side_straight side_strategy;
	122
	123	using bg::strategy::buffer::point_circle;
	124
92f5a8d4	125	#if ! defined(BOOST_GEOMETRY_USE_RESCALING)
b32b8144	126	double const tolerance = 1000.0;
7c673cae	127	#else
b32b8144	128	double const tolerance = 1.0;
7c673cae FG	129	#endif
	130
	131	// Area should be somewhat larger (~>) than pi*distance^2
	132	// 6051788: area ~> 115058122875258
	133
	134	// Strategies with many points, which are (very) slow in debug mode
	135	test_with_custom_strategies<multi_point_type, polygon>(
	136	"mysql_report_2015_02_25_1_8000",
	137	mysql_report_2015_02_25_1, join, end_flat,
	138	distance_strategy(6051788), side_strategy, point_circle(8000),
b32b8144	139	115058661065242.812, ut_settings(10.0 * tolerance));
7c673cae FG	140
	141	// Expectations:
	142	// 115058672785641.031
	143	// 115058672785680.281
	144	// 115058672785679.922
	145	test_with_custom_strategies<multi_point_type, polygon>(
	146	"mysql_report_2015_02_25_1",
	147	mysql_report_2015_02_25_1, join, end_flat,
	148	distance_strategy(6051788), side_strategy, point_circle(83585),
b32b8144	149	115058672785660.0, ut_settings(25.0 * tolerance));
7c673cae FG	150
	151	// Takes about 7 seconds in release mode
	152	// Expectations:
	153	// 115058672880035.391
	154	// 115058672879944.547
	155	// 115058672879920.484
	156	test_with_custom_strategies<multi_point_type, polygon>(
	157	"mysql_report_2015_02_25_1_250k",
	158	mysql_report_2015_02_25_1, join, end_flat,
	159	distance_strategy(6051788), side_strategy, point_circle(250000),
11fdf7f2	160	115058672879977.0, ut_settings(150.0 * tolerance));
7c673cae FG	161
	162	#if defined(BOOST_GEOMETRY_BUFFER_INCLUDE_SLOW_TESTS)
	163	// Takes about 110 seconds in release mode
	164	test_with_custom_strategies<multi_point_type, polygon>(
	165	"mysql_report_2015_02_25_1_800k",
	166	mysql_report_2015_02_25_1, join, end_flat,
	167	distance_strategy(6051788), side_strategy, point_circle(800000),
b32b8144	168	115058672871849.219, ut_settings(tolerance));
7c673cae FG	169	#endif
	170
	171	// 5666962: area ~> 100890546298964
	172	// Expectations:
	173	// 100891031341796.875
	174	// 100891031341794.766
	175	// 100891031341794.078
	176	test_with_custom_strategies<multi_point_type, polygon>(
	177	"mysql_report_2015_02_25_2",
	178	mysql_report_2015_02_25_2, join, end_flat,
	179	distance_strategy(5666962), side_strategy, point_circle(46641),
11fdf7f2	180	100891031341795.0, ut_settings(200.0 * tolerance));
7c673cae FG	181
	182	// Multipoint b with large distances/many points
	183	// Area ~> pi * 10x
	184
	185	// Expectations:
	186	// 3141871558222.398
	187	// 3141871558231.5166
	188	// 3141871558231.48926
	189
	190	test_with_custom_strategies<multi_point_type, polygon>(
	191	"multipoint_b_50k",
	192	multipoint_b, join, end_flat,
	193	distance_strategy(1000000), side_strategy, point_circle(50000),
11fdf7f2	194	3141871558227.0, ut_settings(40.0 * tolerance));
7c673cae FG	195
	196	#if defined(BOOST_GEOMETRY_BUFFER_INCLUDE_SLOW_TESTS)
	197	// Tests optimization min/max radius
	198	// Takes about 55 seconds in release mode
	199	test_with_custom_strategies<multi_point_type, polygon>(
	200	"multipoint_b_500k",
	201	multipoint_b, join, end_flat,
	202	distance_strategy(10000000), side_strategy, point_circle(500000),
b32b8144	203	314162054419515.562, ut_settings((tolerance));
7c673cae FG	204	#endif
	205	}
	206
	207	int test_main(int, char* [])
	208	{
92f5a8d4 TL	209	BoostGeometryWriteTestConfiguration();
	210
	211	test_all<true, bg::model::point<default_test_type, 2, bg::cs::cartesian> >();
	212
	213	#if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_ORDER)
	214	test_all<false, bg::model::point<default_test_type, 2, bg::cs::cartesian> >();
	215	#endif
7c673cae FG	216
	217	#if defined(BOOST_GEOMETRY_COMPILER_MODE_RELEASE) && ! defined(BOOST_GEOMETRY_COMPILER_MODE_DEBUG)
	218	test_many_points_per_circle<bg::model::point<double, 2, bg::cs::cartesian> >();
	219	#else
	220	std::cout << "Skipping some tests in debug or unknown mode" << std::endl;
	221	#endif
	222
	223	return 0;
	224	}