diff options
| author | Gustav Sörnäs <gustav@sornas.net> | 2020-12-03 16:27:06 +0100 |
|---|---|---|
| committer | Gustav Sörnäs <gustav@sornas.net> | 2020-12-03 16:27:06 +0100 |
| commit | 7b7f6808a7b2db2ed21103767434c1445f7815c2 (patch) | |
| tree | 7b3553187d169757fedcdaf20f286761f29c2551 /labb7/src/brute.cpp | |
| parent | 0a8d737eccc6bfdb6ad7b9aaa1f6fc7c5b84f1eb (diff) | |
| download | tddd86-7b7f6808a7b2db2ed21103767434c1445f7815c2.tar.gz | |
add given files l7
Diffstat (limited to 'labb7/src/brute.cpp')
| -rw-r--r-- | labb7/src/brute.cpp | 94 |
1 files changed, 94 insertions, 0 deletions
diff --git a/labb7/src/brute.cpp b/labb7/src/brute.cpp new file mode 100644 index 0000000..ffddd0f --- /dev/null +++ b/labb7/src/brute.cpp @@ -0,0 +1,94 @@ +/*
+ * TDDD86 Pattern Recognition
+ * This program computes and plots all line segments involving 4 points
+ * in a file using Qt.
+ */
+
+#include <QApplication>
+#include <QGraphicsView>
+#include <QGraphicsScene>
+#include <fstream>
+#include <iostream>
+#include <algorithm>
+#include <vector>
+#include <chrono>
+#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 = "input100.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("Brute Force Pattern Recognition");
+ view->show();
+
+ // sort points by natural order
+ // makes finding endpoints of line segments easy
+ sort(points.begin(), points.end());
+ auto begin = chrono::high_resolution_clock::now();
+
+ // iterate through all combinations of 4 points
+ for (int i = 0 ; i < N-3 ; ++i) {
+ for (int j = i+1 ; j < N-2 ; ++j) {
+ for (int k = j+1 ; k < N-1 ; ++k) {
+ //only consider fourth point if first three are collinear
+ if (points.at(i).slopeTo(points.at(j)) == points.at(i).slopeTo(points.at(k))) {
+ for (int m{k+1} ; m < N ; ++m) {
+ if (points.at(i).slopeTo(points.at(j)) == points.at(i).slopeTo(points.at(m))) {
+ render_line(scene, points.at(i), points.at(m));
+ a.processEvents(); // show rendered line
+ }
+ }
+ }
+ }
+ }
+ }
+
+ auto end = chrono::high_resolution_clock::now();
+ cout << "Computing line segments took "
+ << std::chrono::duration_cast<chrono::milliseconds>(end - begin).count()
+ << " milliseconds." << endl;
+
+ return a.exec(); // start Qt event loop
+}
|