Delaunay

by John Doe

HTML

<p id="instruction">Press "Start Test"</p>
<ul>
<!--
<li><a id="start">x Start Test</a></li>
<li><a id="stop">x Stop Test</a></li>
<li><a id="print">x Show Data</a></li>
-->
<li><a id="download">Download as image</a></li>
<li><a id="">--</a></li>
</ul>
<p id="log">just some logging information</p>
<canvas width="500" height="500" id="canvas">Sorry, no canvas available</canvas>
<br/>
<p id="datadump"></p>

CSS

body {
	background-color:#755;
	padding:0;
	margin:0;
	overflow:scroll;
  font-family:sans-serif;
  color:#fff;
}
canvas {
  border:1px solid #000;
  float:left;
  clear:both;
}
ul {
  padding:0;
  padding-left:20px;
  margin:0;
}
li {
  float:left;
  padding:0;
  padding-right:20px;
  margin:0;
}
a {
  cursor:pointer;
  color:#ccc;
}
a:hover {
  color:#fff;
}

JavaScript

/*
* PROBLEM:
* the check whether a point is within the circumcircle of a given triangle depends on the fact that the points of the triangle are always counterclockwise. but for some reason it now works in any case. could it be that the way I construct the triangles ensures that they are always counterclockwise?
% ANSWER:
* yes, my current code apparently makes all triangles in the same orientation as the META-triangle. 
* to find the orientation of a triangle, we can just use the sign of the cross product 
*/

var cnvs = document.getElementById('canvas'),
    ctx = cnvs.getContext('2d')
    
var points = []

function main(){ //TODO
  points = generatePoints(100)
  /*
  points = [[.1,.1],[.1,.9],[.9,.1],[.9,.9],[.5,.5]].map(
  	x => [ x[0] * cnvs.width |0 ,  x[1] * cnvs.height |0 ]
    ) //*/
  eraseCanvas()
  plotPoints(points)
  var tri = triangulate(points)
  //log(tri.join("],["))
  plotTriangulation(points,tri)
  plotPoints(points)
  findOrientations(tri,points)
  //log("\n" + tri.join("],["))
  //plotTriangulation(points,[[1,2,3],[2,3,4],[4,5,6]])
  //log("triangulated")
  
}

function triangulate(P){ //TODO
	//https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm#Pseudocode
  var T = [] // triangulation
  var badTriangles = []
  var newTri = []
  var temp
  /* create meta triangle, all point should be within this one */

  var xmin = P.reduce(function(acc,curr){ return  curr[0] < acc? curr[0] : acc ;},Infinity)
  var ymin = P.reduce(function(acc,curr){	return  curr[1] < acc? curr[1] : acc ;},Infinity)
  var xmax = P.reduce(function(acc,curr){	return  curr[0] > acc? curr[0] : acc ;},-Infinity)
  var ymax = P.reduce(function(acc,curr){	return  curr[1] > acc? curr[1] : acc ;},-Infinity)

	P.push([xmin - (xmax-xmin) * 0.1, ymin - (ymax - ymin) * 0.1])
  P.push([xmin, ymax + (ymax - ymin) * 1.1])
  P.push([xmax + (xmax-xmin) * 1.1, ymin])

  T.push([P.length-3,P.length-2,P.length-1])
  /* add all the points */
  //alert(P.length)
  for(var k = 0; k <...