From 7b7f6808a7b2db2ed21103767434c1445f7815c2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 3 Dec 2020 16:27:06 +0100 Subject: add given files l7 --- labb7/PatternRecognition.pro | 40 +++++++++++++++++++ labb7/src/Point.cpp | 61 ++++++++++++++++++++++++++++ labb7/src/Point.h | 57 +++++++++++++++++++++++++++ labb7/src/brute.cpp | 94 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 252 insertions(+) create mode 100644 labb7/PatternRecognition.pro create mode 100644 labb7/src/Point.cpp create mode 100644 labb7/src/Point.h create mode 100644 labb7/src/brute.cpp (limited to 'labb7') diff --git a/labb7/PatternRecognition.pro b/labb7/PatternRecognition.pro new file mode 100644 index 0000000..a63cef6 --- /dev/null +++ b/labb7/PatternRecognition.pro @@ -0,0 +1,40 @@ +QT += widgets +SOURCES = $$PWD/src/*.cpp +#SOURCES += $$PWD/lib/*.cpp +HEADERS = $$PWD/src/*.h +#HEADERS += $$PWD/lib/*.h + +QMAKE_CXXFLAGS += -std=c++11 + +INCLUDEPATH += $$PWD/lib/ + +# Copies the given files to the destination directory +defineTest(copyToDestdir) { + files = $$1 + + for(FILE, files) { + DDIR = $$OUT_PWD + + # Replace slashes in paths with backslashes for Windows + win32:FILE ~= s,/,\\,g + win32:DDIR ~= s,/,\\,g + + !win32 { + QMAKE_POST_LINK += cp -r '"'$$FILE'"' '"'$$DDIR'"' $$escape_expand(\\n\\t) + } + win32 { + QMAKE_POST_LINK += xcopy '"'$$FILE'"' '"'$$DDIR'"' /e /y $$escape_expand(\\n\\t) + } + } + + export(QMAKE_POST_LINK) +} +!win32 { + copyToDestdir($$files($$PWD/res/*)) +} +win32 { + copyToDestdir($$PWD/res) +} +macx { + cache() +} 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 +#include +#include +#include +#include +#include +#include +#include "Point.h" + +double Point::slopeTo(const Point& p) const { + if (x == p.x && y == p.y) + return -std::numeric_limits::infinity(); + else if (y == p.y) // horizontal line segment + return 0.0; + else if (x == p.x) // vertical line segment + return std::numeric_limits::infinity(); + else + return (static_cast(p.y) - static_cast(y)) / + (static_cast(p.x) - static_cast(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 +#include +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 +#include +#include +#include +#include +#include +#include +#include +#include "Point.h" + +// constants +static const int SCENE_WIDTH = 512; +static const int SCENE_HEIGHT = 512; + +void render_points(QGraphicsScene* scene, const vector& 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 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(end - begin).count() + << " milliseconds." << endl; + + return a.exec(); // start Qt event loop +} -- cgit v1.2.1