forked from gorhill/Javascript-Voronoi
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rhill-voronoi.html
108 lines (108 loc) · 10.6 KB
/
rhill-voronoi.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
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<title>Javascript implementation of Steven J. Fortune's algorithm to compute Voronoi diagrams</title>
<meta name="Keywords" lang="en" content="voronoi, fortune, javascript, raymond hill"/>
<!--[if lte IE 8]><script type="text/javascript" src="excanvas/excanvas.compiled.js"></script><![endif]-->
<script type="text/javascript" src="rhill-voronoi.js"></script>
<style type="text/css">
body {font-family:tahoma,verdana,arial;font-size:13px;margin:0;padding:0}
body > div {margin-left:4px;margin-right:4px;}
body > div > div {margin:0;border:1px solid #ccc;border-top:0;padding:4px;}
h1 {margin:0 0 0.5em 0;padding: 4px 5em 4px 4px;font:bold large sans-serif;background-color:#c9d7f1;}
h4 {font-size:14px;margin:0.5em 0 0 0;border:0;border-bottom:solid 1px #c9d7f1;padding:2px;background-color:#e5ecf9;}
h4 > span {cursor:pointer}
textarea {font-size:11px;color:gray}
table {padding:0;border:1px solid #eee}
table tr:first-child {background-color:#e4f4e4;font-weight:bold;}
table tr:first-child ~ tr:nth-child(odd) {background-color:#f4f4f4}
table td {margin:0;padding:2px;border:0;vertical-align:top;background-color:transparent;}
#canvasParent {margin-top:0;margin-bottom:1em;padding:0;border:0}
</style>
</head>
<body onload="Voronoi.init();">
<a href="https://github.com/gorhill/Javascript-Voronoi"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_red_aa0000.png" alt="Fork me on GitHub"></a>
<h1>Javascript implementation of Steven J. Fortune's algorithm to compute Voronoi diagrams</h1>
<div id="divroot" style="width:800px;">
<p style="margin-top:0;margin-bottom:0"><b>Main page</b><ul style="margin-top:0">
<li><a href="rhill-voronoi-demo1.html">Demo 1: measuring peformance</a>
<li><a href="rhill-voronoi-demo2.html">Demo 2: a bit of interactivity</a>
<li><a href="rhill-voronoi-demo3.php">Demo 3: Fancy tiling</a>
<li><a href="rhill-voronoi-demo4.html">Demo 4: Looking up a Voronoi cell using a quadtree</a>
<li><a href="rhill-voronoi-demo5.html">Demo 5: Lloyd's relaxation</a>
<li><a href="http://www.raymondhill.net/blog/?p=458#comments">Comments</a>
</ul></p>
<h4 class="divhdr">Intro</h4>
<div class="divinfo" id="voronoiIntro">
<p>See my <a href="http://www.raymondhill.net/blog/?p=458">blog post</a> regarding this page. This page uses an out of date version (and customized to serve as a tutorial of Fortune's algorithm) of the Javascript Voronoi object. However the demo pages listed above use the latest version.</p>
</div>
<h4 class="divhdr">Sites generator <span id="voronoiGeneratorCollapse">▵</span></h4>
<div class="divinfo" id="voronoiGenerator">
<input type="button" value="Generate" onclick="Voronoi.clearSites();Voronoi.generateSites(parseInt(document.getElementById('voronoiNumberSites').value,10));"/> or <input type="button" value="Add" onclick="Voronoi.generateSites(parseInt(document.getElementById('voronoiNumberSites').value,10));"/><input id="voronoiNumberSites" type="text" value="100" size="5" maxlength="5"/> sites randomly (Warning: performance might suffer the more sites you add.)<br/>
<div style="display:inline-block;vertical-align:top;"><input id="voronoiParseSites" type="button" value="Parse as sites" onclick="Voronoi.parseSites(document.getElementById('voronoiUserInput').value);"/><br/>
<input id="voronoiParseLattices" type="button" value="Parse as lattices" onclick="Voronoi.parseLattices(document.getElementById('voronoiUserInput').value);"/></div>
<div style="display:inline-block;vertical-align:top;"><textarea id="voronoiUserInput" rows="4" cols="80">Any non-digit character is interpreted as a separator. Sites: The input is scanned for consecutive pairs of values which are interpreted as (x,y). Lattices: The input is scanned for consecutive quadruplets of values which are interpreted as (offset x, offset y, delta x, delta y). Example, try: 0,0,60,100,30,50,60,100</textarea></div>
<input id="voronoiClearSites" type="button" value="Clear all sites" onclick="Voronoi.clearSites();"/>
</div>
<h4 class="divhdr">Canvas <span id="voronoiCanvasControlsCollapse">▵</span></h4>
<div id="voronoiCanvasControls">
<div style="width:80%;margin:0;border:0;display:inline-block;vertical-align:top;"><input id="voronoiCanvasSize" type="button" value="Set" onclick="Voronoi.setCanvasSize(parseInt(document.getElementById('voronoiWidth').value,10),parseInt(document.getElementById('voronoiHeight').value,10));Voronoi.setCanvasMargin(parseInt(document.getElementById('voronoiCanvasMargin').value,10));document.getElementById('divroot').style.width=String(Math.max(Voronoi.canvas.width,800))+'px'"/> canvas W × H to <input id="voronoiWidth" type="text" value="800" size="4" maxlength="4" /> pixels × <input id="voronoiHeight" type="text" value="600" size="4" maxlength="4" /> pixels, with a margin of <input id="voronoiCanvasMargin" type="text" value="0" size="2" maxlength="2" /> pixels.</div>
<div style="width:19%;margin:0;border:0;display:inline-block;vertical-align:top;text-align:right">
<input id="voronoiColourize" type="button" value="Colourize" onclick="Voronoi.drawCells();"/></div>
</div>
<div id="canvasParent">
<noscript>You need to enable Javascript in your browser for this page to display properly.</noscript>
<canvas id="voronoiCanvas" style="cursor:crosshair" width="800" height="600"></canvas>
<div id="voronoiNoCanvasAlert" style="display:none;padding:1em;background-color:#fcc;color:black;">
<p>Your browser doesn't support the HTML5 <canvas> element technology.</p>
<p>See <a target="_blank" href="http://en.wikipedia.org/wiki/Canvas_(HTML_element)">Wikipedia</a> for information on which browsers support the <u>HTML5 <canvas></u> technology.</p>
</div>
</div>
<h4 class="divhdr">Event queue</h4>
<div class="divinfo">
<div style="width:49%;margin:0;border:0;display:inline-block;">
<input id="voronoiProcessAll" type="button" value="Process all" onclick="Voronoi.processQueueAll();"/><br/>
<input id="voronoiProcessOne" type="button" value="Process one" onclick="Voronoi.processQueueOne();Voronoi.draw();Voronoi.dumpBeachline();"/> (down arrow works too)<br/>
<input id="voronoiProcessNDo" type="button" value="Process" onclick="Voronoi.processQueueN(parseInt(document.getElementById('voronoiProcessN').value,10));Voronoi.draw();Voronoi.dumpBeachline();"/> <input id="voronoiProcessN" type="text" value="10" size="4" maxlength="4"/><br/>
<input id="voronoiReset" type="button" value="Reset" onclick="Voronoi.reset();"/>
</div>
<div style="width:49%;margin:0;border:0;display:inline-block;vertical-align:top">
<input id="voronoiMoveSweepline" type="button" value="Move sweep line" onclick="Voronoi.processUpTo(Voronoi.sweep+parseInt(document.getElementById('voronoiMoveSweeplineN').value,10));Voronoi.draw();Voronoi.dumpBeachline();"/> <input id="voronoiMoveSweeplineN" type="text" value="4" size="3" maxlength="3"/> pixel(s)<br/>
<input id="voronoiAnimateSweepline" type="button" value="Animate sweep line" onclick="VoronoiAnimate(parseInt(document.getElementById('voronoiMoveSweeplineN').value,10),parseInt(document.getElementById('voronoiAnimateSweeplineDelay').value,10));document.getElementById('voronoiAnimateSweeplineDelay').value=VoronoiAnimateDelay;"/> every <input id="voronoiAnimateSweeplineDelay" type="text" value="100" size="4" maxlength="4"/> ms <input id="voronoiAnimateSweeplineStop" type="button" value="Stop" onclick="VoronoiAnimateStop();"/><br/></div>
</div>
<h4 class="divhdr">Scrutinize...</h4>
<div class="divinfo">
<!-- <input id="voronoiDumpBeachline" type="button" value="Examine beachline"/> <input id="voronoiDumpVertices" type="button" value="Examine vertices"/> <input id="voronoiDumpEdges" type="button" value="Examine edges"/> <input id="voronoiDumpPolygons" type="button" value="Examine polygons"/> -->
Red beach sections are collapsing (meaning there is a Fortune circle event associated with them), while green beach sections are expanding. When all the Fortune events have been processed, a beachline most likely still exists, which means the start and/or end points of the edges implied by each pair of beach sections are not connected, in which case we must ‘manually’ connect these dangling lines to the bounding box, or discard them if they are outside the viewport.
<div id="console" style="margin-top:1em;margin-bottom:0;margin-left:1em;margin-right:0"></div>
</div>
<h4 class="divhdr">Portions of this software are based on, or depend on, or are inspired from the work of...</h4>
<div class="divinfo">
<ul style="margin-top:0;margin-bottom:0">
<li><a target="_blank" href="http://en.wikipedia.org/wiki/Fortune%27s_Algorithm">“Fortune's algorithm”</a> by <a href="http://ect.bell-labs.com/who/sjf/">Steven Fortune</a>: For his clever algorithm to compute Voronoi diagrams. (<a href="http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt">Powerpoint detailing the algorithm</a>)</li>
<li><a href="http://alecmce.com/as3/parabolas-and-quadratic-bezier-curves">Alec McEachran's code</a> to translate a parabola's focal & directrix into parameters for <a href="http://en.wikipedia.org/wiki/Canvas_element">html5 <code><canvas></code></a>' <code>quadraticCurveTo()</code> method. It occurred to me I could use a <a href="http://en.wikipedia.org/wiki/B%C3%A9zier_curve">Bézier curve</a> to draw a parabolic front, and when I plugged "bézier from focus directrix" in a search engine to find out if someone already went through this, Alec's site was on the first page of results, and his tutorial and <a href="http://github.com/alecmce/as3geometry/blob/master/src/as3geometry/geom2D/ui/ParabolaDrawer.as">accompanying code</a> worked like a charm. His code allows for parabolas with any orientation, so it could be simplified for the current case where parabolas are always oriented vertical and upward.</li>
<li><a target="_blank" href="http://www.skytopia.com/project/articles/compsci/clipping.html">“The Liang-Barsky line clipping algorithm in a nutshell!”</a>, to efficiently clip a line within a rectangle.</li>
<!--[if IE]>
<li><a href="http://code.google.com/p/explorercanvas/">excanvas.js</a>: To simulate support of HTML5 <a href="http://en.wikipedia.org/wiki/Canvas_element"><code><canvas></code></a> element in Microsoft's Internet Explorer.</li>
<![endif]-->
</ul>
</div>
</div>
<script type="text/javascript">
(function(){
var els=document.querySelectorAll('h4 > span');
for (var i=0; i<els.length; i++){
var el=els[i];
el.onclick=function(){
var id=this.id.replace('Collapse','');
var div=document.getElementById(id);
var expanded=div.style.display=='';
div.style.display=expanded?'none':'';
this.innerHTML=expanded?'▿':'▵';
};
}
})();
</script>
</body>
</html>