· 5 years ago · Feb 25, 2020, 11:48 PM
1/*
2 * Copyright 2020 University of Toronto
3 *
4 * Permission is hereby granted, to use this software and associated
5 * documentation files (the "Software") in course work at the University
6 * of Toronto, or for personal use. Other uses are prohibited, in
7 * particular the distribution of the Software either publicly or to third
8 * parties.
9 *
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19 * SOFTWARE.
20 */
21#include <cmath>
22#include <map>
23#include <string>
24#include "m1.h"
25#include "helperFunctions.h"
26#include "StreetsDatabaseAPI.h"
27#include "OSMDatabaseAPI.h"
28#include <map>
29#include <iterator>
30
31//overloaded equality operators for LatLon
32bool operator== (const LatLon&, const LatLon&);
33bool operator!= (const LatLon&, const LatLon&);
34
35std::vector<std::vector<int>> intersection_street_segments; //Street segments of each intersection
36std::vector<std::vector<int>> street_street_segments; //Street segments of each street
37std::vector<std::vector<int>> street_street_intersections; //Street and the intersections of those streets
38std::multimap <std:: string, int> multimap_street_names; //for faster search in partial street name
39std::vector<double> street_segment_travel_time;
40std:: string toLowerCaseWithoutSpaces(std:: string lower); //Helper function
41
42//data structure containing hash tables with correlated OSMID data.
43//Author: Byoungchan Sohn
44struct OSMIDHelper
45{
46 std::unordered_map<OSMID, std::vector<OSMID>> wayLengthStructure; //hash table correlating way OSMIDs to its members for fast lookup
47 std::unordered_map<OSMID,const OSMNode*> listOfOSMID; //hash table correlating OSMID to its Node for fast lookup
48
49 //populates the hash tables
50 bool populateHelper()
51 {
52 //make sorted amp of OSMIDs
53 for (int i = 0; i <getNumberOfNodes() ; i ++)
54 {
55 std::pair<OSMID,const OSMNode*> OSMIDAndOSMNode;
56 OSMIDAndOSMNode.first = getNodeByIndex(i)->id() ;
57 OSMIDAndOSMNode.second = (getNodeByIndex(i));
58 listOfOSMID.insert(OSMIDAndOSMNode);
59 }
60 //make unordered map of ways and wayIDs
61 for (int i = 0; i < getNumberOfWays(); i ++)
62 {
63 std::pair<OSMID,std::vector<OSMID>> tempOSMIDsPair (getWayByIndex(i)->id(), getWayMembers(getWayByIndex(i)));
64 wayLengthStructure.insert(tempOSMIDsPair);
65 }
66 return true;
67 }
68
69 //clears the hash tables
70 void close()
71 {
72 listOfOSMID.clear();
73 wayLengthStructure.clear();
74 }
75};
76
77OSMIDHelper _OSMIDHelper;
78
79bool load_map(std::string map_path) {
80 //author: Shichao Jiang
81 //sub: Byoungchan Sohn added OSMNode and OSMID correlator map
82 //sub: Romil Jain added street_street_intersections
83 bool load_successful = loadStreetsDatabaseBIN(map_path); //Indicates whether the map has loaded
84 //successfully
85 //check for load
86 if (load_successful) {
87 int no_of_intersections = getNumIntersections();
88
89 //Resize each global variable
90 intersection_street_segments.resize(no_of_intersections);
91 street_street_segments.resize(getNumStreets());
92 street_street_intersections.resize(getNumStreets());
93 street_segment_travel_time.resize(getNumStreetSegments());
94 resize_vectors();
95
96 //Create temporary map to prevent duplicates
97 std::unordered_map<int, int> dup_street_segs;
98 std::unordered_map<int, int> dup_streets; //duplicate streets to avoid being added to the multimap multiple times
99
100 //set min and max lat and long
101 double min_lat = 90, min_lon = 360, max_lat = -90, max_lon = -360;
102
103 //loop through each intersection
104 for (IntersectionIndex i = 0; i < no_of_intersections; i++) {
105 std::unordered_map<int, int> dup_streets_for_intersections; //duplicate streets avoided just for one intersection
106 //loop through each street segment relative to the intersection
107 for (int seg = 0; seg < getIntersectionStreetSegmentCount(i); seg++) {
108 //get street segment id
109 int streetSeg = getIntersectionStreetSegment(i, seg);
110 int streetId = getInfoStreetSegment(streetSeg).streetID;
111
112 //push each street segment into global
113 intersection_street_segments[i].push_back(streetSeg);
114
115 //check if streetSegment already exists in street_street_segments;
116 std::unordered_map<int, int>::iterator it = dup_street_segs.find(streetSeg);
117 std::unordered_map<int, int>::iterator it2 = dup_streets_for_intersections.find(streetId);
118 std::unordered_map<int, int>::iterator it3 = dup_streets.find(streetId);
119
120 //sorting street segments by streetID
121 if (it == dup_street_segs.end()) {
122 street_street_segments[streetId].push_back(streetSeg);
123
124 update_data(streetId, streetSeg);
125 }
126
127 //sorting intersections by streetID
128 if (it2 == dup_streets.end()) {
129 street_street_intersections[streetId].push_back(i);
130 }
131
132 if (it3 == dup_streets.end()){
133 std:: string street_lowercase_name = toLowerCaseWithoutSpaces(getStreetName(streetId));
134 //convert string name to lower case and remove spaces for partial street name comparision
135 std :: pair <std::string, int> street_pair(street_lowercase_name, streetId);
136 //pair of street name and id
137 multimap_street_names.insert(street_pair);
138 }
139
140 //insert pair into map to prevent duplicates
141 std::pair<int, int> dup_street_seg_pair(streetSeg, streetSeg);
142 dup_street_segs.insert(dup_street_seg_pair);
143 std::pair<int, int> dup_street_for_intersection_pair(streetId, streetId);
144 dup_streets_for_intersections.insert(dup_street_for_intersection_pair);
145 std::pair<int, int> dup_street_pair(streetId, streetId);
146 dup_streets.insert(dup_street_pair);
147 //Partial street name comparison map
148
149 //storing all segment speed limits in a vector
150 street_segment_travel_time[streetSeg] = (find_street_segment_length(streetSeg)/ (getInfoStreetSegment(streetSeg).speedLimit)) * 3.6;
151 }
152 //finding min and max lat from intersection data
153 LatLon intersection_latlon = getIntersectionPosition(i);
154
155 if(intersection_latlon.lat() < min_lat) min_lat = intersection_latlon.lat();
156 if(intersection_latlon.lat() > max_lat) max_lat = intersection_latlon.lat();
157 if(intersection_latlon.lon() < min_lon) min_lon = intersection_latlon.lon();
158 if(intersection_latlon.lon() > max_lon) max_lon = intersection_latlon.lon();
159 }
160 //store the values in helperFunctions.cpp global variable
161 store_minmax_data(min_lat, min_lon, max_lat, max_lon);
162 }
163
164 //extrapolates the name of the OSMdatabase from the name of the map_path, assumes they are in the same directory
165 std::string mapname (map_path.substr(0,map_path.find_first_of('.')).append(".osm.bin"));
166 if (loadOSMDatabaseBIN(mapname))
167 {
168 _OSMIDHelper.populateHelper();
169 }
170 else //if loading OSMdatabase fails
171 {
172 load_successful = false;
173 }
174 return load_successful;
175}
176
177void close_map() {
178 //Clean-up your map related data structures here
179 closeStreetDatabase();
180 intersection_street_segments.resize(0);
181 street_street_segments.resize(0);
182 _OSMIDHelper.close();
183 multimap_street_names.clear();
184 street_street_intersections.resize(0);
185 closeOSMDatabase();
186}
187
188//Returns the distance between two coordinates (given as LatLon) in meters
189//author: Byoungchan Sohn
190double find_distance_between_two_points(std::pair<LatLon, LatLon> points)
191{
192 //calculates the average latitude of the points
193 double avgLat = DEGREE_TO_RADIAN*(points.first.lat() + points.second.lat())/2;
194
195 //find delta x and delta y
196 double DiffXPos = ((points.second.lon() - points.first.lon())*cos(avgLat));
197 double DiffYPos = (points.second.lat() - points.first.lat());
198
199 //pythagoras formula
200 return DEGREE_TO_RADIAN*EARTH_RADIUS_METERS*(sqrt(pow(DiffXPos,2) + pow(DiffYPos,2)));
201}
202
203//Returns the length of the given street segment in meters, accounting for curves
204//author: Byoungchan Sohn
205double find_street_segment_length(int street_segment_id)
206{
207 int numCurve = getInfoStreetSegment(street_segment_id).curvePointCount;
208 double sumlength = 0.00;
209 std::pair<LatLon, LatLon> endPoints; //pair of LatLons to find distance between
210
211 //makes and defines the pair of LatLon's for each curve point
212 if (numCurve == 0) //if street is straight
213 {
214 endPoints.first = getIntersectionPosition(getInfoStreetSegment(street_segment_id).from);
215 endPoints.second = getIntersectionPosition(getInfoStreetSegment(street_segment_id).to);
216 sumlength += find_distance_between_two_points(endPoints);
217 }
218 else //if not straight
219 {
220 //distance from starting point to 1st bend
221 endPoints.first = getIntersectionPosition(getInfoStreetSegment(street_segment_id).from);
222 endPoints.second = getStreetSegmentCurvePoint(0,street_segment_id);
223 sumlength += find_distance_between_two_points(endPoints);
224 for (int i = 0; i < numCurve-1; i ++) //if there are more than one bend, get distance between them
225 {
226 endPoints.first = getStreetSegmentCurvePoint(i,street_segment_id);
227 endPoints.second = getStreetSegmentCurvePoint(i+1,street_segment_id);
228 sumlength += find_distance_between_two_points(endPoints);
229 }
230 //distance from second last bend point to end point
231 endPoints.first = getStreetSegmentCurvePoint(numCurve-1,street_segment_id);
232 endPoints.second = getIntersectionPosition(getInfoStreetSegment(street_segment_id).to);
233 sumlength += find_distance_between_two_points(endPoints);
234 }
235 return sumlength;
236}
237
238//Returns the travel time to drive a street segment in seconds
239//(time = distance/speed_limit)
240//Author: Romil Jain
241double find_street_segment_travel_time(int street_segment_id){
242 return street_segment_travel_time[street_segment_id];
243}
244
245//Returns the nearest intersection to the given position
246//Author: Romil Jain
247int find_closest_intersection(LatLon my_position){
248
249 int closest_intersection = 0;
250 double length_closest;
251
252 for(int i =0; i<getNumIntersections(); i++){ //goes over all intersections
253 std::pair <LatLon, LatLon> points(getIntersectionPosition(i), my_position); //makes a pair of points to find distance between
254 double length = find_distance_between_two_points(points);
255
256 if(i==0){ //first iteration is closest length initially
257 length_closest=length;
258 }
259 else if(length<length_closest){
260 length_closest = length; // the current length is shorter
261 closest_intersection = i;
262 }
263 }
264 return closest_intersection;
265}
266
267//Returns the street segments for the given intersection
268std::vector<int> find_street_segments_of_intersection(int intersection_id){
269 //author: Shichao Jiang
270 return intersection_street_segments[intersection_id];
271}
272
273//Returns the street names at the given intersection (includes duplicate street
274//names in returned vector)
275std::vector<std::string> find_street_names_of_intersection(int intersection_id){
276 //author: Shichao Jiang
277 std::vector<std::string> names;
278
279 for (int i = 0; i < intersection_street_segments[intersection_id].size(); i++) {
280 //Get id of street in each street segment of the given intersection
281 StreetIndex streetId = getInfoStreetSegment(intersection_street_segments[intersection_id][i]).streetID;
282 names.push_back(getStreetName(streetId));
283 }
284
285 return names;
286}
287
288//Returns true if the first member is directly connected to the second member in the pair
289//or if the first is identical to the second
290//author: Byoungchan Sohn
291bool are_directly_connected(std::pair<int, int> intersection_ids){
292 //creates a pair of integers with the number of street segments each intersection has
293 std::pair<int, int> numConnected(getIntersectionStreetSegmentCount(intersection_ids.first)
294 , getIntersectionStreetSegmentCount(intersection_ids.second));
295
296 //corner case: to itself
297 if (intersection_ids.first == intersection_ids.second) return true;
298
299 //round robin equivalency comparison (Order smallM*smallN)
300 for (int i = 0; i <numConnected.first; i ++)
301 {
302 for (int j = 0; j<numConnected.second; j++)
303 {
304 if (getIntersectionStreetSegment(intersection_ids.first,i)==(getIntersectionStreetSegment(intersection_ids.second,j))) return true;
305 }
306 }
307 return false;
308}
309
310//Returns all intersections reachable by traveling down one street segment
311//from given intersection (hint: you can't travel the wrong way on a 1-way street)
312//the returned vector should NOT contain duplicate intersections
313std::vector<int> find_adjacent_intersections(int intersection_id){
314 //author: Shichao Jiang
315 std::vector<int> adjacent;
316
317 //Get segments of the intersection
318 std::vector<int> segments = find_street_segments_of_intersection(intersection_id);
319
320 for (int i=0; i < segments.size(); i++) {
321 std::vector<int>::iterator it = std::find(adjacent.begin(), adjacent.end(), getInfoStreetSegment(segments[i]).to);
322 std::vector<int>::iterator it2 = std::find(adjacent.begin(), adjacent.end(), getInfoStreetSegment(segments[i]).from);
323
324 //Check if segment is already in array
325 if (it == adjacent.end()) {
326 //Case for one way streets
327 if (getInfoStreetSegment(segments[i]).oneWay) {
328 //Check which side of segment is the intersection
329 if (getInfoStreetSegment(segments[i]).from == intersection_id) {
330 adjacent.push_back(getInfoStreetSegment(segments[i]).to);
331 }
332 } else {
333 //Check which side of segment is the intersection
334 if (getInfoStreetSegment(segments[i]).from == intersection_id) {
335 adjacent.push_back(getInfoStreetSegment(segments[i]).to);
336 } else if (it2 == adjacent.end()) {
337 adjacent.push_back(getInfoStreetSegment(segments[i]).from);
338 }
339 }
340 }
341 }
342
343 return adjacent;
344}
345
346//Returns all street segments for the given street
347std::vector<int> find_street_segments_of_street(int street_id) {
348 //author: Shichao Jiang
349 return street_street_segments[street_id];
350}
351
352//Returns all intersections along the a given street
353std::vector<int> find_intersections_of_street(int street_id){
354 //author: Romil Jain
355 return street_street_intersections[street_id];
356}
357
358//Return all intersection ids for two intersecting streets
359//This function will typically return one intersection id.
360//author: Romil Jain
361std::vector<int> find_intersections_of_two_streets(std::pair<int, int> street_ids){
362 //Go over all streets and push the common intersections
363 std::vector<int> common_intersections;
364
365 //iterator over the first street
366 for(auto it_street_1=street_street_intersections[street_ids.first].begin(); it_street_1!= street_street_intersections[street_ids.first].end(); it_street_1++){
367 //iterator over the second street
368 for(auto it_street_2=street_street_intersections[street_ids.second].begin(); it_street_2!= street_street_intersections[street_ids.second].end(); it_street_2++){
369
370 //second condition in if statement above checks if intersection index is already pushed back
371 if(*it_street_1 == *it_street_2 && (std::find(common_intersections.begin(), common_intersections.end(), *it_street_1)) == common_intersections.end()){
372 common_intersections.push_back(*it_street_1);
373 }
374 }
375 }
376
377 return common_intersections;
378}
379
380//Returns all street ids corresponding to street names that start with the given prefix
381//The function should be case-insensitive to the street prefix. You should ignore spaces.
382//For example, both "bloor " and "BloOrst" are prefixes to "Bloor Street East".
383//If no street names match the given prefix, this routine returns an empty (length 0)
384//vector.
385//You can choose what to return if the street prefix passed in is an empty (length 0)
386//string, but your program must not crash if street_prefix is a length 0 string.
387//author: Romil Jain
388std::vector<int> find_street_ids_from_partial_street_name(std::string street_prefix){
389
390 std:: vector <int> matched_streets;
391 int length_of_prefix = street_prefix.length();
392 if(length_of_prefix == 0) return matched_streets; //return empty vector
393
394 street_prefix = toLowerCaseWithoutSpaces(street_prefix.substr(0,length_of_prefix));// edited street prefix to be lower case and without spaces
395 auto it = multimap_street_names.lower_bound(street_prefix); //iterator to first partial match of street-prefix
396
397 while(it!=multimap_street_names.end() && (*it).first.substr(0,street_prefix.length())== street_prefix){ //if the strings match till the length of the prefix
398 matched_streets.push_back((*it).second);
399 it++;
400 }
401 return matched_streets;
402}
403
404//Returns the area of the given closed feature in square meters
405//Assumes non-intersecting polygon
406//Author: Byoungchan Sohn
407//Source: https://www.wikihow.com/Calculate-the-Area-of-a-Polygon
408double find_feature_area(int feature_id)
409{
410 //declares a vector of coordinates
411 std::vector<LatLon> points_of_POI;
412 int numPoints = getFeaturePointCount(feature_id);
413 double maxLat = 0.00, minLat = 0.00, avgLat;
414
415 // gets all the points of a POI(feature)
416 for (int i = 0; i < numPoints; i ++)
417 {
418 points_of_POI.push_back(getFeaturePoint(i, feature_id));
419 // finds the minimum and maximum latitudes to find x and y
420 if (i == 0) {
421 maxLat = getFeaturePoint(i, feature_id).lat();
422 minLat = getFeaturePoint(i, feature_id).lat();
423 }
424 if (maxLat < getFeaturePoint(i, feature_id).lat()) maxLat = getFeaturePoint(i, feature_id).lat();
425 if (minLat > getFeaturePoint(i, feature_id).lat()) minLat = getFeaturePoint(i, feature_id).lat();
426 }
427 avgLat = DEGREE_TO_RADIAN*(minLat + maxLat)/2;
428
429 // if the polygon is not closed, return 0 as specified
430 if ((points_of_POI[0] != points_of_POI[numPoints-1])||(numPoints < 3)) return 0.0;
431
432 //append the first element to the list
433 points_of_POI.push_back(getFeaturePoint(0, feature_id));
434
435 //Adds the sums to get final result
436 double sumPlus = 0.00,sumMinus = 0.00;
437 for (int i = 0; i<numPoints; i ++)
438 {
439 sumPlus += (points_of_POI[i].lon()*cos(avgLat)) * (points_of_POI[i+1].lat());
440 }
441 for (int i = numPoints; i>0; i --)
442 {
443 sumMinus += (points_of_POI[i].lon()*cos(avgLat)) * (points_of_POI[i-1].lat());
444 }
445 return fabs((sumPlus - sumMinus)*pow(EARTH_RADIUS_METERS,1)*1941.26117549768)/2;
446}
447
448//Returns the length of the OSMWay that has the given OSMID, in meters.
449//Author: Byoungchan Sohn
450double find_way_length(OSMID way_id)
451{
452 double sumOfLength = 0.00;
453 std::vector<LatLon> wayLatLon; //should be a vector of LatLon's
454 std::vector<OSMID> wayMembersOSMID; //vector of OSMIDs of the nodes in the way
455
456 //gets a vector of OSMIDs of nodes in the way using the set vector
457 wayMembersOSMID = _OSMIDHelper.wayLengthStructure.find(way_id)->second;
458
459 //find the lat and lon of the members of the way, populating wayLatLon
460 for (int i = 0; i < wayMembersOSMID.size(); i ++)
461 {
462 wayLatLon.push_back(getNodeCoords((_OSMIDHelper.listOfOSMID.find(wayMembersOSMID[i]))->second));
463 //computes length between i'th and i'th -1 node
464 if (i>0)
465 {
466 std::pair<LatLon, LatLon> wayseg(wayLatLon[i], wayLatLon[i-1]);
467 sumOfLength += find_distance_between_two_points(wayseg);
468 }
469 }
470 return sumOfLength;
471}
472
473//overloaded equality operator for LatLon
474//author: Byoungchan Sohn
475bool operator== (const LatLon& a, const LatLon& b)
476{
477 if (a.lat()!=b.lat() || a.lon()!=b.lon())
478 return false;
479 return true;
480}
481
482//overloaded inequality operator for LatLon
483//author: Byoungchan Sohn
484bool operator!= (const LatLon& a, const LatLon& b)
485{
486 return !(a==b);
487}
488
489//author: Romil Jain
490std:: string toLowerCaseWithoutSpaces(std:: string lower){
491 int length_of_prefix = lower.length();
492 for(int i=0; i<length_of_prefix; i++){
493
494 more_than_one_space:
495 if(lower[i] == ' '){ //I am assuming the user does not enter other stupid special characters
496 for(int j=i; j<length_of_prefix; j++){
497 lower[j] = lower[j+1]; //eliminate white spaces by shifting the characters by one space.
498 //The characters at the end become '\0' but we do not traverse them while finding common characters
499 }
500 length_of_prefix--;
501 if(lower[i] == ' ')
502 goto more_than_one_space;
503 }
504 if(lower[i]<91 && lower[i] > 64){
505 lower[i]+=32;//adding 32 to make the character lower case
506 }
507 }
508 return lower.substr(0,length_of_prefix);
509}