1 #include <mbgl/text/check_max_angle.hpp>
2 #include <mbgl/geometry/anchor.hpp>
3 #include <mbgl/util/math.hpp>
4
5 #include <queue>
6
7 namespace mbgl{
8
9 struct Corner {
Cornermbgl::Corner10 Corner(float _distance, float _angleDelta) :
11 distance(_distance), angleDelta(_angleDelta) {}
12 float distance;
13 float angleDelta;
14 };
15
checkMaxAngle(const GeometryCoordinates & line,const Anchor & anchor,const float labelLength,const float windowSize,const float maxAngle)16 bool checkMaxAngle(const GeometryCoordinates& line,
17 const Anchor& anchor,
18 const float labelLength,
19 const float windowSize,
20 const float maxAngle) {
21 // horizontal labels always pass
22 if (anchor.segment < 0) return true;
23
24 GeometryCoordinate anchorPoint = convertPoint<int16_t>(anchor.point);
25 GeometryCoordinate &p = anchorPoint;
26 int index = anchor.segment + 1;
27 float anchorDistance = 0;
28
29 // move backwards along the line to the first segment the label appears on
30 while (anchorDistance > -labelLength / 2) {
31 index--;
32
33 // there isn't enough room for the label after the beginning of the line
34 if (index < 0) return false;
35
36 anchorDistance -= util::dist<float>(line[index], p);
37 p = line[index];
38 }
39
40 anchorDistance += util::dist<float>(line[index], line[index + 1]);
41 index++;
42
43 // store recent corners and their total angle difference
44 std::queue<Corner> recentCorners;
45 float recentAngleDelta = 0;
46
47 // move forwards by the length of the label and check angles along the way
48 while (anchorDistance < labelLength / 2) {
49
50 // there isn't enough room for the label before the end of the line
51 if (index + 1 >= (int)line.size()) return false;
52
53 auto& prev = line[index - 1];
54 auto& current = line[index];
55 auto& next = line[index + 1];
56
57 float angleDelta = util::angle_to(prev, current) - util::angle_to(current, next);
58 // restrict angle to -pi..pi range
59 angleDelta = std::fabs(std::fmod(angleDelta + 3 * M_PI, M_PI * 2) - M_PI);
60
61 recentCorners.emplace(anchorDistance, angleDelta);
62 recentAngleDelta += angleDelta;
63
64 // remove corners that are far enough away from the list of recent anchors
65 while (anchorDistance - recentCorners.front().distance > windowSize) {
66 recentAngleDelta -= recentCorners.front().angleDelta;
67 recentCorners.pop();
68 }
69
70 // the sum of angles within the window area exceeds the maximum allowed value. check fails.
71 if (recentAngleDelta > maxAngle) return false;
72
73 index++;
74 anchorDistance += util::dist<float>(current, next);
75 }
76
77 // no part of the line had an angle greater than the maximum allowed. check passes.
78 return true;
79 }
80
81 } // namespace mbgl
82