-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
124 lines (123 loc) · 6.64 KB
/
index.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<title>Algorithm Visualization</title>
<link rel="stylesheet" type="text/css" href="bootstrap.min.css">
<link rel="stylesheet" type="text/css" href="style.css">
</head>
<body>
<main class="center-content">
<div id="project-description">
<h1>Geometric Algorithm Visualizations</h1>
<h6>by Gavin Nishizawa</h6>
<h4>Project Goal</h4>
<p>
The project is to build an interactive educational tool for geometric algorithms, which is able to simultaneously
highlight the geometric data currently being operated on and the high level algorithmic task being worked on.
This should provide a visual link between the idea of the algorithm, and the visualized geometry of the problem.
</p>
</div>
<div id="convexHull">
<h2>Convex Hull via Graham's Scan</h2>
<p>An interactive visualization of the graham's scan algorithm for computing the convex hull of a set of points.</p>
<h4>Background</h4>
<p>
The convex hull of a set of points is the smallest convex shape which encloses the set of points.
A planar shape is convex if none of its interior angles are greater than 180 degrees.
Graham's scan is an incremental construction algorithm for computing the convex hull of a set of points.
The algorithm constructs the upper and lower portions of the convex hull independently and joins the results.
The upper and lower portions of the convex hull are split by the leftmost and rightmost points.
It is an incremental construction algorithm because the hull is partially constructed as each point is added one at a time.
</p>
<h4>Algorithm Overview</h4>
<p>
The algorithm starts by sorting the points by x (primary) and y (secondary).
For both the upper and lower hull sections, the following steps occur.
Initialize a stack with the first 2 points.
Repeatedly pop a point from the top of the stack while the interior angle between the next point to be added,
and the top two points on the stack is greater than 180 degrees.
Finally the add the point onto the stack before proceeding to the next point.
The upper and lower hull sections process the points in opposite directions, one after the other.
</p>
<h4>Instructions</h4>
<ul>
<li>Add specific points either by clicking or tapping on the canvas</li>
<li>Add 10 random points each time you select the Add 10 Random Points button</li>
<li>Play the algorithm visualization automatically with the Play/Pause button</li>
<li>Adjust speed of automatic play with the speed sliderbar</li>
<li>Use the step button while the algorithm is not playing to control each step of the algorithm</li>
<li>Use the reset button to reset the state of the algorithm</li>
<li>Wait for the algorithm to finish or reset it before adding new points</li>
</ul>
<div id="controls">
<button class="btn btn-dark control control-btn" id="playConvexHull">Play</button>
<button class="btn btn-outline-dark control control-btn" id="stepConvexHull">Step</button>
<label for="playInterval">Speed:
<input class="control align-middle" type="range" id="playInterval" min=0 max=9 step=1 value="2"/>
</label>
<button class="btn btn-outline-dark control control-btn" id="resetConvexHull">Reset</button>
<button class="btn btn-outline-dark control control-btn" id="add10Points">Add 10 Random Points</button>
</div>
<div class="row">
<div class="col col-sm">
<canvas id="algo-visual" height="400px" width="600px"></canvas>
</div>
<div class="col col-sm">
<h4>Algorithm Steps</h4>
<ol class="control" id="algoStateList">
<li>Sort the points data structure by x value then y value</li>
<li>Compute the upper hull
<ul class="font-weight-light ">
<li>Check interior angle</li>
<li>Pop old point</li>
<li>Push new point</li>
</ul>
</li>
<li>Compute the lower hull
<ul class="font-weight-light ">
<li>Check interior angle</li>
<li>Pop old point</li>
<li>Push new point</li>
</ul>
</li>
</ol>
</div>
</div>
<p>High-level algorithm state: <span class="control" id="highLevelStateDesc">Not running</span></p>
</div>
<div>
<h2>References</h2>
<ol>
<li>
Paper.js : <a href="http://paperjs.org" target="_blank">paperjs.org</a>
</li>
<li>
Mount, David. “CMSC 754 Computational Geometry. Lecture Notes” UMD Department of Computer Science,
2012, http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf
</li>
<li>
Bootstrap : <a href="https://getbootstrap.com" target="_blank">getbootstrap.com</a>
</li>
</ol>
</div>
</main>
<!-- Load the Paper.js library -->
<script type="text/javascript" src="js/paper-full.min.js"></script>
<!-- Utility functions -->
<script type="text/javascript" src="js/util.js"></script>
<!-- Canvas -->
<script type="text/javascript" src="js/canvas.js"></script>
<!-- State -->
<script type="text/javascript" src="js/state.js"></script>
<!-- Load graham scan js code -->
<script type="text/javascript" src="js/graham_scan.js"></script>
<!-- Drawing functions -->
<script type="text/javascript" src="js/draw.js"></script>
<!-- Interface -->
<script type="text/javascript" src="js/interface.js"></script>
<!-- Main -->
<script type="text/javascript" src="js/main.js"></script>
</body>
</html>