Download code

Jump to: navigation, search

Back to Quickhull_(Javascript)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

qh.js

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Quickhull_(Javascript)?oldid=19191
 14 */
 15 
 16 function getDistant(cpt, bl) {
 17     var Vy = bl[1][0] - bl[0][0];
 18     var Vx = bl[0][1] - bl[1][1];
 19     return (Vx * (cpt[0] - bl[0][0]) + Vy * (cpt[1] -bl[0][1]))
 20 }
 21 
 22 
 23 function findMostDistantPointFromBaseLine(baseLine, points) {
 24     var maxD = 0;
 25     var maxPt = new Array();
 26     var newPoints = new Array();
 27     for (var idx in points) {
 28         var pt = points[idx];
 29         var d = getDistant(pt, baseLine);
 30         
 31         if ( d > 0) {
 32             newPoints.push(pt);
 33         } else {
 34             continue;
 35         }
 36         
 37         if ( d > maxD ) {
 38             maxD = d;
 39             maxPt = pt;
 40         }
 41     
 42     } 
 43     return {'maxPoint':maxPt, 'newPoints':newPoints}
 44 }
 45 
 46 var allBaseLines = new Array();
 47 function buildConvexHull(baseLine, points) {
 48     
 49     allBaseLines.push(baseLine)
 50     var convexHullBaseLines = new Array();
 51     var t = findMostDistantPointFromBaseLine(baseLine, points);
 52     if (t.maxPoint.length) { // if there is still a point "outside" the base line
 53         convexHullBaseLines = 
 54             convexHullBaseLines.concat( 
 55                 buildConvexHull( [baseLine[0],t.maxPoint], t.newPoints) 
 56             );
 57         convexHullBaseLines = 
 58             convexHullBaseLines.concat( 
 59                 buildConvexHull( [t.maxPoint,baseLine[1]], t.newPoints) 
 60             );
 61         return convexHullBaseLines;
 62     } else {  // if there is no more point "outside" the base line, the current base line is part of the convex hull
 63         return [baseLine];
 64     }    
 65 }
 66 function getConvexHull(points) {
 67     //find first baseline
 68     var maxX, minX;
 69     var maxPt, minPt;
 70     for (var idx in points) {
 71         var pt = points[idx];
 72         if (pt[0] > maxX || !maxX) {
 73             maxPt = pt;
 74             maxX = pt[0];
 75         }
 76         if (pt[0] < minX || !minX) {
 77             minPt = pt;
 78             minX = pt[0];
 79         }
 80     }
 81     var ch = [].concat(buildConvexHull([minPt, maxPt], points),
 82                        buildConvexHull([maxPt, minPt], points))
 83     return ch;
 84 }
 85 function getRandomPoints(numPoint, xMax, yMax) {
 86     var points = new Array();
 87     var phase = Math.random() * Math.PI * 2;
 88     for (var i = 0; i < numPoint/2; i++) {
 89         var r =  Math.random()*xMax/4;
 90         var theta = Math.random() * 1.5 * Math.PI + phase;
 91         points.push( [ xMax /4 + r * Math.cos(theta), yMax/2 + 2 * r * Math.sin(theta) ] )
 92     }
 93     var phase = Math.random() * Math.PI * 2;
 94     for (var i = 0; i < numPoint/2; i++) {
 95         var r =  Math.random()*xMax/4;
 96         var theta = Math.random() * 1.5 * Math.PI + phase;
 97         points.push( [ xMax /4 * 3 +  r * Math.cos(theta), yMax/2 +  r * Math.sin(theta) ] )
 98     }
 99     return points
100 }
101 
102 
103 function plotBaseLine(baseLine,color) {
104     var ctx = document.getElementById('qh_demo').getContext('2d');
105     var pt1 = baseLine[0]
106     var pt2 = baseLine[1];
107     ctx.save()
108     ctx.strokeStyle = color;
109     ctx.beginPath();
110     ctx.moveTo(pt1[0],pt1[1]);
111     ctx.lineTo(pt2[0],pt2[1]);
112     ctx.stroke();
113     ctx.restore();
114 }   
115 
116 
117 
118 var pts;
119 
120 function qhPlotPoints() {
121     ctx = document.getElementById('qh_demo').getContext('2d');
122     ctx.clearRect(0,0,200,200);
123     ctx.fillStyle = 'rgb(0,0,0)';
124     pts = getRandomPoints(250,200,200);
125     for (var idx in pts) {
126         var pt = pts[idx];
127         ctx.fillRect(pt[0],pt[1],2,2);
128     }
129 }
130 
131 
132 
133 function qhPlotConvexHull() {
134     var ch = getConvexHull(pts);
135     var eBL = allBaseLines[0];
136     function plotIntermediateBL() {
137         var l = allBaseLines.shift();
138         if (l) {
139             plotBaseLine(l, 'rgb(180,180,180)');
140             setTimeout(plotIntermediateBL, 250);
141         } else {
142             for (var idx in ch) {    
143                 var baseLine = ch[idx];
144                 plotBaseLine(baseLine, 'rgb(255,0,0)');
145             }
146             plotBaseLine(eBL,'rgb(0,255,0)');
147         }
148     }
149     plotIntermediateBL();
150 }


hijacker
hijacker
hijacker
hijacker

qh.html

 1 <html>
 2 <head>
 3 <script language="javascript" src="./qh.js"></script>
 4 </head>
 5 <body>
 6 <button onclick='qhPlotPoints()'>Get Random Points</button> 
 7 <button onclick='qhPlotConvexHull()'>Get convex hull</button><br>
 8 <canvas id="qh_demo" width=200 height=200 style='margin:20pt;border:solid 1px #888;'></canvas>
 9 </body>
10 </html>


hijacker
hijacker
hijacker
hijacker