AVmJKn7n

1
2#ifndef _PATH_H
3#define _PATH_H
4
5#include "cs221util/PNG.h"
6#include "cs221util/RGBAPixel.h"
7#include <utility>
8#include <vector>
9using namespace std;
10using namespace cs221util;
11
12class path {
13
14public:
15
16    // initializes variables and calls BFS to initialize path.
17	path(const PNG & im,pair<int,int> s,pair<int,int> e);
18
19	//draws path points in red on a copy of the image and returns it
20	PNG render();
21
22	//returns path of points
23	vector<pair<int,int> > getPath();
24
25	//returns length of shortest path of points
26	int length();
27
28private:
29
30    // used to initialize member variable pathPts.
31    // called by constructor to create path if it 
32    // exists. 
33    //
34    // requires: neighbors, good, assemble helpers
35    //
36    // See the interfaces for good and assemble
37    // to get a hint on two auxiliary structures
38    // you will want to build: predecessor table,
39    // and visited table.
40   void BFS();
41
42    // tests a neighbor (adjacent vertex) to see if it is 
43    // 1. within the image, 2. unvisited, and 3. close in color to curr.
44    // An entry in table V is true if a cell has previously been 
45    // visited.
46	bool good(vector<vector<bool>> & v, pair<int,int> curr, pair<int,int> next);
47
48    // builds a vector containing the locations of the 
49    // four vertices adjacent to curr:
50    // above, left, right, below (no particular order). 
51    // does not pay any attention to whether or not the neighbors are 
52    // valid (in the image, previously visited, or the right color).
53	vector<pair<int,int>> neighbors(pair<int,int> curr) ;
54
55    // Assumes the predecessor table, built in the BFS as follows: For each 
56    // location in the image reachable from the start vertex, "loc", the 
57    // table contains the location "pred" from which "loc" was first seen.
58    // ("pred", "loc") is thus an edge in the shortest path from s to 
59    // "loc".
60    //
61    // returns the set of points on the shortest path from s to e, if 
62    // it exists. Call this vector P.
63    //
64    // if there is a shortest path: position 0 should contain s, 
65    // and for all 0 < i < size, P[0] to P[i] is the set of points
66    // on the shortest path from s to point P[i]. P[size-1] == e.
67
68    // if no path from s to e exists, then just return a single element
69    // vector P with P[0] == s.
70  
71	vector<pair<int,int>> assemble(vector<vector<pair<int,int>>> & p,
72		pair<int,int> s, pair<int,int> e);
73
74
75    pair<int,int> getPathRoot(vector<vector<pair<int,int>>> & p, pair<int,int> e);
76
77    // tests whether p1 and p2 are near in color. returns 
78    // true if the sum of squared difference over color channels
79    // is less than or equal to 80. 
80    bool closeEnough(RGBAPixel p1, RGBAPixel p2);
81
82// ========= private member variables ================
83
84	// stores the points in the path
85	// pathPts[0] == start, pathPts[size-1] == end.
86    // if no path exists, then only pathPts[0] == start 
87    // see description for assemble for more details.
88	vector <pair<int,int>> pathPts;
89
90
91
92	pair<int,int> start;
93	pair<int,int> end;
94	PNG image;
95
96};
97
98#endif