Simple way of fusing a few close points?

Question

I have a list of points as such

points = [(-57.213878612138828, 17.916958304169601),
          (76.392039480378514, 0.060882542482108504),
          (0.12417670682730897, 1.0417670682730924),
          (-64.840321976787706, 21.374279296143762),
          (-48.966302937359913, 81.336323778066188),
          (11.122014925372399, 85.001119402984656),
          (8.6383049769438465, 84.874829066623917),
          (-57.349835526315836, 16.683634868421084),
          (83.051530302006697, 97.450469562867383),
          (8.5405200433369473, 83.566955579631625),
          (81.620435769843965, 48.106831247886376),
          (78.713027357450656, 19.547209139192304),
          (82.926153287322933, 81.026080639302577)]

They are as such when plotted in red:

I now want to fuse the points that are near to each other (circles together in black). By fuse, I mean replace those points with one point that has the averages of their coordinates.

I do understand there are whole bunches of clustering techniques there to do the similar jobs. However, as you can see this is a simple task, if I am able to tune the distance threshold. So I am reluctant to use any clustering techniques. Just a simple solution would be enough.

I am using Python, if it helps.

---

By near, I mean the euclidean distance between them is smaller than a threshold, which can be tuned by myself. So the right top two dots will not get circled.

Answer 1

You can have a function, which given a distance d would fuse the points which are within distance d of a given point (by taking their average):

def dist2(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2

def fuse(points, d):
    ret = []
    d2 = d * d
    n = len(points)
    taken = [False] * n
    for i in range(n):
        if not taken[i]:
            count = 1
            point = [points[i][0], points[i][1]]
            taken[i] = True
            for j in range(i+1, n):
                if Dist2(points[i], points[j]) < d2:
                    point[0] += points[j][0]
                    point[1] += points[j][1]
                    count+=1
                    taken[j] = True
            point[0] /= count
            point[1] /= count
            ret.append((point[0], point[1]))
    return ret

Answer 2

You could just give a radius limit and iteratively join points that are closer than that radius away. If your dataset is small enough, brute force may suffice:

def join_pair(points, r):
    for p, q in itertools.combinations(points, 2):
        if dist(p, q) < r:
            points.remove(p)
            points.remove(q)
            points.append(((p[0]+q[0]) / 2, (p[1]+q[1]) / 2))
            return True
    return False

while join_pair(points, R):
    pass

Answer 3

def merge_close_pts(pts, rad=5): # pts is a numpy array of size mx2 where each row is ( xy )
pts = np.float32(pts) # avoid issues with ints

# iteratively make points that are close to each other get closer ( robust to clouds of multiple close pts merge )
pts_to_merge = (np.sqrt(np.power(pts[:, 0].reshape(-1, 1) - pts[:, 0].reshape(1,-1),2) + \
                   np.power(pts[:, 1].reshape(-1, 1) - pts[:, 1].reshape(1, -1), 2))) <= rad

for _ in range(5):
    for pt_ind in range(pts.shape[0]):
        pts[pt_ind,:] = pts[pts_to_merge[pt_ind, :], :].reshape(-1, 2).mean(axis=0)

#now keep only one pts from each group. 
pts_to_merge = ((np.sqrt(np.power(pts[:, 0].reshape(-1, 1) - pts[:, 0].reshape(1, -1), 2) + \
                        np.power(pts[:, 1].reshape(-1, 1) - pts[:, 1].reshape(1, -1), 2))) <= rad) * \
               (np.eye(pts.shape[0])== 0)


for pt_ind in range(pts.shape[0]):
    if (pts[pt_ind,:] == 0).all() == False:
        inds_to_erase = pts_to_merge[pt_ind, :]
        pts[inds_to_erase, :] = 0


return pts[(pts==0).all() == False, :]

Answer 4

Ok, here's my severly unoptimized go at a slightly more complex algorithm, which first creates a boolean proximity matrix, from that a list of clusters which is ultimately used to obtain the averaged coordinates:

# -*- coding: utf-8 -*-
"""
Created on Wed Oct 16 08:42:50 2013

@author: Tobias Kienzler
"""


def squared_distance(p1, p2):
    # TODO optimization: use numpy.ndarrays, simply return (p1-p2)**2
    sd = 0
    for x, y in zip(p1, p2):
        sd += (x-y)**2
    return sd


def get_proximity_matrix(points, threshold):
    n = len(points)
    t2 = threshold**2
    # TODO optimization: use sparse boolean matrix
    prox = [[False]*n for k in xrange(n)]
    for i in xrange(0, n):
        for j in xrange(i+1, n):
            prox[i][j] = (squared_distance(points[i], points[j]) < t2)
            prox[j][i] = prox[i][j]  # symmetric matrix
    return prox


def find_clusters(points, threshold):
    n = len(points)
    prox = get_proximity_matrix(points, threshold)
    point_in_list = [None]*n
    clusters = []
    for i in xrange(0, n):
        for j in xrange(i+1, n):
            if prox[i][j]:
                list1 = point_in_list[i]
                list2 = point_in_list[j]
                if list1 is not None:
                    if list2 is None:
                        list1.append(j)
                        point_in_list[j] = list1
                    elif list2 is not list1:
                        # merge the two lists if not identical
                        list1 += list2
                        point_in_list[j] = list1
                        del clusters[clusters.index(list2)]
                    else:
                        pass  # both points are already in the same cluster
                elif list2 is not None:
                    list2.append(i)
                    point_in_list[i] = list2
                else:
                    list_new = [i, j]
                    for index in [i, j]:
                        point_in_list[index] = list_new
                    clusters.append(list_new)
        if point_in_list[i] is None:
            list_new = [i]  # point is isolated so far
            point_in_list[i] = list_new
            clusters.append(list_new)
    return clusters


def average_clusters(points, threshold=1.0, clusters=None):
    if clusters is None:
        clusters = find_clusters(points, threshold)
    newpoints = []
    for cluster in clusters:
        n = len(cluster)
        point = [0]*len(points[0])  # TODO numpy
        for index in cluster:
            part = points[index]  # in numpy: just point += part / n
            for j in xrange(0, len(part)):
                point[j] += part[j] / n  # TODO optimization: point/n later
        newpoints.append(point)
    return newpoints


points = [(-57.213878612138828, 17.916958304169601),
          (76.392039480378514, 0.060882542482108504),
          (0.12417670682730897, 1.0417670682730924),
          (-64.840321976787706, 21.374279296143762),
          (-48.966302937359913, 81.336323778066188),
          (11.122014925372399, 85.001119402984656),
          (8.6383049769438465, 84.874829066623917),
          (-57.349835526315836, 16.683634868421084),
          (83.051530302006697, 97.450469562867383),
          (8.5405200433369473, 83.566955579631625),
          (81.620435769843965, 48.106831247886376),
          (78.713027357450656, 19.547209139192304),
          (82.926153287322933, 81.026080639302577)]

threshold = 20.0
clusters = find_clusters(points, threshold)
clustered = average_clusters(points, clusters=clusters)
print "clusters:", clusters
print clustered

import matplotlib.pyplot as plt
ax = plt.figure().add_subplot(1, 1, 1)
for cluster in clustered:
    ax.add_patch(plt.Circle(cluster, radius=threshold/2, color='g'))
for point in points:
    ax.add_patch(plt.Circle(point, radius=threshold/2, edgecolor='k', facecolor='none'))
plt.plot(*zip(*points), marker='o', color='r', ls='')
plt.plot(*zip(*clustered), marker='.', color='g', ls='')
plt.axis('equal')
plt.show()

(For better visualization, the circles' radii are half the threshold, i.e. points are in the same cluster if their circles merely intersect/touch one another's edge.)