Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/Quadrilateral.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*
2 * Copyright 2020 Axel Waggershauser
3 */
4 // SPDX-License-Identifier: Apache-2.0
5
6 #pragma once
7
8 #include "Point.h"
9 #include "ZXAlgorithms.h"
10
11 #include <array>
12 #include <cmath>
13 #include <string>
14
15 namespace ZXing {
16
17 template <typename T>
18 class Quadrilateral : public std::array<T, 4>
19 {
20 using Base = std::array<T, 4>;
21 using Base::at;
22 public:
23 using Point = T;
24
25 Quadrilateral() = default;
26 Quadrilateral(T tl, T tr, T br, T bl) : Base{tl, tr, br, bl} {}
27 template <typename U>
28 Quadrilateral(PointT<U> tl, PointT<U> tr, PointT<U> br, PointT<U> bl)
29 : Quadrilateral(Point(tl), Point(tr), Point(br), Point(bl))
30 {}
31
32 constexpr Point topLeft() const noexcept { return at(0); }
33 constexpr Point topRight() const noexcept { return at(1); }
34 constexpr Point bottomRight() const noexcept { return at(2); }
35 constexpr Point bottomLeft() const noexcept { return at(3); }
36
37 double orientation() const
38 {
39 auto centerLine = (topRight() + bottomRight()) - (topLeft() + bottomLeft());
40 if (centerLine == Point{})
41 return 0.;
42 auto centerLineF = normalized(centerLine);
43 return std::atan2(centerLineF.y, centerLineF.x);
44 }
45 };
46
47 using QuadrilateralF = Quadrilateral<PointF>;
48 using QuadrilateralI = Quadrilateral<PointI>;
49
50 template <typename PointT = PointF>
51 Quadrilateral<PointT> Rectangle(int width, int height, typename PointT::value_t margin = 0)
52 {
53 return {
54 PointT{margin, margin}, {width - margin, margin}, {width - margin, height - margin}, {margin, height - margin}};
55 }
56
57 template <typename PointT = PointF>
58 Quadrilateral<PointT> CenteredSquare(int size)
59 {
60 return Scale(Quadrilateral(PointT{-1, -1}, {1, -1}, {1, 1}, {-1, 1}), size / 2);
61 }
62
63 template <typename PointT = PointI>
64 Quadrilateral<PointT> Line(int y, int xStart, int xStop)
65 {
66 return {PointT{xStart, y}, {xStop, y}, {xStop, y}, {xStart, y}};
67 }
68
69 template <typename PointT>
70 bool IsConvex(const Quadrilateral<PointT>& poly)
71 {
72 const int N = Size(poly);
73 bool sign = false;
74
75 typename PointT::value_t m = INFINITY, M = 0;
76
77 for(int i = 0; i < N; i++)
78 {
79 auto d1 = poly[(i + 2) % N] - poly[(i + 1) % N];
80 auto d2 = poly[i] - poly[(i + 1) % N];
81 auto cp = cross(d1, d2);
82
83 // TODO: see if the isInside check for all boundary points in GridSampler is still required after fixing the wrong fabs()
84 // application in the following line
85 UpdateMinMax(m, M, std::fabs(cp));
86
87 if (i == 0)
88 sign = cp > 0;
89 else if (sign != (cp > 0))
90 return false;
91 }
92
93 // It turns out being convex is not enough to prevent a "numerical instability"
94 // that can cause the corners being projected inside the image boundaries but
95 // some points near the corners being projected outside. This has been observed
96 // where one corner is almost in line with two others. The M/m ratio is below 2
97 // for the complete existing sample set. For very "skewed" QRCodes a value of
98 // around 3 is realistic. A value of 14 has been observed to trigger the
99 // instability.
100 return M / m < 4.0;
101 }
102
103 template <typename PointT>
104 Quadrilateral<PointT> Scale(const Quadrilateral<PointT>& q, int factor)
105 {
106 return {factor * q[0], factor * q[1], factor * q[2], factor * q[3]};
107 }
108
109 template <typename PointT>
110 PointT Center(const Quadrilateral<PointT>& q)
111 {
112 return Reduce(q) / Size(q);
113 }
114
115 template <typename PointT>
116 Quadrilateral<PointT> RotatedCorners(const Quadrilateral<PointT>& q, int n = 1, bool mirror = false)
117 {
118 Quadrilateral<PointT> res;
119 std::rotate_copy(q.begin(), q.begin() + ((n + 4) % 4), q.end(), res.begin());
120 if (mirror)
121 std::swap(res[1], res[3]);
122 return res;
123 }
124
125 template <typename PointT>
126 bool IsInside(const PointT& p, const Quadrilateral<PointT>& q)
127 {
128 // Test if p is on the same side (right or left) of all polygon segments
129 int pos = 0, neg = 0;
130 for (int i = 0; i < Size(q); ++i)
131 (cross(p - q[i], q[(i + 1) % Size(q)] - q[i]) < 0 ? neg : pos)++;
132 return pos == 0 || neg == 0;
133 }
134
135 template <typename PointT>
136 Quadrilateral<PointT> BoundingBox(const Quadrilateral<PointT>& q)
137 {
138 auto [minX, maxX] = std::minmax({q[0].x, q[1].x, q[2].x, q[3].x});
139 auto [minY, maxY] = std::minmax({q[0].y, q[1].y, q[2].y, q[3].y});
140 return {PointT{minX, minY}, {maxX, minY}, {maxX, maxY}, {minX, maxY}};
141 }
142
143 template <typename PointT>
144 bool HaveIntersectingBoundingBoxes(const Quadrilateral<PointT>& a, const Quadrilateral<PointT>& b)
145 {
146 auto bba = BoundingBox(a), bbb = BoundingBox(b);
147
148 bool x = bbb.topRight().x < bba.topLeft().x || bbb.topLeft().x > bba.topRight().x;
149 bool y = bbb.bottomLeft().y < bba.topLeft().y || bbb.topLeft().y > bba.bottomLeft().y;
150 return !(x || y);
151 }
152
153 template <typename PointT>
154 Quadrilateral<PointT> Blend(const Quadrilateral<PointT>& a, const Quadrilateral<PointT>& b)
155 {
156 auto dist2First = [r = a[0]](auto s, auto t) { return distance(s, r) < distance(t, r); };
157 // rotate points such that the the two topLeft points are closest to each other
158 auto offset = std::min_element(b.begin(), b.end(), dist2First) - b.begin();
159
160 Quadrilateral<PointT> res;
161 for (int i = 0; i < 4; ++i)
162 res[i] = (a[i] + b[(i + offset) % 4]) / 2;
163
164 return res;
165 }
166
167 template <typename T>
168 std::string ToString(const Quadrilateral<PointT<T>>& points)
169 {
170 std::string res;
171 for (const auto& p : points)
172 res += std::to_string(p.x) + "x" + std::to_string(p.y) + (&p == &points.back() ? "" : " ");
173 return res;
174 }
175
176 } // ZXing
177