Two small optimizations for getCentroidCell()
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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