​

function calcCircumCirc(v0, v1, v2) {

  var A = v1.x - v0.x;

  var B = v1.y - v0.y;

  var C = v2.x - v0.x;

  var D = v2.y - v0.y;

​

  var E = A * (v0.x + v1.x) + B * (v0.y + v1.y);

  var F = C * (v0.x + v2.x) + D * (v0.y + v2.y);

​

  var G = 2.0 * (A * (v2.y - v1.y) - B * (v2.x - v1.x));

​

  var dx, dy;

​

  // Collinear points, get extremes and use midpoint as center

  if (Math.round(Math.abs(G)) == 0) {

    var minx = Math.min(v0.x, v1.x, v2.x);

    var miny = Math.min(v0.y, v1.y, v2.y);

    var maxx = Math.max(v0.x, v1.x, v2.x);

    var maxy = Math.max(v0.y, v1.y, v2.y);

​

    center = new Vertex((minx + maxx) / 2, (miny + maxy) / 2);

​

    dx = center.x - minx;

    dy = center.y - miny;

  } else {

    var cx = (D * E - B * F) / G;

    var cy = (A * F - C * E) / G;

​

    center = new Vertex(cx, cy);

​

    dx = center.x - v0.x;

    dy = center.y - v0.y;

  }

  radius = Math.sqrt(dx * dx + dy * dy);

​

  return {c: center, r: radius}

}

​

​

function getBounding2(enclosing){

  ang1 = 0

  ang2 = TAU/3

  ang3 = TAU/3*2

​

  let ev0 = new Vertex(enclosing.x + enclosing.r*cos(ang1)*2,

          enclosing.y + enclosing.r*sin(ang1)*2)

  let ev1 = new Vertex(enclosing.x + enclosing.r*cos(ang2)*2,

          enclosing.y + enclosing.r*sin(ang2)*2)

  let ev2 = new Vertex(enclosing.x + enclosing.r*cos(ang3)*2,

          enclosing.y + enclosing.r*sin(ang3)*2)

​

  return new Triangle(ev0, ev1, ev2)

}

​

function getPerpendicular(p1, p2) {

  let slope = (p2.y - p1.y) / (p2.x - p1.x) + 0.0000000001

  let reciprocal = -1 / slope

  let b = (p1.y + p2.y) / 2 - (p1.x + p2.x) / 2 * reciprocal

​

  return {

    m: reciprocal,

    b: b

  };

}

​

​

// line intercept math by Paul Bourke http://paulbourke.net/geometry/pointlineplane/

// Determine the intersection point of two line segments

// Return FALSE if the lines don't intersect

function intersect(p1, p2, p3, p4) {

  let x1 = p1.x,

    y1 = p1.y,

    x2 = p2.x,

    y2 = p2.y,

    x3 = p3.x,

    y3 = p3.y,

    x4 = p4.x,

    y4 = p4.y;

​

  // Check if none of the lines are of length 0

  if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {

    return false

  }

​

  denominator = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))

​

  // Lines are parallel

  if (denominator === 0) {

    return false

  }

​

  let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator

  let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator

​

  /* this part can be omitted becasue we assume that the lines expand to infinity */

​

  // // is the intersection along the segments

  // if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {

  //    return false

  // }

​

  // Return a object with the x and y coordinates of the intersection

  let x = x1 + ua * (x2 - x1)

  let y = y1 + ua * (y2 - y1)

​

  return {

    x,

    y

  }

}

​

​

/*

 * Smallest enclosing circle - Library (compiled from TypeScript)

 *

 * Copyright (c) 2022 Project Nayuki

 * https://www.nayuki.io/page/smallest-enclosing-circle

 *

 * This program is free software: you can redistribute it and/or modify

 * it under the terms of the GNU Lesser General Public License as published by

 * the Free Software Foundation, either version 3 of the License, or

 * (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public License

 * along with this program (see COPYING.txt and COPYING.LESSER.txt).

 * If not, see <http://www.gnu.org/licenses/>.

 */

"use strict";

var Point = /** @class */ (function () {

    function Point(x, y) {

        this.x = x;

        this.y = y;

    }

    return Point;

}());

var Circle = /** @class */ (function () {

    function Circle(x, y, r) {

        this.x = x;

        this.y = y;

        this.r = r;

    }

    return Circle;

}());

/*

 * Returns the smallest circle that encloses all the given points. Runs in expected O(n) time, randomized.

 * Note: If 0 points are given, null is returned. If 1 point is given, a circle of radius 0 is returned.

 */

// Initially: No boundary points known

function makeCircle(points) {

    // Clone list to preserve the caller's data, do Durstenfeld shuffle

    var shuffled = points.slice();

    for (var i = points.length - 1; i >= 0; i--) {

        var j = Math.floor(Math.random() * (i + 1));

        j = Math.max(Math.min(j, i), 0);

        var temp = shuffled[i];

        shuffled[i] = shuffled[j];

        shuffled[j] = temp;

    }

    // Progressively add points to circle or recompute circle

    var c = null;

    shuffled.forEach(function (p, i) {

        if (c === null || !isInCircle(c, p))

            c = makeCircleOnePoint(shuffled.slice(0, i + 1), p);

    });

​

    return c;

}

// One boundary point known

function makeCircleOnePoint(points, p) {

    var c = new Circle(p.x, p.y, 0);

    points.forEach(function (q, i) {

        if (!isInCircle(c, q)) {

            if (c.r == 0)

                c = makeDiameter(p, q);

            else

                c = makeCircleTwoPoints(points.slice(0, i + 1), p, q);

        }

    });

    return c;

}

// Two boundary points known

function makeCircleTwoPoints(points, p, q) {

    var circ = makeDiameter(p, q);

    var left = null;

    var right = null;

    // For each point not in the two-point circle

    for (var _i = 0, points_1 = points; _i < points_1.length; _i++) {

        var r = points_1[_i];

        if (isInCircle(circ, r))

            continue;

        // Form a circumcircle and classify it on left or right side

        var cross = crossProduct(p.x, p.y, q.x, q.y, r.x, r.y);

        var c = makeCircumcircle(p, q, r);

        if (c === null)

            continue;

        else if (cross > 0 && (left === null || crossProduct(p.x, p.y, q.x, q.y, c.x, c.y) > crossProduct(p.x, p.y, q.x, q.y, left.x, left.y)))

            left = c;

        else if (cross < 0 && (right === null || crossProduct(p.x, p.y, q.x, q.y, c.x, c.y) < crossProduct(p.x, p.y, q.x, q.y, right.x, right.y)))

            right = c;

    }

    // Select which circle to return

    if (left === null && right === null)

        return circ;

    else if (left === null && right !== null)

        return right;

    else if (left !== null && right === null)

        return left;

    else if (left !== null && right !== null)

        return left.r <= right.r ? left : right;

    else

        throw new Error("Assertion error");

}

function makeDiameter(a, b) {

    var cx = (a.x + b.x) / 2;

    var cy = (a.y + b.y) / 2;

    var r0 = distance(cx, cy, a.x, a.y);

    var r1 = distance(cx, cy, b.x, b.y);

    return new Circle(cx, cy, Math.max(r0, r1));

}

function makeCircumcircle(a, b, c) {

    // Mathematical algorithm from Wikipedia: Circumscribed circle

    var ox = (Math.min(a.x, b.x, c.x) + Math.max(a.x, b.x, c.x)) / 2;

    var oy = (Math.min(a.y, b.y, c.y) + Math.max(a.y, b.y, c.y)) / 2;

    var ax = a.x - ox;

    var ay = a.y - oy;

    var bx = b.x - ox;

    var by = b.y - oy;

    var cx = c.x - ox;

    var cy = c.y - oy;

    var d = (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)) * 2;

    if (d == 0)

        return null;

    var x = ox + ((ax * ax + ay * ay) * (by - cy) + (bx * bx + by * by) * (cy - ay) + (cx * cx + cy * cy) * (ay - by)) / d;

    var y = oy + ((ax * ax + ay * ay) * (cx - bx) + (bx * bx + by * by) * (ax - cx) + (cx * cx + cy * cy) * (bx - ax)) / d;

    var ra = distance(x, y, a.x, a.y);

    var rb = distance(x, y, b.x, b.y);

    var rc = distance(x, y, c.x, c.y);

    return new Circle(x, y, Math.max(ra, rb, rc));

}

/* Simple mathematical functions */

var MULTIPLICATIVE_EPSILON = 1 + 1e-14;

function isInCircle(c, p) {

    return c !== null && distance(p.x, p.y, c.x, c.y) <= c.r * MULTIPLICATIVE_EPSILON;

}

// Returns twice the signed area of the triangle defined by (x0, y0), (x1, y1), (x2, y2).

function crossProduct(x0, y0, x1, y1, x2, y2) {

    return (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0);

}

function distance(x0, y0, x1, y1) {

    return Math.hypot(x0 - x1, y0 - y1);

}

if (!("hypot" in Math)) // Polyfill

    Math.hypot = function (x, y) { return Math.sqrt(x * x + y * y); };

​

​

var Vertex = function(x, y) {

  this.x = x

  this.y = y

  this.equals = function(vertex){ return this.x === vertex.x && this.y == vertex.y }

}

​

var Edge = function(v0, v1) {

  this.v0 = v0

  this.v1 = v1

  this.equals = function(edge){

    return (this.v0.equals(edge.v0) && this.v1.equals(edge.v1)) ||

      (this.v0.equals(edge.v1) && this.v1.equals(edge.v0));

  }

}

​

// Triangle

var Triangle = function(v0, v1, v2) {

  this.v0 = v0

  this.v1 = v1

  this.v2 = v2

  this.circumCirc = calcCircumCirc(v0,v1,v2)

  this.inCircumcircle = function(v) {

    var dx = this.circumCirc.c.x - v.x;

    var dy = this.circumCirc.c.y - v.y;

    return Math.sqrt(dx * dx + dy * dy) <= this.circumCirc.r;

  }

};

​

// Remove duplicate edges

var uniqueEdges = function(edges) {

  var uniqueEdges = [];

  for (var i = 0; i < edges.length; ++i) {

    var isUnique = true;

​

    // See if edge is unique

    for (var j = 0; j < edges.length; ++j) {

      if (i != j && edges[i].equals(edges[j])) {

        isUnique = false;

        break;

      }

    }

​

    // Edge is unique, add to unique edges array

    isUnique && uniqueEdges.push(edges[i]);

  }

​

  return uniqueEdges;

};

​

// Update array of triangles by adding a new vertex

var addVertex = function(vertex, triangles) {

  var edges = [];

​

  // Remove triangles with circumcircles containing the vertex

  triangles = triangles.filter(function(triangle) {

    if (triangle.inCircumcircle(vertex)) {

      edges.push(new Edge(triangle.v0, triangle.v1));

      edges.push(new Edge(triangle.v1, triangle.v2));

      edges.push(new Edge(triangle.v2, triangle.v0));

      return false;

    }

    return true;

  });

​

​

  // Get unique edges

  edges = uniqueEdges(edges);

​

  // Create new triangles from the unique edges and new vertex

  edges.forEach(function(edge) {

    triangles.push(new Triangle(edge.v0, edge.v1, vertex));

  });

​

​

  return triangles;

};

​

​

function triangulate(vertices, stopi) {

  // Create bounding 'super' triangle

  var st = getBounding2(e) //superTriangle(vertices);

​

  // Initialize triangles while adding bounding triangle

  var triangles = [st];

​

  for(let n = 0; n < stopi; n++){

    triangles = addVertex(vertices[n], triangles);

  }

​

  //Remove triangles that share edges with super triangle

  triangles = triangles.filter(function(triangle) {

    return !(triangle.v0 == st.v0 || triangle.v0 == st.v1 || triangle.v0 == st.v2 ||

      triangle.v1 == st.v0 || triangle.v1 == st.v1 || triangle.v1 == st.v2 ||

      triangle.v2 == st.v0 || triangle.v2 == st.v1 || triangle.v2 == st.v2);

  });

​

  return triangles;

};

​

function setup() {

  frameRate(60)

  //randomSeed(1000)

  w = min(windowWidth, windowHeight)

  wx = w

  wy = w

  createCanvas(wx, wy)

​

  pad = w/12

​

  background(0)

  stroke(255)

  noFill()

  strokeWeight(5)

  strokeJoin(ROUND)

​

  //randomSeed(1000)

  pointList = []

  pointList2 = []

  for (let n = 0; n < 300; n++) {

​

    r = w*2 * sqrt(random())

    theta = random() * 2 * PI

​

    randX = random(pad, w-pad) //w/2 + r*cos(theta)

    randY = random(pad, w-pad) //w/2 + r*sin(theta)

​

    pointList.push(

      new Vertex(randX, randY)

    )

    pointList2.push(

      new Point(randX, randY)

    )

​

  }

​

  strokeWeight(1)

  e = makeCircle(pointList)

}

​

function draw(){

  background(0)

  strokeWeight(5)

  for(let j = 0; j < pointList.length; j++){

    point(pointList[j].x, pointList[j].y)

  }

​

  triangles = triangulate(pointList, frameCount)

​

  strokeWeight(1)

  stroke(255)

  triangles.forEach(

    (tri, i) => {

​

      beginShape()

      vertex(tri.v0.x, tri.v0.y)

      vertex(tri.v1.x, tri.v1.y)

      vertex(tri.v2.x, tri.v2.y)

​

      endShape(CLOSE)

    }

  )

​

  for(let j = 0; j < pointList.length; j++){

    point(pointList[j].x, pointList[j].y)

​

  }

​

  if(frameCount > 299){

    noLoop()

  }

​

}

​