mapbox / mapbox/polylabel

Two small optimizations for getCentroidCell()

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

Nobody has claimed this yet.

question
Dominant language
JavaScript
Stars
1.6k
Forks
163
PR merge metrics
No merged PRs in 30d

Description

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);
}

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.

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.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.