-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHuskyMaps.html
More file actions
164 lines (150 loc) · 7.18 KB
/
HuskyMaps.html
File metadata and controls
164 lines (150 loc) · 7.18 KB
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
<!DOCTYPE HTML>
<!--
Forty by HTML5 UP
html5up.net | @ajlkn
Free for personal and commercial use under the CCA 3.0 license (html5up.net/license)
-->
<html>
<head>
<title>Landing - Forty by HTML5 UP</title>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no" />
<link rel="stylesheet" href="assets/css/main.css" />
<noscript><link rel="stylesheet" href="assets/css/noscript.css" /></noscript>
</head>
<body class="is-preload">
<!-- Wrapper -->
<div id="wrapper">
<!-- Header -->
<!-- Note: The "styleN" class below should match that of the banner element. -->
<header id="header" class="alt">
<a href="index.html" class="logo"><strong>Conner Wallace</strong></a>
<nav>
<a href="#menu">Menu</a>
</nav>
</header>
<!-- Menu -->
<nav id="menu">
<ul class="links">
<li><a href="index.html">Home</a></li>
<li><a href="about.html">About Me</a></li>
</ul>
</nav>
<!-- Banner -->
<!-- Note: The "styleN" class below should match that of the header element. -->
<section id="banner" class="style2">
<div class="inner">
<span class="image">
<img src="images/HuskyMaps/mapImage.png" alt="" />
</span>
<header class="major">
<h1>HuskyMaps</h1>
</header>
<div class="content">
<p>Final project for my Data Structures and Parallelism class. Provides realtime routing to any location using contraction hierarchies determined by the importance of a road.
</p>
</div>
</div>
</section>
<!-- Main -->
<div id="main" role="main">
<!-- One -->
<section id="one">
<div class="inner">
<header class="major">
<h2>Get There Faster</h2>
</header>
<p>Utilizing Java's functional stream processing for parallelism to create the contraction hierarchies, this routing algorithm is about 1.5 times faster than the traditional non-parallel approach.</p>
</div>
</section>
<!-- Two -->
<section id="two" class="spotlights">
<section>
<span class="image">
<img src="images/HuskyMaps/server-rastering-example.png" alt="" data-position="center center" />
</span>
<div class="content">
<div class="inner">
<header class="major">
<h3>Rastering</h3>
</header>
<p>The first part of this project's goal was to implement the backend for<a href="https://github.com/connermwallace/HuskyMaps/blob/master/server/logic/Rasterer.java"> HuskyMaps Rasterer.java</a>. This involved creating a rastering algorithm to decide which images to display. The underlying algorithm for this section was to use the search query's top left point and bottom right point, as well as the depth of the zoom, to determine the dimensions of the tile array to be returned. Next, using the AStar path-finding algorithm I implemented earlier in the course, I returned the shortest path between two points.
</p>
</div>
</div>
</section>
<section>
<span class="image">
<img src="images/HuskyMaps/Shortcut_in_a_shortest_path.svg" alt="" data-position="center center" />
</span>
<div class="content">
<div class="inner">
<header class="major">
<h3>Rastering</h3>
</header>
<p>The second part of this project involved implementing the contraction hierarchies algorithm on <a href="https://github.com/connermwallace/HuskyMaps/blob/master/ContractedStreetMapGraph.java">HuskyMaps Graph</a>. This is a two part algorithm designed for creating a smarter representation of a street map in a graph. Essentially, we go through the graph and assign shortcuts two the nodes which represent "important" roads. This is because generally it does not make sense to explore all the highway exits and smaller roads once you are on the highway. The parallel algorithm was the following:
While there are uncontracted nodes:
<ul>
<li>Update each roads importance while caching the road's associated shortcuts in parallel.</li>
<li>Create a set of independent nodes in parallel.</li>
<li>Contract each independent node.</li>
<li>Remove the contracted nodes from the uncontracted nodes.</li>
</ul>
The parallel work was done using Java's functional interfaces as well as Lambda expressions.
</p>
</div>
</div>
</section>
<section>
<a span class="image">
<img src="images/HuskyMaps/mapImage.png" alt="" data-position="25% 25%" />
</span>
<div class="content">
<div class="inner">
<header class="major">
<h3>The Result</h3>
</header>
<p>Now, any husky is capable of navigating their way through the U-District. Made in collaboration with code from CSE 332, Kevin Lin, <a href="https://courses.cs.washington.edu/courses/cse332/20wi/homework/server/">HuskyMaps Server </a>, <a href="https://courses.cs.washington.edu/courses/cse332/20wi/homework/contraction/"> Contraction Hierarchies</a></p>
</div>
</div>
</section>
</section>
<!-- Three -->
<section id="three">
<div class="inner">
<header class="major">
<h2>More Information</h2>
</header>
<p>The project is currently available on my personal GitLab under a private repo to prevent plagiarism. Please feel free to email me if you would like to see more.</p>
<ul class="actions">
<li><a href="https://gitlab.cs.washington.edu/cse332-20wi-students/connerw/tree/master/huskymaps" class="button next">GitLab</a></li>
</ul>
</div>
</section>
</div>
<!-- Footer -->
<footer id="footer">
<div class="inner">
<ul class="icons">
<li><a href="#" class="icon brands alt fa-twitter"><span class="label">Twitter</span></a></li>
<li><a href="#" class="icon brands alt fa-facebook-f"><span class="label">Facebook</span></a></li>
<li><a href="#" class="icon brands alt fa-instagram"><span class="label">Instagram</span></a></li>
<li><a href="#" class="icon brands alt fa-github"><span class="label">GitHub</span></a></li>
<li><a href="#" class="icon brands alt fa-linkedin-in"><span class="label">LinkedIn</span></a></li>
</ul>
<ul class="copyright">
<li>© Untitled</li><li>Design: <a href="https://html5up.net">HTML5 UP</a></li>
</ul>
</div>
</footer>
</div>
<!-- Scripts -->
<script src="assets/js/jquery.min.js"></script>
<script src="assets/js/jquery.scrolly.min.js"></script>
<script src="assets/js/jquery.scrollex.min.js"></script>
<script src="assets/js/browser.min.js"></script>
<script src="assets/js/breakpoints.min.js"></script>
<script src="assets/js/util.js"></script>
<script src="assets/js/main.js"></script>
</body>
</html>