Creating a rectangle filled with triangles

Question

I'm doing this in JavaScript ( SVG or Canvas ) but I'm really just looking for pseudocode for how somebody could accomplish this:

If given a rectangle, how can you fill it with various sized, non-overlapping triangles similar to this picture: https://i.stack.imgur.com/skvvw.jpg

UPDATE

Here is what I came up with for those that are interested. I used D3.js which has a great delaunay function to do this.

var width = 360;
var height = 220;

var vertices = d3.range(100).map(function (d) {
    return [Math.random() * width, Math.random() * height];
});

// place coordinates in the corners
[
    [0, 0],
    [width, 0],
    [0, height],
    [width, height]
].forEach(function (d) {
    vertices.push(d);
});

// add the temporary coordinates that will follow mousemove
vertices.unshift([0, 0]);

var svg = d3.select("#main").append("svg")
    .style("width", width + "px")
    .style("height", height + "px")
    .on("mousemove", function () {
    vertices[0] = d3.mouse(this);
    draw();
})
    .on("click", function () {
    vertices.push(d3.mouse(this));
});

var path = svg.append("g").selectAll("path");

draw();

function draw() {
    path = path.data(d3.geom.delaunay(vertices).map(function (d) {
        return "M" + d.join("L") + "Z";
    }), String);
    path.exit().remove();
    path.enter().append("path").attr("class", function (d, i) {
        return "q" + (i % 9) + "-9";
    }).attr("d", String);
}

#main {
    position: relative;
    width: 360px;
    height: 220px;
    border: 1px solid #ddd;
}
path {
    fill: #fff;
    stroke: steelblue;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js"></script>
<div id="main"></div>

Answer 1

I would do the following:

• Define a 2D array for your points, 1D for each line where each entry contains a point for a vertice/corner.
• Create points based on a grid
• Offset the same points using some form of "jitter". The jitter will only offset the point's position but you will still have the same order in the array
• Have a method looping over the arrays drawing a quadrant for each two points on two lines
• Split that quadrant into two triangles using the two opposite corner vertices.

Varying jitter should create a similar pattern as shown in the image. To control the jitter you could randomize an angle and radius rather than just the position. Then convert the result of that to a new position.

An ASCII representation (perhaps not useful..):

line 0: xy xy xy xy xy ....  vertices for upper part of quadrant
line 1: xy xy xy xy xy ....  vertices for lower part and shared
                             upper part of next quadrant
line 2: xy xy xy xy xy ....
line 3: xy xy xy xy xy ....
...

Apply jitter

Draw in ordered fashion whatever the point position is:

line 0: xy_xy_xy xy xy ....
        | /| /| ...
        |/_|/_|
line 1: xy xy xy xy xy ....
...

You could also look into Voronoi diagram but be aware of that you'll end up with quadratic polygons and n-gons, the latter can be a bit of a challenge but check Delaunay triangulation for that.

Answer 2

Someone has already written a library to do exactly this. http://qrohlf.com/trianglify/