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
|
#include <QApplication>
#include <QGraphicsView>
#include <QGraphicsScene>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <chrono>
#include <cmath>
#include <unordered_map>
#include "Point.h"
// constants
static const int SCENE_WIDTH = 512;
static const int SCENE_HEIGHT = 512;
void render_points(QGraphicsScene* scene, const vector<Point>& points) {
for(const auto& point : points) {
point.draw(scene);
}
}
void render_line(QGraphicsScene* scene, const Point& p1, const Point& p2) {
p1.lineTo(scene, p2);
}
int main(int argc, char *argv[]) {
QApplication a(argc, argv);
// open file
string filename = "grid6x6.txt";
ifstream input;
input.open(filename);
// the vector of points
vector<Point> points;
// read points from file
int N;
int x;
int y;
input >> N;
for (int i = 0; i < N; ++i) {
input >> x >> y;
points.push_back(Point(x, y));
}
input.close();
// setup graphical window
QGraphicsView *view = new QGraphicsView();
QGraphicsScene *scene = new QGraphicsScene(0, 0, SCENE_WIDTH, SCENE_HEIGHT);
view->setScene(scene);
// draw points to screen all at once
render_points(scene, points);
view->scale(1, -1); //screen y-axis is inverted
view->resize(view->sizeHint());
view->setWindowTitle("Fast Pattern Recognition");
sort(points.begin(), points.end());
auto begin = chrono::high_resolution_clock::now();
vector<pair<double, Point>> angles;
int draws = 0;
for (int p1 = 0; p1 < N-1; p1++) {
angles.clear();
for (int p2 = p1 + 1; p2 < N; p2++) {
double angle = points.at(p1).slopeTo(points.at(p2));
angles.push_back({ angle, points.at(p2) });
}
sort(angles.begin(), angles.end());
int num_in_row = 0;
for (int i = 1; i < angles.size(); i++) {
double prev_angle = angles[i - 1].first;
if (angles[i].first == prev_angle) {
num_in_row++;
if (num_in_row >= 2) {
render_line(scene, points.at(p1), angles[i].second);
draws++;
}
} else {
num_in_row = 0;
}
}
}
cout << draws << endl;
auto end = chrono::high_resolution_clock::now();
cout << "Computing line segments took "
<< std::chrono::duration_cast<chrono::milliseconds>(end - begin).count()
<< " milliseconds." << endl;
view->show();
return a.exec(); // start Qt event loop
}
|
