Two small optimizations for getCentroidCell()

There are two opportunities for improving the performance of the centroid calculation, saving one multiply and one addition per polygon vertex.

First, when summing the vertex coordinates, we scale the sum of coordinates of the prior and the current vertex. But since we're just looping over all vertices, that just means that we'll be adding in a coordinate twice (once as the prior, and once as the current). Thus, we can just add each coordinate once, and scale by two outside the loop, saving an addition for every vertex.

Second, when accumulating the area, we scale f by three before adding. Instead of multiplying N times inside the loop, we can just scale the sum of fs by three after the loop is done, saving a multiply for every vertex.

Here's my proposed iteration:

function getCentroidCell(polygon) {
    var doubleArea = 0;
    var xSum = 0;
    var ySum = 0;
    var points = polygon[0];

    for (var i = 0, len = points.length, j = len - 1;  i < len;  j = i++) {
        var a = points[j]; // Swapped indices. Might as well traverse in native order.
        var b = points[i];
        var f = a[0] * b[1] - a[1] * b[0];

        xSum += f * a[0];
        ySum += f * a[1];
        doubleArea += f;
    }

    if (doubleArea === 0) return new Cell(points[0][0], points[0][1], 0, polygon);

    var sumScale = 2 / (3 * doubleArea);
    return new Cell(xSum * sumScale, ySum * sumScale, 0, polygon);
}

mapbox / polylabel

Two small optimizations for getCentroidCell() #71