5 * Created by Ralf Kistner on 7/12/2009.
6 * Copyright 2008 ZXing authors All rights reserved.
8 * Licensed under the Apache License, Version 2.0 (the "License");
9 * you may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
12 * http://www.apache.org/licenses/LICENSE-2.0
14 * Unless required by applicable law or agreed to in writing, software
15 * distributed under the License is distributed on an "AS IS" BASIS,
16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17 * See the License for the specific language governing permissions and
18 * limitations under the License.
21 #include <zxing/common/EdgeDetector.h>
28 namespace EdgeDetector {
30 void findEdgePoints(std::vector<Point>& points, const BitMatrix& image, Point start, Point end, bool invert, int skip, float deviation) {
31 float xdist = end.x - start.x;
32 float ydist = end.y - start.y;
33 float length = sqrt(xdist * xdist + ydist * ydist);
38 if (abs(xdist) > abs(ydist)) {
43 var = int(abs(deviation * length / xdist));
45 float dy = ydist / xdist * skip;
46 bool left = (skip < 0) ^ invert;
49 int steps = int(xdist / skip);
50 for (int i = 0; i < steps; i++) {
52 if (x < 0 || x >= (int)image.getWidth())
53 continue; // In case we start off the edge
54 int my = int(start.y + dy * i);
55 int ey = min(my + var + 1, (int)image.getHeight() - 1);
56 int sy = max(my - var, 0);
57 for (int y = sy + 1; y < ey; y++) {
59 if (image.get(x, y) && !image.get(x, y + 1)) {
60 points.push_back(Point(x, y + 0.5f));
63 if (!image.get(x, y) && image.get(x, y + 1)) {
64 points.push_back(Point(x, y + 0.5f));
74 var = int(abs(deviation * length / ydist));
76 float dx = xdist / ydist * skip;
77 bool down = (skip > 0) ^ invert;
80 int steps = int(ydist / skip);
81 for (int i = 0; i < steps; i++) {
83 if (y < 0 || y >= (int)image.getHeight())
84 continue; // In case we start off the edge
85 int mx = int(start.x + dx * i);
86 int ex = min(mx + var + 1, (int)image.getWidth() - 1);
87 int sx = max(mx - var, 0);
88 for (int x = sx + 1; x < ex; x++) {
90 if (image.get(x, y) && !image.get(x + 1, y)) {
91 points.push_back(Point(x + 0.5f, y));
95 if (!image.get(x, y) && image.get(x + 1, y)) {
96 points.push_back(Point(x + 0.5f, y));
106 Line findLine(const BitMatrix& image, Line estimate, bool invert, int deviation, float threshold, int skip) {
107 float t = threshold * threshold;
109 Point start = estimate.start;
110 Point end = estimate.end;
114 findEdgePoints(edges, image, start, end, invert, skip, deviation);
116 int n = edges.size();
118 float xdist = end.x - start.x;
119 float ydist = end.y - start.y;
121 bool horizontal = abs(xdist) > abs(ydist);
124 Line bestLine(start, end); // prepopulate with the given line, in case we can't find any line for some reason
126 for (int i = -deviation; i < deviation; i++) {
130 x1 = start.x - i * ydist / xdist;
132 y1 = start.y - i * xdist / ydist;
136 for (int j = -deviation; j < deviation; j++) {
140 x2 = end.x - j * ydist / xdist;
142 y2 = end.y - j * xdist / ydist;
148 float length = sqrt(dx * dx + dy * dy);
152 for(int k = 0; k < n; k++) {
153 const Point& edge = edges[k];
154 float dist = ((x1 - edge.x) * dy - (y1 - edge.y) * dx) / length;
155 // Similar to least squares method
156 float s = t - dist * dist;
163 bestLine.start = Point(x1, y1);
164 bestLine.end = Point(x2, y2);
172 Point intersection(Line a, Line b) {
173 float dxa = a.start.x - a.end.x;
174 float dxb = b.start.x - b.end.x;
175 float dya = a.start.y - a.end.y;
176 float dyb = b.start.y - b.end.y;
178 float p = a.start.x * a.end.y - a.start.y * a.end.x;
179 float q = b.start.x * b.end.y - b.start.y * b.end.x;
180 float denom = dxa * dyb - dya * dxb;
181 if(denom == 0) // Lines don't intersect
182 return Point(INFINITY, INFINITY);
184 float x = (p * dxb - dxa * q) / denom;
185 float y = (p * dyb - dya * q) / denom;
190 } // namespace EdgeDetector