Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/RegressionLine.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 <algorithm>
12 #include <cmath>
13 #include <vector>
14
15 #ifdef PRINT_DEBUG
16 #include <cstdio>
17 #endif
18
19 namespace ZXing {
20
21 class RegressionLine
22 {
23 protected:
24 std::vector<PointF> _points;
25 PointF _directionInward;
26 PointF::value_t a = NAN, b = NAN, c = NAN;
27
28 friend PointF intersect(const RegressionLine& l1, const RegressionLine& l2);
29
30 template<typename T> bool evaluate(const PointT<T>* begin, const PointT<T>* end)
31 {
32 auto mean = Reduce(begin, end, PointF()) / std::distance(begin, end);
33 PointF::value_t sumXX = 0, sumYY = 0, sumXY = 0;
34 for (auto p = begin; p != end; ++p) {
35 auto d = *p - mean;
36 sumXX += d.x * d.x;
37 sumYY += d.y * d.y;
38 sumXY += d.x * d.y;
39 }
40 if (sumYY >= sumXX) {
41 auto l = std::sqrt(sumYY * sumYY + sumXY * sumXY);
42 a = +sumYY / l;
43 b = -sumXY / l;
44 } else {
45 auto l = std::sqrt(sumXX * sumXX + sumXY * sumXY);
46 a = +sumXY / l;
47 b = -sumXX / l;
48 }
49 if (dot(_directionInward, normal()) < 0) {
50 a = -a;
51 b = -b;
52 }
53 c = dot(normal(), mean); // (a*mean.x + b*mean.y);
54 return dot(_directionInward, normal()) > 0.5f; // angle between original and new direction is at most 60 degree
55 }
56
57 template <typename T> bool evaluate(const std::vector<PointT<T>>& points) { return evaluate(&points.front(), &points.back() + 1); }
58
59 template <typename T> static auto distance(PointT<T> a, PointT<T> b) { return ZXing::distance(a, b); }
60
61 public:
62 RegressionLine() { _points.reserve(16); } // arbitrary but plausible start size (tiny performance improvement)
63
64 template<typename T> RegressionLine(PointT<T> a, PointT<T> b)
65 {
66 evaluate(std::vector{a, b});
67 }
68
69 template<typename T> RegressionLine(const PointT<T>* b, const PointT<T>* e)
70 {
71 evaluate(b, e);
72 }
73
74 const auto& points() const { return _points; }
75 int length() const { return _points.size() >= 2 ? int(distance(_points.front(), _points.back())) : 0; }
76 bool isValid() const { return !std::isnan(a); }
77 PointF normal() const { return isValid() ? PointF(a, b) : _directionInward; }
78 auto signedDistance(PointF p) const { return dot(normal(), p) - c; }
79 template <typename T> auto distance(PointT<T> p) const { return std::abs(signedDistance(PointF(p))); }
80 PointF project(PointF p) const { return p - signedDistance(p) * normal(); }
81 PointF centroid() const { return Reduce(_points) / _points.size(); }
82
83 void reset()
84 {
85 _points.clear();
86 _directionInward = {};
87 a = b = c = NAN;
88 }
89
90 void add(PointF p) {
91 assert(_directionInward != PointF());
92 _points.push_back(p);
93 if (_points.size() == 1)
94 c = dot(normal(), p);
95 }
96
97 void pop_back() { _points.pop_back(); }
98 void pop_front()
99 {
100 std::rotate(_points.begin(), _points.begin() + 1, _points.end());
101 _points.pop_back();
102 }
103
104 void setDirectionInward(PointF d) { _directionInward = normalized(d); }
105
106 bool evaluate(double maxSignedDist = -1, bool updatePoints = false)
107 {
108 bool ret = evaluate(_points);
109 if (maxSignedDist > 0) {
110 auto points = _points;
111 while (true) {
112 auto old_points_size = points.size();
113 // remove points that are further 'inside' than maxSignedDist or further 'outside' than 2 x maxSignedDist
114 #ifdef __cpp_lib_erase_if
115 std::erase_if(points, [this, maxSignedDist](auto p) {
116 auto sd = this->signedDistance(p);
117 return sd > maxSignedDist || sd < -2 * maxSignedDist;
118 });
119 #else
120 auto end = std::remove_if(points.begin(), points.end(), [this, maxSignedDist](auto p) {
121 auto sd = this->signedDistance(p);
122 return sd > maxSignedDist || sd < -2 * maxSignedDist;
123 });
124 points.erase(end, points.end());
125 #endif
126 // if we threw away too many points, something is off with the line to begin with
127 if (points.size() < old_points_size / 2 || points.size() < 2)
128 return false;
129 if (old_points_size == points.size())
130 break;
131 #ifdef PRINT_DEBUG
132 printf("removed %zu points -> %zu remaining\n", old_points_size - points.size(), points.size());
133 fflush(stdout);
134 #endif
135 ret = evaluate(points);
136 }
137
138 if (updatePoints)
139 _points = std::move(points);
140 }
141 return ret;
142 }
143
144 bool isHighRes() const
145 {
146 PointF min = _points.front(), max = _points.front();
147 for (auto p : _points) {
148 UpdateMinMax(min.x, max.x, p.x);
149 UpdateMinMax(min.y, max.y, p.y);
150 }
151 auto diff = max - min;
152 auto len = maxAbsComponent(diff);
153 auto steps = std::min(std::abs(diff.x), std::abs(diff.y));
154 // due to aliasing we get bad extrapolations if the line is short and too close to vertical/horizontal
155 return steps > 2 || len > 50;
156 }
157 };
158
159 inline PointF intersect(const RegressionLine& l1, const RegressionLine& l2)
160 {
161 assert(l1.isValid() && l2.isValid());
162 auto d = l1.a * l2.b - l1.b * l2.a;
163 auto x = (l1.c * l2.b - l1.b * l2.c) / d;
164 auto y = (l1.a * l2.c - l1.c * l2.a) / d;
165 return {x, y};
166 }
167
168 } // ZXing
169