Introduction

Merging approximately equal points means grouping points that are close enough to be treated as duplicates and then replacing each group with one representative point. This is a common preprocessing step in geometry, sensor cleanup, GIS work, and machine learning pipelines where tiny coordinate differences are noise rather than real distinctions.

Start by Defining "Approximately Equal"

There is no universal threshold for equality in floating-point or spatial data. You need a distance rule and a tolerance.

For two-dimensional Euclidean points, a simple rule is:

• two points belong to the same group if their distance is at most eps

That sounds simple, but the choice of eps changes the result dramatically. If eps is too small, obvious duplicates remain separate. If it is too large, distinct points collapse together.

The first design decision is therefore not the merge code. It is the tolerance policy.

A Simple Merge Strategy Using Connected Components

One reliable way to merge close points is to treat each point as a node in a graph. If two points are within eps, connect them. Each connected component is then a merge group.

1import math
2from collections import defaultdict
3
4points = [
5    (0.0, 0.0),
6    (0.04, 0.03),
7    (1.0, 1.0),
8    (1.06, 0.98),
9    (3.5, 3.5),
10]
11eps = 0.1
12
13parent = list(range(len(points)))
14
15
16def find(x):
17    while parent[x] != x:
18        parent[x] = parent[parent[x]]
19        x = parent[x]
20    return x
21
22
23def union(a, b):
24    ra, rb = find(a), find(b)
25    if ra != rb:
26        parent[rb] = ra
27
28
29def distance(p, q):
30    return math.dist(p, q)
31
32for i in range(len(points)):
33    for j in range(i + 1, len(points)):
34        if distance(points[i], points[j]) <= eps:
35            union(i, j)
36
37clusters = defaultdict(list)
38for i, point in enumerate(points):
39    clusters[find(i)].append(point)
40
41merged = []
42for cluster in clusters.values():
43    x = sum(p[0] for p in cluster) / len(cluster)
44    y = sum(p[1] for p in cluster) / len(cluster)
45    merged.append((round(x, 3), round(y, 3)))
46
47print(merged)

This approach is easy to reason about. It preserves the idea that closeness defines equivalence classes, and it replaces each class with its centroid.

Choose the Representative Point Carefully

The centroid is common, but it is not always the best representative.

Depending on the domain, you may want:

• the arithmetic mean, for smooth numerical data
• the median, for better resistance to outliers
• the first point, if you only want deduplication and not averaging
• the highest-confidence point, if each point has a score

The merge rule and the representative rule are separate decisions. Do not hard-code one just because it is convenient.

Scaling Beyond the Naive O(n^2) Scan

The pairwise comparison approach checks every pair of points, which is O(n^2). That is fine for small datasets and often the right starting point because it is easy to validate.

For larger datasets, use a spatial index or bucketing strategy. A simple grid approach is often enough: place each point into a cell derived from eps, then compare only against points in the same cell and neighboring cells.

That cuts down the number of candidate comparisons drastically when the points are spread out.

If you are already using scientific Python tooling, density-based clustering such as DBSCAN is another good fit because it naturally groups nearby points without requiring you to specify the number of clusters.

Be Explicit About Transitive Merges

Suppose point A is close to B, and B is close to C, but A is slightly farther than eps from C. Should all three merge together?

The connected-component approach says yes, because closeness is treated transitively through the graph.

That may be correct or incorrect for your domain. If you need stricter pairwise similarity inside each final cluster, you need a different algorithm. This is one of the most overlooked design choices in approximate deduplication.

Common Pitfalls

The most common mistake is choosing eps by guesswork and never validating the resulting merges on real data.

Another mistake is using a centroid when the data contains outliers or categorical attributes that do not average meaningfully.

A third issue is assuming the naive algorithm will scale. It is fine for thousands of points, but painful for millions.

Finally, many developers forget to define whether closeness should be transitive. That choice changes cluster membership and therefore changes the merged dataset.

Summary

• Merging approximately equal points requires both a distance metric and a tolerance.
• A connected-component or union-find approach is a clear starting solution.
• The merge representative can be a mean, median, original point, or weighted choice.
• Naive pairwise scans are easy to write but scale poorly.
• For large datasets, use spatial indexing, bucketing, or clustering.
• Define the transitive-merge rule explicitly before you trust the output.