API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Sep 1st, 2015
74
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 5.47 KB | None | 0 0
raw download clone embed print report
  1. <!DOCTYPE html>
  2. <html>
  3. <body>
  4.     <canvas id="canvas" width="600" height="600"></canvas>
  5. <script type="text/javascript">
  6. var Delaunay;
  7. (function() {
  8.     "use strict";
  9.     var EPSILON = 1.0 / 1048576.0;
  10.     function supertriangle(vertices) {
  11.         var xmin = Number.POSITIVE_INFINITY,
  12.         ymin = Number.POSITIVE_INFINITY,
  13.         xmax = Number.NEGATIVE_INFINITY,
  14.         ymax = Number.NEGATIVE_INFINITY,
  15.         i, dx, dy, dmax, xmid, ymid;
  16.  
  17.         for(i = vertices.length; i--; ) {
  18.             if(vertices[i][0] < xmin) xmin = vertices[i][0];
  19.             if(vertices[i][0] > xmax) xmax = vertices[i][0];
  20.             if(vertices[i][1] < ymin) ymin = vertices[i][1];
  21.             if(vertices[i][1] > ymax) ymax = vertices[i][1];
  22.         }
  23.         dx = xmax - xmin;
  24.         dy = ymax - ymin;
  25.         dmax = Math.max(dx, dy);
  26.         xmid = xmin + dx * 0.5;
  27.         ymid = ymin + dy * 0.5;
  28.  
  29.         return [
  30.             [xmid - 20 * dmax, ymid - dmax],
  31.             [xmid            , ymid + 20 * dmax],
  32.             [xmid + 20 * dmax, ymid - dmax]
  33.         ];
  34.     }
  35.    
  36.     function circumcircle(vertices, i, j, k) {
  37.         var x1 = vertices[i][0],
  38.         y1 = vertices[i][1],
  39.         x2 = vertices[j][0],
  40.         y2 = vertices[j][1],
  41.         x3 = vertices[k][0],
  42.         y3 = vertices[k][1],
  43.         fabsy1y2 = Math.abs(y1 - y2),
  44.         fabsy2y3 = Math.abs(y2 - y3),
  45.         xc, yc, m1, m2, mx1, mx2, my1, my2, dx, dy;
  46.  
  47.         if(fabsy1y2 < EPSILON && fabsy2y3 < EPSILON)
  48.             throw new Error("Eek! Coincident points!");
  49.  
  50.         if(fabsy1y2 < EPSILON) {
  51.             m2 = -((x3 - x2) / (y3 - y2));
  52.             mx2 = (x2 + x3) / 2.0;
  53.             my2 = (y2 + y3) / 2.0;
  54.             xc = (x2 + x1) / 2.0;
  55.             yc = m2 * (xc - mx2) + my2;
  56.         }
  57.         else if(fabsy2y3 < EPSILON) {
  58.             m1 = -((x2 - x1) / (y2 - y1));
  59.             mx1 = (x1 + x2) / 2.0;
  60.             my1 = (y1 + y2) / 2.0;
  61.             xc = (x3 + x2) / 2.0;
  62.             yc = m1 * (xc - mx1) + my1;
  63.         }
  64.         else {
  65.             m1 = -((x2 - x1) / (y2 - y1));
  66.             m2 = -((x3 - x2) / (y3 - y2));
  67.             mx1 = (x1 + x2) / 2.0;
  68.             mx2 = (x2 + x3) / 2.0;
  69.             my1 = (y1 + y2) / 2.0;
  70.             my2 = (y2 + y3) / 2.0;
  71.             xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
  72.             yc = (fabsy1y2 > fabsy2y3) ?
  73.             m1 * (xc - mx1) + my1 :
  74.             m2 * (xc - mx2) + my2;
  75.         }
  76.         dx = x2 - xc;
  77.         dy = y2 - yc;
  78.  
  79.         return {i: i, j: j, k: k, x: xc, y: yc, r: dx * dx + dy * dy};
  80.     }
  81.  
  82.     function dedup(edges) {
  83.         var i, j, a, b, m, n;
  84.  
  85.         for(j = edges.length; j; ) {
  86.             b = edges[--j];
  87.             a = edges[--j];
  88.        
  89.             for(i = j; i; ) {
  90.                 n = edges[--i];
  91.                 m = edges[--i];
  92.                 if((a === m && b === n) || (a === n && b === m)) {
  93.                     edges.splice(j, 2);
  94.                     edges.splice(i, 2);
  95.                     break;
  96.                 }
  97.             }
  98.         }
  99.     }
  100.  
  101. Delaunay = {
  102.     triangulate: function(vertices) {
  103.         var n = vertices.length,
  104.         i, j, indices, st, open, closed, edges, dx, dy, a, b, c;
  105.  
  106.         if(n < 3)
  107.             return [];
  108.  
  109.         vertices = vertices.slice(0);
  110.        
  111.         indices = new Array(n);
  112.         for(i = n; i--; )
  113.             indices[i] = i;
  114.  
  115.         indices.sort(function(i, j) {
  116.             return vertices[j][0] - vertices[i][0];
  117.         });
  118.  
  119.         st = supertriangle(vertices);
  120.         vertices.push(st[0], st[1], st[2]);
  121.  
  122.         open = [circumcircle(vertices, n + 0, n + 1, n + 2)];
  123.         closed = [];
  124.         edges = [];
  125.  
  126.         for(i = indices.length; i--; edges.length = 0) {
  127.             c = indices[i];
  128.             for(j = open.length; j--; ) {
  129.                 dx = vertices[c][0] - open[j].x;
  130.  
  131.                 if(dx > 0.0 && dx * dx > open[j].r) {
  132.                     closed.push(open[j]);
  133.                     open.splice(j, 1);
  134.                     continue;
  135.                 }
  136.  
  137.                 dy = vertices[c][1] - open[j].y;
  138.  
  139.                 if(dx * dx + dy * dy - open[j].r > EPSILON)
  140.                     continue;
  141.  
  142.                 edges.push(
  143.                     open[j].i, open[j].j,
  144.                     open[j].j, open[j].k,
  145.                     open[j].k, open[j].i
  146.                 );
  147.  
  148.                 open.splice(j, 1);
  149.             }
  150.  
  151.             dedup(edges);
  152.  
  153.             for(j = edges.length; j; ) {
  154.                 b = edges[--j];
  155.                 a = edges[--j];
  156.                 open.push(circumcircle(vertices, a, b, c));
  157.             }
  158.         }
  159.  
  160.         for(i = open.length; i--; )
  161.             closed.push(open[i]);
  162.         open.length = 0;
  163.  
  164.         for(i = closed.length; i--; )
  165.             if(closed[i].i < n && closed[i].j < n && closed[i].k < n)
  166.                 open.push(closed[i].i, closed[i].j, closed[i].k);
  167.  
  168.         return open;
  169.     },
  170.  
  171.     contains: function(tri, p) {
  172.         if((p[0] < tri[0][0] && p[0] < tri[1][0] && p[0] < tri[2][0]) ||
  173.         (p[0] > tri[0][0] && p[0] > tri[1][0] && p[0] > tri[2][0]) ||
  174.         (p[1] < tri[0][1] && p[1] < tri[1][1] && p[1] < tri[2][1]) ||
  175.         (p[1] > tri[0][1] && p[1] > tri[1][1] && p[1] > tri[2][1]))
  176.             return null;
  177.  
  178.         var a = tri[1][0] - tri[0][0],
  179.         b = tri[2][0] - tri[0][0],
  180.         c = tri[1][1] - tri[0][1],
  181.         d = tri[2][1] - tri[0][1],
  182.         i = a * d - b * c;
  183.  
  184.         if(i === 0.0)
  185.             return null;
  186.  
  187.         var u = (d * (p[0] - tri[0][0]) - b * (p[1] - tri[0][1])) / i,
  188.         v = (a * (p[1] - tri[0][1]) - c * (p[0] - tri[0][0])) / i;
  189.  
  190.         if(u < 0.0 || v < 0.0 || (u + v) > 1.0)
  191.             return null;
  192.         return [u, v];
  193.     }
  194. };
  195.  
  196. if(typeof module !== "undefined")
  197.     module.exports = Delaunay;
  198. })();
  199.  
  200. </script>
  201. <script type="text/javascript">
  202.  
  203. var canvas = document.getElementById("canvas"),
  204. ctx = canvas.getContext("2d"),
  205. vertices = new Array(5),
  206. i, x, y;
  207.  
  208. for(i = vertices.length; i--; ) {
  209.     do {
  210.         x = Math.random() - 0.5;
  211.         y = Math.random() - 0.5;
  212.     } while(x * x + y * y > 0.25);
  213.  
  214.     x = (x * 0.96875 + 0.5) * canvas.width;
  215.     y = (y * 0.96875 + 0.5) * canvas.height;
  216.     vertices[i] = [x, y];
  217. }
  218.  
  219. console.time("triangulate");
  220. var triangles = Delaunay.triangulate(vertices);
  221. console.timeEnd("triangulate");
  222.  
  223. for(i = triangles.length; i; ) {
  224.     ctx.beginPath();
  225.     --i; ctx.moveTo(vertices[triangles[i]][0], vertices[triangles[i]][1]);
  226.     --i; ctx.lineTo(vertices[triangles[i]][0], vertices[triangles[i]][1]);
  227.     --i; ctx.lineTo(vertices[triangles[i]][0], vertices[triangles[i]][1]);
  228.     ctx.closePath();
  229.     ctx.stroke();
  230. }
  231. </script>
  232. </body>
  233. </html>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!