<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1000 1000" version="1.1" overflow="hidden">
  <!-- 
    Johan Karlsson, 2020
    https://twitter.com/DonKarlssonSan 
  -->
</svg>

html, body {
  height: 100%;
  margin: 0;
}

svg {
  position: absolute;
  width: 100%;
  height: 100%;
}

/*
  Johan Karlsson, 2020
  https://twitter.com/DonKarlssonSan
  MIT License, see Details View
  
  https://en.wikipedia.org/wiki/Voronoi_diagram
  https://en.wikipedia.org/wiki/Delaunay_triangulation
  https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm
  https://en.wikipedia.org/wiki/Circumscribed_circle
*/

const svgNs = "http://www.w3.org/2000/svg";
let svg;
let w;
let h;

class Triangle {
  constructor(a, b, c) {
    this.a = a;
    this.b = b;
    this.c = c;
  }
  
  vertexes() {
    return [this.a, this.b, this.c];
  }
  
  vertexesAsString() {
    return this.vertexes().map(vertex => `${vertex.x}, ${vertex.y}`).join(", ");
  }
  
  draw(groupElement) {
    let polygon = document.createElementNS(svgNs, "polygon");
    polygon.setAttribute("points", this.vertexesAsString());
    polygon.setAttribute("fill", "none");
    polygon.setAttribute("stroke-linecap", "round");
    polygon.setAttribute("stroke-linejoin", "round");
    groupElement.appendChild(polygon);    
  }
  
  getPoints(p1, p2, nrOfPoints) {
    let points = [];
    let delta = p1.sub(p2).div(nrOfPoints+1);
    for(let i = 1; i < nrOfPoints+1; i++) {
      let currentPos = p2.add(delta.mult(i));
      points.push(currentPos);
    }
    return points;
  }

  edges() {
    return [
      [this.a, this.b],
      [this.b, this.c],
      [this.c, this.a]
    ];
  }
  
  sharesAVertexWith(triangle) {
    // TODO: optimize me please!
    for(let i = 0; i < 3; i++) {
      for(let j = 0; j < 3; j++) {
        let v = this.vertexes()[i];
        let vv = triangle.vertexes()[j];
        if(v.equals(vv)) {
          return true;
        }
      }
    }
    return false;
  }
  
  sharesAnEdgeWith(triangle) {
    let edges = triangle.edges();
    for(let i = 0; i < edges.length; i++) {
      let edge = edges[i];
      if(this.hasEdge(edge)) {
        return true;
      }
    } 
    return false;
  }

  hasEdge(edge) {
    for(let i = 0; i < 3; i++) {
      let e = this.edges()[i];
      if(e[0].equals(edge[0]) && e[1].equals(edge[1]) || 
         e[1].equals(edge[0]) && e[0].equals(edge[1])) {
        return true;
      }
    }
    return false;
  }
  
  get centroid() {
    if(!this._centroid) {
      this._centroid = this.a.add(this.b).add(this.c).div(3);
    }
    return this._centroid;
  }
  
  get circumcenter() {
    if(this._circumcenter) {
      return this._circumcenter;
    }
    let d = 2 * (this.a.x * (this.b.y - this.c.y) + 
                 this.b.x * (this.c.y - this.a.y) + 
                 this.c.x * (this.a.y - this.b.y));
    
    let x = 1 / d * ((this.a.x * this.a.x + this.a.y * this.a.y) * (this.b.y - this.c.y) + 
                     (this.b.x * this.b.x + this.b.y * this.b.y) * (this.c.y - this.a.y) + 
                     (this.c.x * this.c.x + this.c.y * this.c.y) * (this.a.y - this.b.y));
    
    let y = 1 / d * ((this.a.x * this.a.x + this.a.y * this.a.y) * (this.c.x - this.b.x) + 
                     (this.b.x * this.b.x + this.b.y * this.b.y) * (this.a.x - this.c.x) + 
                     (this.c.x * this.c.x + this.c.y * this.c.y) * (this.b.x - this.a.x));
    this._circumcenter = new Vector(x, y);
    return this._circumcenter;
  }
  
  circumradius() {
    return this.circumcenter.sub(this.a).getLength();    
  }
  
  pointIsInsideCircumcircle(point) {
    let circumcenter = this.circumcenter;
    let circumradius = circumcenter.sub(this.a).getLength();
    let dist = point.sub(circumcenter).getLength();
    return dist < circumradius;
  }
}

function getRandomPoints() {
  let pointList = [];
  let div = Math.random() * 3000 + 1000;
  let nrOfPoints = w * h / div;
  for(let i = 0; i < nrOfPoints; i++) {
    pointList.push(new Vector(
      Math.random() * w,
      Math.random() * h
    ));
  }
  return pointList;
}

function bowyerWatson (superTriangle, pointList) {
  // pointList is a set of coordinates defining the 
  // points to be triangulated
  let triangulation = [];

  // add super-triangle to triangulation 
  // must be large enough to completely contain all 
  // the points in pointList
  triangulation.push(superTriangle);
  
  // add all the points one at a time to the triangulation
  pointList.forEach(point => {
    let badTriangles = [];
    
    // first find all the triangles that are no 
    // longer valid due to the insertion
    triangulation.forEach(triangle => { 
      if(triangle.pointIsInsideCircumcircle(point)) {
        badTriangles.push(triangle); 
      }
    });
    let polygon = [];
    
    // find the boundary of the polygonal hole
    badTriangles.forEach(triangle => {
      triangle.edges().forEach(edge => {
        let edgeIsShared = false;
        badTriangles.forEach(otherTriangle => {
          if(triangle !== otherTriangle &&  otherTriangle.hasEdge(edge)) {
            edgeIsShared = true;
          }
        });
        if(!edgeIsShared) {
          //edge is not shared by any other 
          // triangles in badTriangles
          polygon.push(edge);
        }
      });
    });
    
    // remove them from the data structure
    badTriangles.forEach(triangle => {
      let index = triangulation.indexOf(triangle);
      if (index > -1) {
        triangulation.splice(index, 1);
      }
    });
    
    // re-triangulate the polygonal hole
    polygon.forEach(edge => {
      //form a triangle from edge to point
      let newTri = new Triangle(edge[0], edge[1], point);
      triangulation.push(newTri);
    });
  });
  
  // done inserting points, now clean up
  let i = triangulation.length;
  while(i--) {
    let triangle = triangulation[i];
    if(triangle.sharesAVertexWith(superTriangle)) {
      //remove triangle from triangulation
      let index = triangulation.indexOf(triangle);
      if (index > -1) {
        triangulation.splice(index, 1);
      }
    }  
  }
  
  return triangulation;
}

function getVoronoiLines(triangles) {
  let lines = [];
  for(let i = 0; i < triangles.length; i++) {
    let currentTriangle = triangles[i];
    for(let j = i+1; j < triangles.length; j++) {
      let otherTriangle = triangles[j];
      if(currentTriangle.sharesAnEdgeWith(otherTriangle)) {
        let line = {
          x1: currentTriangle.circumcenter.x,
          y1: currentTriangle.circumcenter.y,
          x2: otherTriangle.circumcenter.x,
          y2: otherTriangle.circumcenter.y
        };
        lines.push(line);
      }
    }
  }
  return lines;
}

function drawLines(groupElement, lines) {
  lines.forEach(line => {
    let lineElement = createLineElement(line);
    groupElement.appendChild(lineElement);
  });
}

function createLineElement(line) {
  let lineElement = document.createElementNS(svgNs, "line");
  lineElement.setAttribute("x1", line.x1);
  lineElement.setAttribute("y1", line.y1);
  lineElement.setAttribute("x2", line.x2);
  lineElement.setAttribute("y2", line.y2);
  return lineElement;
}

function setup() {
  svg = document.querySelector("svg");
  document.addEventListener("click", draw);
  document.addEventListener("keydown", onKeyDown);
  window.addEventListener("resize", onResize);
  onResize();
}

function onResize() {
  w = window.innerWidth;
  h = window.innerHeight;
  svg.setAttribute("viewBox", `0 0 ${w} ${h}`);
  draw();
}

function onKeyDown (e) {
  if(e.code === "KeyD") {
    download();
  }
}

function download() {
  let svgDoc = svg.outerHTML;
  let filename = "voronoi.svg";
  let element = document.createElement("a");
  element.setAttribute("href", "data:image/svg+xml;charset=utf-8," + encodeURIComponent(svgDoc));
  element.setAttribute("download", filename);
  element.style.display = "none";
  document.body.appendChild(element);
  element.addEventListener("click", e => e.stopPropagation());
  element.click();
  document.body.removeChild(element);
}

function draw() {
  let group = document.querySelector("g");
  if(group) {
    group.remove();
  }
  group = document.createElementNS(svgNs, "g");
  group.setAttribute("stroke", "black");
  
  let pointList = getRandomPoints();
  
  let superTriangle = new Triangle(
    new Vector(-w * 10, h * 10),
    new Vector(w * 10, h * 10),
    new Vector(w / 2, -h * 10)
  );
  
  let triangles = bowyerWatson(superTriangle, pointList);
  let lines = getVoronoiLines(triangles);
  drawLines(group, lines);
  svg.appendChild(group);
}

setup();