it's been a couple days, been a bit busy with other work but just finished it:
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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
|
/*
* Tunnel route planning algorithm
* Done as part of the MEA2 assignment for APSC 100 Module 2 of Queen's University Engineering Program
* (c) Mitchell Bland 2017
*/
// included Libraries
#include <string> // for string object -> only used in file I/O
#include <iostream> // cout
#include <vector> // vector object
#include <cmath> // sqrt(), etc
#include <fstream> // ifstream -> used for file I/O
// number of points
#define N 26
using namespace std;
struct point
{
double x, y;
// used to shorten print statements
void print()
{
cout << "(" << x << ", " << y << ")";
}
};
// less of a vector class than a line class, as it has two points (a line is a vector/slope and a point)
struct vect
{
point start_pt;
point end_pt;
double x,y;
// Yes, I know that I should put my functions at the bottom of the code.
// I did this because they're all pretty short
// would use class ctor, but needs to be called repeatedly to reduce # of variables
void construct(point a, point b)
{
start_pt = a;
end_pt = b;
calc();
}
// calculate points of vector
void calc()
{
x = end_pt.x - start_pt.x;
y = end_pt.y - start_pt.y;
}
// calculate magnitude of vector
double mag()
{
return sqrt(x * x + y * y);
}
// calculate midpoint of vector
point midpoint()
{
// could also use x = start_pt.x + 0.5 * x;
point val;
val.x = (start_pt.x + end_pt.x) / 2;
val.y = (start_pt.y + end_pt.y) / 2;
return val;
}
};
int main()
{
point pts[N];
vector <vect> tun_map;
// FILE INPUT TO GET POINTS
string line;
ifstream myfile("points.txt"); // create file object
if (myfile.is_open()) // checks if file works
{
int index = 0;
while (getline(myfile, line)) // checks if still open while moving line of txt to line string
{
point temp;
// convert ASCII text to numbers
temp.x = (line[0] - 48) * 100 + (line[1] - 48) * 10 + (line[2] - 48);
temp.y = (line[4] - 48) * 100 + (line[5] - 48) * 10 + (line[6] - 48);
pts[index] = temp; // put point in array
index++;
}
myfile.close();
}
else cout << "bad file" << endl;
// transform map points into a vector to allow for looping
vector <point> curr_pts;
for (int i = 0; i < N; i++)
{
curr_pts.push_back(pts[i]);
}
vect test;
bool cont = true;
while(cont)
{
int num = curr_pts.size(); // number of points - set to variable due to # of usages
vector <point> new_pts;
vector <int> used_i;
// if num is odd -> extra point. Move it to end, and decrement num to avoid errors
if (num % 2 == 1)
{
new_pts.push_back(curr_pts.at(num-1));
num--; // insure even
}
// increment thru first point
for (int i = 0; i < num; i++)
{
// variables
double min_dist = INT_MAX;
int min_dist_i = i;
vect temp;
// check if already used
bool used = false;
for (int k = 0; k < used_i.size(); k++)
{
if (i == used_i.at(k)) used = true;
}
if(used) continue;
// if not make sure it cant be again
used_i.push_back(i);
// increment thru second point
for (int j = 0; j < num; j++)
{
// check if already used
used = false;
for (int k = 0; k < used_i.size(); k++)
{
if (j == used_i.at(k)) used = true;
}
if(used) continue;
// check if its the closest one
temp.construct(curr_pts.at(i), curr_pts.at(j));
int temp_dist = temp.mag();
// if closest set it as such
if (temp_dist < min_dist)
{
min_dist = temp_dist;
min_dist_i = j;
}
}
// reconstruct temp based on minimum dist
temp.construct(curr_pts.at(i), curr_pts.at(min_dist_i));
// add vector to map and eliminate j value from list
tun_map.push_back(temp);
used_i.push_back(min_dist_i);
// push back midpoint of tunnel for next round
new_pts.push_back(temp.midpoint());
}
// loop thru vectors and assign values to include new lines. This is done to allow easy looping
curr_pts.clear(); // erase current points so as to not have an infinite loop
// *definately* didn't add this after several minutes of debugging
for (int i = 0; i < new_pts.size(); i++)
{
curr_pts.push_back(new_pts.at(i));
}
cont = !(curr_pts.size() == 1); // if only 1 point remaining, its the midpoint of the last vector drawn
// otherwise continue
}
double tot_dist = 0;
// prints the connected points, the vector they make, and the magnitude
for (int i = 0; i < tun_map.size(); i++)
{
tun_map.at(i).start_pt.print();
cout << " + "; // yes I know it's not correct to "add" points but this makes sense to me
tun_map.at(i).end_pt.print();
cout << " = ";
cout << "[" << tun_map.at(i).x << ", " << tun_map.at(i).y << "] -> ";
cout << tun_map.at(i).mag() << endl;
tot_dist += tun_map.at(i).mag();
}
cout << tot_dist << endl; // units = pixels
cout << (tot_dist / sqrt(13*13 + 265*265)) * 300 << " meters" << endl; // units = meters
return 0;
}
|
Sorry if the code is a bit rough, a lot of my console debugging lines are still in because I literally just finished 5 minutes ago. I'd be happy to take feedback on the code if anyone has any comments, just keep in mind that this isn't a programing class, they won't mark the actual program for efficiency, etc.
On one of the last lines, I use this:
(tot_dist / sqrt(13*13 + 265*265)) * 300
. That's just unit conversion. I used google maps to calculate the distance from Barrie/Stuart to Barrie/Union, (300m), then used GIMP (a Photoshop software) to select all my points in terms of pixels on this map:
https://drive.google.com/file/d/1HbdITe_2XW3Cg3wLZfyRWOwPsUvF1R7y/view?usp=sharing, as well as points for the two intersections, then did basic math to determine a "conversion factor". I know my method is inaccurate as google maps is +/- 50m (if i remember correctly), but its the best I have so far.
The file I used was this:
https://drive.google.com/file/d/1O4eoFKcRUjOX4dkn2LiE5LTz21GITkuq/view?usp=sharing
EDIT:
replaced the code with slightly nicer-looking code without all the console debugging. I need to actually test the program by drawing out each of the vectors on a graph, but the total distance seems about right (I predicted about 4km, and got 4.3) so hopefully it's OK.