1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
// Boost.Geometry
// Unit Test
// Copyright (c) 2021 Barend Gehrels, Amsterdam, the Netherlands.
// This file was modified by Oracle on 2021-2024.
// Modifications copyright (c) 2021-2024, Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// 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/get_clusters.hpp>
#include <boost/geometry/algorithms/area.hpp>
#include <boost/geometry/algorithms/is_valid.hpp>
#include <boost/geometry/strategies/strategies.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/util/condition.hpp>
#include <boost/geometry/io/wkt/wkt.hpp>
#include <vector>
#include <map>
template <typename Turn, typename Point>
Turn make_turn(Point const& p)
{
Turn result;
result.point = p;
return result;
}
template <typename Point>
void do_test(std::string const& case_id,
std::vector<Point> const& points,
std::size_t expected_cluster_count)
{
using coor_type = typename bg::coordinate_type<Point>::type;
using turn_info = bg::detail::overlay::turn_info
<
Point,
typename bg::segment_ratio_type<Point>::type
>;
using cluster_type = std::map
<
bg::signed_size_type,
bg::detail::overlay::cluster_info
>;
std::vector<turn_info> turns;
for (auto const& p : points)
{
turns.push_back(make_turn<turn_info>(p));
}
cluster_type clusters;
bg::detail::overlay::get_clusters(turns, clusters);
BOOST_CHECK_MESSAGE(expected_cluster_count == clusters.size(),
"Case: " << case_id
<< " ctype: " << string_from_type<coor_type>::name()
<< " expected: " << expected_cluster_count
<< " detected: " << clusters.size());
}
template <typename Point>
void test_get_clusters()
{
do_test<Point>("no", {{1.0, 1.0}, {1.0, 2.0}}, 0);
do_test<Point>("simplex", {{1.0, 1.0}, {1.0, 1.0}}, 1);
// Tests below come from realtime cases
do_test<Point>("buffer1", {{2, 1},{12, 13},{6, 5},{8, 9},{1, 1},{2, 1},{1, 13},{2, 13},{5, 5},{6, 5},{5, 9},{6, 9},{13, 1},{12, 1},{13, 13},{12, 13},{9, 5},{8, 5},{9, 9},{8, 9},{1, 12},{5, 8},{1, 2},{5, 6},{1, 12},{5, 8},{13, 2},{9, 6},{13, 2},{9, 6},{13, 12},{9, 8}},
8);
do_test<Point>("buffer2", {{2.72426406871, 1.7},{2.72426406871, 4.7},{2.3, 3.12426406871},{2.3, 3.7},{2.7, 2.72426406871},{2.7, 3.7},{2.72426406871, 3.7},{2.72426406871, 1.7},{0.7, 3.12426406871},{0.7, 1.7},{1.7, 0.7},{1.7, 2.3},{1.7, 2.7},{1.3, 2.3},{1.3, 2.7},{1.7, 5.72426406871},{1.7, 5.72426406871},{1.7, 4.7},{1.7, 5},{1.7, 4.3},{3.7, 3.72426406871},{3.72426406871, 3.7},{3.7, 3.7},{3.72426406871, 1.7},{3, 1.7},{3.7, 3.7},{3.7, 5.72426406871},{4.72426406871, 4.7},{3.7, 4.72426406871},{3.7, 4.72426406871},{3.7, 4.7},{3.7, 4.7},{3.7, 4.7},{3.7, 4.7},{3.7, 5},{3.7, 5.72426406871}},
6);
do_test<Point>("buffer3", {{6.41421356237, 5},{6.41421356236, 5},{6.70710678119, 5.29289321881},{6.41421356237, 5},{6, 5},{6.41421356238, 5},{7, 5},{8, 10},{8.41421356237, 10},{8, 9.58578643763},{8.41421356237, 10},{7.41421356237, 9},{7.41421356237, 9},{7, 5.58578643763},{7, 5.58578643763},{6, 5},{6, 5},{6, 5},{6, 5},{6, 5},{6, 6},{4, 6},{4, 6},{3.41421356237, 3},{3, 5},{6, 5},{5, 3},{4, 6},{4, 6},{4, 7},{4, 8},{10.9142135624, 5.5},{8, 5},{10.4142135624, 5},{8, 5},{8, 3.58578643763},{8, 5},{9.41421356237, 7},{9.41421356237, 7},{8.91421356237, 7.5},{10, 7},{8, 9},{7.41421356237, 9},{11, 7}},
8);
}
template <typename Point>
void test_get_clusters_border_cases(typename bg::coordinate_type<Point>::type eps)
{
do_test<Point>("borderx_no", {{1, 1}, {1, 2}, {1 + eps * 10, 1}}, 0);
do_test<Point>("borderx_yes", {{1, 1}, {1, 2}, {1 + eps, 1}}, 1);
do_test<Point>("bordery_no", {{1, 1}, {2, 1}, {1 + eps * 10, 1}}, 0);
do_test<Point>("bordery_yes", {{1, 1}, {2, 1}, {1 + eps, 1}}, 1);
}
int test_main(int, char* [])
{
constexpr bool has_long_double = sizeof(long double) > sizeof(double);
using fp = bg::model::point<float, 2, bg::cs::cartesian>;
using dp = bg::model::point<double, 2, bg::cs::cartesian>;
using ep = bg::model::point<long double, 2, bg::cs::cartesian>;
test_get_clusters<fp>();
test_get_clusters<dp>();
test_get_clusters<ep>();
// These constant relate to the (earlier) thresholds in get_clusters.hpp,
// and the used floating point type.
// (thresholds are now replaced by common_approximately_equals_epsilon_multiplier)
test_get_clusters_border_cases<fp>(1.0e-5);
test_get_clusters_border_cases<dp>(1.0e-14);
if (BOOST_GEOMETRY_CONDITION(has_long_double))
{
test_get_clusters_border_cases<ep>(1.0e-17);
}
return 0;
}
|
