Compute Centroid

easyFREELeast Squares AlignmentAlignmentCV: Image Alignment and Stitching

You are given a set of 2D points and need to compute their centroid (center of mass).

The centroid is the average position of all points: $\bar{x} = \frac{1}{n}\sum_{i=1}^{n} x_i, \quad \bar{y} = \frac{1}{n}\sum_{i=1}^{n} y_i$

Centroids are fundamental in alignment algorithms because:

They're used to normalize point sets before computing transformations
They help separate translation from rotation/scaling
They minimize the sum of squared distances to all points

In Procrustes analysis and ICP (Iterative Closest Point), centering point sets at the origin simplifies the computation of optimal rotation.

Example

Input

points = [(0, 0), (2, 0), (2, 2), (0, 2)]

Output

(1.0, 1.0)

Reasoning

Input: points holds $n = 4$ pairs $(x_i, y_i)$ : the corners $(0,0)$ , $(2,0)$ , $(2,2)$ , $(0,2)$ of a square with side length 2.
x coordinate: the four $x$ values are $0, 2, 2, 0$ . Their total is 4, so $\bar{x} = \frac{4}{4} = 1$ .
y coordinate: the four $y$ values are $0, 0, 2, 2$ , which also total 4, so $\bar{y} = \frac{4}{4} = 1$ .
Output: the pair $(\bar{x}, \bar{y})$ as a tuple of floats, each rounded to 4 decimal places, giving (1.0, 1.0). The division makes both values floats even though every input is an integer.
Notice: the centroid is not one of the input points. It sits at the centre of the square, at distance $\sqrt{1^2 + 1^2} = \sqrt{2}$ from every corner, so the squared distances total $4 \times 2 = 8$ , the smallest total any point in the plane can achieve. With a single point, the centroid is that point itself.

Constraints

points is a list of (x, y) tuples
Return centroid as (x, y) tuple
Round each coordinate to 4 decimal places

More from CV: Image Alignment and Stitching

Jacobian for Bundle Adjustmenthard Cylindrical Projection for Panoramashard Essential Matrix Estimationhard Procrustes Analysismedium Gradient Descent Updatemedium

Concept primer

The centroid of a set of 2D points is just the average of all their coordinates, and it is used in alignment problems to “recentre” point sets so that translation is factored out before estimating rotation and scaling.

1. Background Knowledge

Centroid definition For 2D points $p_i = (x_i, y_i)$ , $i = 1,\dots,n$ , the centroid is

\bar{x} = \frac{1}{n}\sum_{i=1}^n x_i,\qquad \bar{y} = \frac{1}{n}\sum_{i=1}^n y_i.

Geometrically, this is the “center of mass” if each point has equal mass.

Why centering matters in alignment Many alignment methods (e.g., Procrustes analysis, ICP) first translate each point set so its centroid is at the origin. After this centering, any remaining difference between point sets is explained by rotation and scaling, making their estimation simpler (often via SVD or eigen-decomposition).
Least squares connection The centroid minimizes the sum of squared Euclidean distances from all points to a single point:

\min_{c} \sum_{i=1}^n \|p_i - c\|^2.

The minimizer $c$ is exactly $($ \bar{x} $,$ \bar{y} $)$ . This least-squares optimality is why centroids naturally appear in algorithms that minimize squared errors.

2. Algorithm / General Approach

The general pattern to compute a centroid:

Accumulate sums of all x-coordinates and y-coordinates.
Count the number of points $n$ .
Divide sums by $n$ to get the average in each dimension.

This extends directly to higher dimensions: average each coordinate independently.

3. Step-by-Step Strategy

Assume input is a list/array of points, where each point is (x, y):

Initialize accumulators

sum_x = 0.0
sum_y = 0.0
n = len(points)

Edge case: if n == 0, decide how your problem specification says to handle it (often not allowed, or return a default/raise an error).
Loop through points and accumulate

for (x, y) in points:
sum_x += x
sum_y += y

Compute averages

cx = sum_x / n
cy = sum_y / n
centroid = (cx, cy)

Return or use the centroid (e.g., to subtract it from all points for centering):

centered_points = [(x - cx, y - cy) for (x, y) in points]

4. Common Pitfalls

Empty input Division by zero if there are no points. Handle n == 0 explicitly.
Integer division (in some languages)
In languages like Python 2, C, C++, Java (with int), sum_x / n might do integer division.
Ensure you use floating-point: cast either the sum or n to float (double) before division.
Overflow / precision
For very large coordinates or huge numbers of points, sums can overflow or lose precision.
For an easy-level problem this is usually not relevant, but in high-precision applications you might consider more stable summation (e.g., Kahan summation).
Coordinate order Make sure you are consistent with (x, y) ordering and do not mix them.

5. Time & Space Complexity

Time complexity:
Single pass over all points: $O(n)$ .
Space complexity:
Only a few scalar accumulators plus the centroid: $O(1)$ extra space (ignoring the input storage).

solution.py

Python 3.13

Test results