add given files l7

3 files changed, 212 insertions, 0 deletions

diff --git a/labb7/src/Point.cpp b/labb7/src/Point.cpp
new file mode 100644
index 0000000..be42b8b
--- /dev/null
+++ b/labb7/src/Point.cpp
@@ -0,0 +1,61 @@
+/*

+ * TDDD86 Pattern Recognition

+ * This file contains the implementation of the Point class.

+ * See Point.h for comments about each member.

+ * Your code should work properly with an unmodified version of this file.

+ */

+

+#include <limits>

+#include <iomanip>

+#include <iostream>

+#include <sstream>

+#include <cmath>

+#include <QGraphicsEllipseItem>

+#include <QGraphicsLineItem>

+#include "Point.h"

+

+double Point::slopeTo(const Point& p) const {

+    if (x == p.x && y == p.y)

+        return  -std::numeric_limits<double>::infinity();

+    else if (y == p.y) // horizontal line segment

+        return 0.0;

+    else if (x == p.x) // vertical line segment

+        return  std::numeric_limits<double>::infinity();

+    else

+        return (static_cast<double>(p.y) - static_cast<double>(y)) /

+                (static_cast<double>(p.x) - static_cast<double>(x));

+}

+

+void Point::draw(QGraphicsScene *scene) const {

+    QGraphicsEllipseItem *item = new QGraphicsEllipseItem(x / (COORD_MAX + 1.0) * scene->width(),

+                                                          y / (COORD_MAX + 1.0) * scene->height(),

+                                                          1, 1);

+    item->setBrush(QBrush(QColor(255, 0, 0)));

+    scene->addItem(item);

+}

+

+void Point::lineTo(QGraphicsScene *scene, const Point& p) const {

+    QGraphicsLineItem *item = new QGraphicsLineItem(x / (COORD_MAX + 1.0) * scene->width(),

+                                                    y / (COORD_MAX + 1.0) * scene->height(),

+                                                    p.x / (COORD_MAX + 1.0) * scene->width(),

+                                                    p.y / (COORD_MAX + 1.0) * scene->height());

+    item->setPen(QPen(QColor(0, 0, 255), 0));

+    scene->addItem(item);

+}

+

+bool Point::operator<(const Point& other) const {

+    if (x == other.x)

+        return y < other.y;

+    else

+        return x < other.x;

+}

+

+bool Point::operator>(const Point& other) const

+{

+    return other < *this;

+}

+

+ostream& operator<<(std::ostream& out, const Point& p) {

+    out << "(" << p.x << ", " << p.y << ")";

+    return out;

+}

diff --git a/labb7/src/Point.h b/labb7/src/Point.h
new file mode 100644
index 0000000..3b167a4
--- /dev/null
+++ b/labb7/src/Point.h
@@ -0,0 +1,57 @@
+/*

+ * TDDD86 Pattern Recognition

+ * This file contains the declaration of the Point class.

+ * See Point.cpp for implementation of each member.

+ * Your code should work properly with an unmodified version of this file.

+ */

+

+#ifndef POINT_H

+#define POINT_H

+

+#include <iostream>

+#include <QGraphicsScene>

+using namespace std;

+

+static const int COORD_MAX = 32767; // max value of x and y coordinates

+

+/*

+ * Each Point object represents an immutable single point

+ * with integer coordinates in the Euclidean plane.

+ */

+class Point {

+public:

+

+    Point() = delete;

+    Point(unsigned int _x, unsigned int _y) : x(_x), y(_y){}

+

+    /**

+     * Slope between this point and p

+     *

+     * If the points are the same, negative infinity is returned

+     * If the line between the points is horizontal positive zero is returned

+     * If the line between the points is vertical positive infinity is returned

+     */

+    double slopeTo(const Point& p) const;

+    /**

+     * Draw point to scene

+     */

+    void draw(QGraphicsScene* scene) const;

+    /**

+     * Draw line from this point to p to scene

+     */

+    void lineTo(QGraphicsScene* scene, const Point& p) const;

+

+    /**

+     * Is this point lexicographically smaller than p?

+     * Comparing x-ccordinates and breaking ties by y-coordinates

+     */

+    bool operator<(const Point&) const;

+    bool operator>(const Point&) const;

+

+    friend ostream& operator<<(ostream&, const Point&);

+

+private:

+    unsigned int x, y; // position

+};

+

+#endif // POINT_H

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

+}