Two small optimizations for getCentroidCell()

Open
#71 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
48/100
Issue type
Refactor
Clarity
Clearly specified
Activity status
Stale
Tech stack
javascript
Domain
performance

Research direction

Start at the getCentroidCell(polygon) implementation and compare its current centroid and area accumulation with the proposed loop. Verify that the optimized calculation preserves results for regular and degenerate polygons, and confirm the existing project checks pass; done means equivalent centroid behavior with the intended per-vertex arithmetic reductions.

Written by the indexing model from the issue text.

Description

question

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);
}
Dominant language
JavaScript
Stars
1.6k
Forks
163
No merged PRs in 30d

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from mapbox/polylabel

All issues in mapbox/polylabel

Similar issues

More JavaScript issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.