forked from gregorybchris/chans
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
171 lines (156 loc) · 9.28 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
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
<!DOCTYPE html>
<html>
<head>
<title>Chan's Algorithm Demo</title>
<link rel="icon" type="image/ico" href="images/icons/favicon.ico">
<meta charset="utf-8" />
<meta name="description" content="Chan's Algorithm Demo">
<meta name="keywords" content="Chris,Gregory,Computational,
Geometry,Comp163,Javascript,Computer,Science,Tufts,University">
<meta name="author" content="Chris Gregory">
<link href="styles/reset.css" rel="stylesheet" type="text/css">
<link href="styles/lib/sweetalert.css" rel="stylesheet" type="text/css"/>
<link href="styles/styles.less" rel="stylesheet/less" type="text/css"/>
<script src="scripts/lib/less.min.js" type="text/javascript"></script>
<script src="scripts/lib/velocity.min.js"></script>
<script src="scripts/lib/jquery.min.js"></script>
<script src="scripts/lib/hotkeys.js"></script>
<script src="scripts/lib/d3.min.js"></script>
<script src="scripts/lib/sweetalert.min.js"></script>
<script src="scripts/lib/queue.min.js"></script>
</head>
<body>
<div class="header">
<div class="title">Chan's Algorithm Demo</div>
<div class="credits">Chris Gregory © 2016</div>
</div>
<div class="content">
<div class="graphics-panel">
<svg id="graphics" class="graphics"></svg>
</div><div class="dialog-panel">
<div class="explanation">
<span class="step-counter">Step: <span id="step">0</span> of 5</span>
<!-- WELCOME STEP -->
<div data-step="0" class="explanation-section">
<p class="explanation-text">This is a dynamic demo of
<a class="link" href="https://en.wikipedia.org/wiki/Chan's_algorithm" target="_blank">Chan's Algorithm</a>,
an optimal, output-sensitive algorithm for computing the
<a class="link" href="https://en.wikipedia.org/wiki/Convex_hull" target="_blank">convex hull</a> of a
point set in <span class="big-o">O(nlogh)</span> time.</p>
<p class="explanation-text"><span class="emph">n</span> is the number of input points
and <span class="emph">h</span> is the number of output hull points.</p>
<p class="explanation-text">Hit the
<a href="https://en.wikipedia.org/wiki/Space_bar" target="_blank" class="link">space bar</a>
or use the buttons below to walk through the
steps of the algorithm.</p>
<br /><br />
<p class="explanation-text">
Additional resources:
<br />
<a href="http://www.cs.ucsb.edu/~suri/cs235/ChanCH.pdf" target="_blank" class="link">Chan's original paper</a>
<br />
<a href="https://www.youtube.com/watch?v=020v2md_WHw" target="_blank" class="link">Video walkthrough</a>
<br />
<a href="http://tomswitzer.net/2010/12/2d-convex-hulls-chans-algorithm" target="_blank" class="link">Python implementation</a>
<br />
<a href="http://www.utdallas.edu/~daescu/convexhull.pdf" target="_blank" class="link">Mathematical explanation</a>
<br />
<a href="https://www.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf" target="_blank" class="link">Convex hulls pseudocode</a>
<br />
<a href="https://bost.ocks.org/mike/algorithms" target="_blank" class="link">Visualizing algorithms</a>
<br />
<a href="https://github.com/gregorybchris" target="_blank" class="link">Demo source code</a>
<br />
<a href="https://d3js.org" target="_blank" class="link">D3.js</a>
<a href="http://velocityjs.org" target="_blank" class="link">Velocity.js</a>
<a href="http://lesscss.org/" target="_blank" class="link">Less.js</a>
</p>
</div>
<!-- POINT CREATION STEP -->
<div data-step="1" class="explanation-section">
<p class="explanation-text">First, let's add some points to our plane.
You can <span class="emph">click to the left</span> to add your own points or <span class="emph">press P</span>
to add random points.</p>
<p class="explanation-text">In the next few steps we will be grouping our point set into
smaller convex hulls and then finding the convex hull of those smaller hulls.</p>
<p class="explanation-text">Hit the <span class="emph">space bar</span> when you are ready to continue.</p>
</div>
<!-- GROUPING STEP -->
<div data-step="2" class="explanation-section">
<p class="explanation-text">Now that we have our points, we pick some small constant <span class="emph">m</span>.
The choice of <span class="emph">m</span> will be explained later in the demo.</p>
<p class="explanation-text">We partition our point set into groups of <span class="emph">m</span> points.</p>
<p class="explanation-text">In this example <span class="emph">m</span> is set to <span class="emph">5</span> and each color
represents a group of <span class="emph">m</span> points.</p>
</div>
<!-- GRAHAM SCAN STEP -->
<div data-step="3" class="explanation-section">
<p class="explanation-text">Given these groups of <span class="emph">m</span>
points, we find the convex hull of
each group with an <span class="big-o">O(nlogn)</span>
algorithm. In this demo we use
<a class="link" href="https://en.wikipedia.org/wiki/Graham_scan" target="_blank">Graham Scan</a>.</p>
<p class="explanation-text">Because each group has size <span class="emph">m</span>
we can convex hull each group in <span class="big-o">O(mlogm)</span>.
There are <span class="big-o">O(n/m)</span> groups.</p>
<p class="explanation-text">In total this step takes <span class="big-o">O(nlogm)</span> time.</p>
</div>
<!-- JARVIS MARCH STEP -->
<div data-step="4" class="explanation-section">
<p class="explanation-text">We then use
<a class="link" href="https://en.wikipedia.org/wiki/Gift_wrapping_algorithm" target="_blank">Gift wrapping</a>,
an <span class="big-o">O(nh)</span> algorithm on the small convex hulls.</p>
<p class="explanation-text">To use gift wrapping on convex hulls rather than points we
can perform a
<a class="link" href="https://en.wikipedia.org/wiki/Binary_search_algorithm" target="_blank">binary search</a>
to determine the
<a class="link" href="https://en.wikipedia.org/wiki/Tangent" target="_blank">tangent</a>
between an extreme point and a convex hull.
A binary search on a small convex hull takes <span class="big-o">O(logm)</span>.</p>
<p class="explanation-text">We can compute tangents for all <span class="big-o">O(n/m)</span>
groups in <span class="big-o">O(n/m * logm)</span> time. We use the tangent with the largest angle.
By doing this we get one edge of the overall convex hull.
We must do this for all <span class="emph">h</span> hull points.</p>
<p class="explanation-text">We can assume for now that <span class="emph">m</span> < <span class="emph">h</span> so this step is
<span class="big-o">O(nlogh)</span> like the last step.</p>
<p class="explanation-text">We have to be careful that we do not exceed <span class="emph">h</span>
iterations of gift wrapping given our <span class="big-o">O(n/m)</span> input size.
Therefore, we halt gift wrapping execution after <span class="emph">m</span> iterations.</p>
</div>
<!-- COMPLETED HULL STEP -->
<div data-step="5" class="explanation-section">
<p class="explanation-text">We want to increase <span class="emph">m</span> until it equals <span class="emph">h</span>.
If we increase <span class="emph">m</span> too slowly our gift wrapping time overall will surpass
<span class="big-o">O(nlogh)</span>. On the other hand, if we increase <span class="emph">m</span> too quickly
some gift wrapping iteration will take much more than <span class="big-o">O(nlogh)</span> on its own.</p>
<p class="explanation-text">To solve this problem we can utilize a
<a class="link" href="https://en.wikipedia.org/wiki/Double_exponential_function" target="_blank">double exponential</a>.
We let
<span class="emph">m</span> = <span class="emph">2<sup>2<sup>t</sup></sup></span>
where <span class="emph">t</span> is the current iteration number.</p>
<p class="explanation-text">We throw away the work we do in each attempt
at finding an <span class="emph">m</span> equal to <span class="emph">h</span>. Because iterations
form a
<a class="link" href="https://en.wikipedia.org/wiki/Geometric_series" target="_blank">geometric series</a>
the total work is still <span class="big-o">O(nlogh)</span>.</p>
<p class="explanation-text">We now have the convex hull of our orignal point set.</p>
<p class="explanation-text">Press restart to try it again!</p>
</div>
</div>
<div class="navigation">
<div id="restart-button" class="nav-button">
<span class="nav-button-text">Restart</span>
</div>
<!-- <div id="replay-button" class="nav-button">
<span class="nav-button-text">Replay</span>
</div> -->
<div id="next-button" class="nav-button">
<span class="nav-button-text">Next</span>
</div>
</div>
</div>
</div>
<script type="text/javascript" src="scripts/demo/graphics.js"></script>
<script type="text/javascript" src="scripts/demo/demo.js"></script>
</body>
</html>