Thomas Huijzer

Slikveld 22
3311VT Dordrecht

+31 (0)6 - 52 18 06 31
thomas@thuijzer.nl
PGP key
Of contact me via Signal

IBAN: NL93INGB0006752359
KvK: 57865841
btw: NL181253240B02

user@thuijzer.nl:/home/blog/delaunay_triangulatie/

Delaunay-triangulatie

Afgelopen week bekeek ik een aantal methoden om een verzameling punten met elkaar te verbinden door middel van driehoeken. Daarbij kwam ik de methode van Boris Delaunay tegen. Deze methode geeft een erg goed resultaat.
In Javascript maakte ik een demo.

Er zijn verschillende methoden om Delaunay-triangulatie toe te passen, maar de voorwaarde is dat buiten de drie punten die een driehoek vormen geen ander punt in de omschrijvende cirkel van de driehoek ligt.
Het algoritme dat ik heb gebruikt ziet er in pseudocode ongeveer zo uit:


Genereer een verzameling (willekeurige) punten;

Voor elk punt in de verzameling {
    Maak een lijst met driehoeken waarbij het punt in de omschrijvende cirkel ligt;
    Verwijder de gevonden driehoeken, maar onthoudt de zijden;
    Verwijder alle dubbele zijden;
    Maak nieuwe driehoeken die de overgebleven zijden met het punt verbinden;
}

Willekeurige punten

Het is natuurlijk mogelijk om punten willekeurig te plaatsen, maar ik wilde een meer uniforme verdeling. Dus plaatste ik de punten in een vast grid en verplaatste de punten vervolgens willekeurig binnen een bepaalde marge:


var distance = 50;

var generateCenters = function(canvas) {
    var xCount = Math.floor(canvas.width / distance);
    var yCount = Math.floor(canvas.height / distance);
    var centers = [];
    for(var x = 0; x < xCount; x ++) {
        for(var y = 0; y < yCount; y ++) {
            var index = x + y * yCount;
            var rX = (Math.random() - 0.5) * distance * 0.8;
            var rY = (Math.random() - 0.5) * distance * 0.8;
            centers[index * 3 + 0] = distance * 0.5 + x * distance + rX;
            centers[index * 3 + 1] = distance * 0.5 + y * distance + rY;
            centers[index * 3 + 2] = 0;
        }
    }
    return centers;
}
willekeurige punten

Triangulatie starten

Om het algoritme te starten moet er een driehoek in de lijst driehoeken aanwezig zijn waarbij het eerste punt in de omschrijvende cirkel valt. Hiervoor maken we als eerst een super-driehoek die alle punten uit de verzameling omvat. Op die manier zal het algoritme altijd werken.
Wanneer alle punten verbonden zijn verwijderen we de restanten van deze super-driehoek weer.


var triangles = [];
var superTriangle = [
    x1 - distance,
    y1 - distance,
    x1 + (x2 - x1) * 2 + distance * 2,
    y1 - distance,
    x1 - distance,
    y1 + (y2 - y1) * 2 + distance * 2
];
triangles.push(createTriangle(
    superTriangle[0],
    superTriangle[1],
    superTriangle[2],
    superTriangle[3],
    superTriangle[4],
    superTriangle[5]
));
super-driehoek

Resultaat

Wanneer je de gevonden driehoeken vult met een tint krijg je best leuke resultaten:

resultaat 1

Met meer punten:

resultaat 2

Nog meer punten:

resultaat 3

Of met willekeurige kleuren:

resultaat 4

Code

De volledige code:


"use strict";

var thuijzer = thuijzer || {};
thuijzer.triangulate = thuijzer.triangulate || {};

(function() {

    var distance = 20;

    var render = function(canvas) {
        var centers = generateCenters(canvas);
        var triangles = delaunayTriangulate(centers, 0, 0, canvas.width, canvas.height);
        renderTriangles(canvas, triangles);
        //renderCenters(canvas, centers);
    }

    var generateCenters = function(canvas) {
        var xCount = Math.floor(canvas.width / distance);
        var yCount = Math.floor(canvas.height / distance);
        var centers = [];
        for(var x = 0; x < xCount; x ++) {
            for(var y = 0; y < yCount; y ++) {
                var index = x + y * yCount;
                var rX = (Math.random() - 0.5) * distance * 0.8;
                var rY = (Math.random() - 0.5) * distance * 0.8;
                centers[index * 3 + 0] = distance * 0.5 + x * distance + rX;
                centers[index * 3 + 1] = distance * 0.5 + y * distance + rY;
                centers[index * 3 + 2] = 0;
            }
        }
        return centers;
    }

    var renderCenters = function(canvas, centers) {
        var context = canvas.getContext('2d');
        context.fillStyle = '#ff0000';
        for(var i = 0; i < centers.length; i += 3) {
            context.beginPath();
            context.arc(centers[i + 0], centers[i + 1], 2, 0, 360);
            context.fill();
        }
    }

    var renderTriangles = function(canvas, triangles) {
        var context = canvas.getContext('2d');
        for(var t = 0; t < triangles.length; t ++) {
            var r = Math.round(Math.random() * 255);
            var g = Math.round(Math.random() * 255);
            var b = Math.round(Math.random() * 255);
            context.fillStyle = 'rgb(' + r + ',' + g + ',' + b + ')';
            context.beginPath();
            context.moveTo(triangles[t][0], triangles[t][1]);
            context.lineTo(triangles[t][2], triangles[t][3]);
            context.lineTo(triangles[t][4], triangles[t][5]);
            context.lineTo(triangles[t][0], triangles[t][1]);
            context.fill();
        }
    }

    var delaunayTriangulate = function(centers, x1, y1, x2, y2) {
        var triangles = [];
        var superTriangle = [
            x1 - distance,
            y1 - distance,
            x1 + (x2 - x1) * 2 + distance * 2,
            y1 - distance,
            x1 - distance,
            y1 + (y2 - y1) * 2 + distance * 2
        ];
        triangles.push(createTriangle(
            superTriangle[0],
            superTriangle[1],
            superTriangle[2],
            superTriangle[3],
            superTriangle[4],
            superTriangle[5]
        ));

        for(var i = 0; i < centers.length; i += 3) {
            var trianglesToRemove = getTrianglesToRemove(triangles, centers[i + 0], centers[i + 1]);
            for(var t = trianglesToRemove.length - 1; t >= 0; t --) {
                triangles.splice(trianglesToRemove[t][9], 1);
            }
            var edges = getEdges(trianglesToRemove);
            for(var e = 0; e < edges.length; e ++) {
                if(edges[e][4] > 1) {
                    continue;
                }
                triangles.push(createTriangle(
                    edges[e][0],
                    edges[e][1],
                    edges[e][2],
                    edges[e][3],
                    centers[i + 0],
                    centers[i + 1]
                ));
            }
        }

        for(var t = triangles.length - 1; t >= 0; t --) {
            if(triangles[t][6] < x1
                || triangles[t][7] < y1
                || triangles[t][6] > x2
                || triangles[t][7] > y2) {
                triangles.splice(t, 1);
            }

        }

        return triangles;
    }

    var getEdges = function(triangles) {
        var edges = [];
        for(var t = 0; t < triangles.length; t ++) {
            for(var te = 0; te < 3; te ++) {
                var found = false;
                var ex1 = triangles[t][te * 2 + 0];
                var ey1 = triangles[t][te * 2 + 1];
                var ex2 = triangles[t][te == 2 ? 0 : te * 2 + 2];
                var ey2 = triangles[t][te == 2 ? 1 : te * 2 + 3];
                for(var e = 0; e < edges.length; e++) {
                    if((edges[e][0] == ex1 && edges[e][1] == ey1 && edges[e][2] == ex2 && edges[e][3] == ey2)
                        || (edges[e][0] == ex2 && edges[e][1] == ey2 && edges[e][2] == ex1 && edges[e][3] == ey1)) {
                        edges[e][4] ++;
                        found = true;
                    }
                }
                if(!found) {
                    edges.push([ex1, ey1, ex2, ey2, 1]);
                }
            }
        }
        return edges;
    }

    var getTrianglesToRemove = function(triangles, x, y) {
        var trianglesToRemove = [];
        for(var t = 0; t < triangles.length; t ++) {
            if(Math.sqrt(Math.pow(triangles[t][6] - x, 2) + Math.pow(triangles[t][7] - y, 2)) <= triangles[t][8]) {
                triangles[t][9] = t;
                trianglesToRemove.push(triangles[t]);
            }
        }
        return trianglesToRemove;
    }

    var createTriangle = function(x1, y1, x2, y2, x3, y3) {
        // 0 = x1
        // 1 = y1
        // 2 = x2
        // 3 = y2
        // 4 = x3
        // 5 = y3
        // 6 = cx
        // 7 = cy
        // 8 = cd
        var triangle = [
            x1,
            y1,
            x2,
            y2,
            x3,
            y3
        ];
        var c = getCircumcircleCenter(
            triangle[0],
            triangle[1],
            triangle[2],
            triangle[3],
            triangle[4],
            triangle[5]
        );
        triangle.push(c[0], c[1]);
        triangle.push(Math.sqrt(Math.pow(triangle[6] - triangle[0], 2) + Math.pow(triangle[7] - triangle[1], 2)));

        return triangle;
    }

    var getCircumcircleCenter = function(x1, y1, x2, y2, x3, y3) {
        var d = 2 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
        var cx = ((x1 * x1 + y1 * y1) * (y2 - y3) + (x2 * x2 + y2 * y2) * (y3 - y1) + (x3 * x3 + y3 * y3) * (y1 - y2)) / d;
        var cy = ((x1 * x1 + y1 * y1) * (x3 - x2) + (x2 * x2 + y2 * y2) * (x1 - x3) + (x3 * x3 + y3 * y3) * (x2 - x1)) / d;
        return [cx, cy];
    }

    var ns = thuijzer.triangulate;
    ns.render = render;

})();

thuijzer.triangulate.render(
    document.getElementById('canvasElement')
);

Reacties


Plaats een reactie