From fa32f97c3617381eec9d9f4736ae94dd284d1617 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= <gustav@sornas.net>
Date: Tue, 15 Dec 2020 13:05:18 +0100
Subject: e8 dont draw shorter overlapping lines

---
 labb7/src/fast.cpp | 94 ++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 81 insertions(+), 13 deletions(-)

diff --git a/labb7/src/fast.cpp b/labb7/src/fast.cpp
index 8937c8f..e01af2d 100644
--- a/labb7/src/fast.cpp
+++ b/labb7/src/fast.cpp
@@ -24,6 +24,43 @@ void render_line(QGraphicsScene* scene, const Point& p1, const Point& p2) {
     p1.lineTo(scene, p2);
 }
 
+/*
+ * Return whether v1 contains v2.
+ */
+template <typename T>
+bool vec_contains_vec(const vector<T>& v1, const vector<T>& v2) {
+    if (v2.size() == 0) {
+        return true;
+    }
+    int i1 = 0;
+    int i2 = 0;
+    while (i1 < v1.size()) {
+        if (v1[i1] == v2[i2]) {
+            i2++;
+            if (i2 == v2.size()) {
+                return true;
+            }
+        } else {
+            i2 = 0;
+        }
+        i1++;
+    }
+    return false;
+}
+
+/*
+ * Return whether inner is contained in some vector before itself in outer.
+ */
+template <typename T>
+bool contained_in_before(const vector<vector<T>>& outer, int index) {
+    for (int i = 0; i < index; i++) {
+        if (vec_contains_vec(outer[i], outer[index])) {
+            return true;
+        }
+    }
+    return false;
+}
+
 int main(int argc, char *argv[]) {
     QApplication a(argc, argv);
 
@@ -62,31 +99,62 @@ int main(int argc, char *argv[]) {
     sort(points.begin(), points.end());
     auto begin = chrono::high_resolution_clock::now();
 
-    vector<pair<double, Point>> angles;
-    int draws = 0;
+    // these contain indexes since points can't be compared
+    vector<vector<int>> lines;  // all lines we want to draw
+    vector<pair<double, int>> angles;  // for each point, the angle to every other point
+
     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) });
+            angles.push_back({ angle, p2 });
         }
         sort(angles.begin(), angles.end());
-
-        int num_in_row = 0;
-        for (int i = 1; i < angles.size(); i++) {
+        vector<int> line = { p1, 1 };
+        for (int i = 2; 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++;
-                }
+                line.push_back(angles[i].second);
             } else {
-                num_in_row = 0;
+                if (line.size() >= 4) {
+                    lines.push_back(line);
+                }
+                line.clear();
+                line.push_back(p1);
+                line.push_back(angles[i].second);
             }
         }
+        if (line.size() >= 4) {
+            lines.push_back(line);
+        }
+    }
+
+    for (int i = 0; i < lines.size();) {
+        if (contained_in_before(lines, i)) {
+            lines.erase(lines.begin() + i);
+        } else {
+            i++;
+        }
+    }
+
+    for (const auto& line : lines) {
+        render_line(scene, points.at(line.front()), points.at(line.back()));
     }
-    cout << draws << endl;
+    cout << lines.size() << " draws" << endl;
+
+    vector<int> v1 = {1, 2, 3};
+    vector<int> v2 = {2, 3};
+    vector<int> v3 = {3};
+    vector<int> v4 = {2, 3, 4};
+    cout << vec_contains_vec(v1, v2) << " "
+         << vec_contains_vec(v2, v1) << " "
+         << vec_contains_vec(v1, v3) << " "
+         << vec_contains_vec(v1, v4) << endl;
+
+    vector<vector<int>> outer = {{1,2,3}, {2,3}, {3,4}};
+    cout << contained_in_before(outer, 0) << " "
+         << contained_in_before(outer, 1) << " "
+         << contained_in_before(outer, 2) << endl;
 
     auto end = chrono::high_resolution_clock::now();
     cout << "Computing line segments took "
-- 
cgit v1.2.1