4

我有一个这样的点列表

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)]

当用红色绘制时，它们就是这样：

在此处输入图像描述

我现在想融合彼此靠近的点（黑色圆圈）。通过保险丝，我的意思是用一个具有其坐标平均值的点替换这些点。

我确实知道那里有一大堆集群技术可以完成类似的工作。但是，如您所见，这是一项简单的任务，如果我能够调整距离阈值。所以我不愿意使用任何聚类技术。只需一个简单的解决方案就足够了。

如果有帮助，我正在使用 Python。

近，我的意思是它们之间的欧式距离小于阈值，可以自己调整。所以右上角的两个点不会被圈起来。

4

4 回答 4

7

你可以有一个函数，给定距离 d 将融合在给定点距离 d 内的点（通过取它们的平均值）：

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
于 2013-10-15T07:53:04.813 回答
3

您可以只给出一个半径限制并迭代地连接比该半径更近的点。如果您的数据集足够小，蛮力可能就足够了：

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
于 2013-10-15T07:56:18.723 回答
0

好的，这是我的严重未优化的稍微复杂一点的算法，它首先创建一个布尔邻近矩阵，从最终用于获得平均坐标的集群列表中创建：

# -*- 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()

聚类...

（为了更好的可视化，圆的半径是阈值的一半，即如果它们的圆仅仅相交/接触彼此的边缘，则点在同一个簇中。）

于 2013-10-16T07:41:37.833 回答
0 
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, :]
于 2018-04-05T18:41:27.610 回答