融合几个关键点的简单方法？

Question

我有一个点列表

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,如果有帮助的话.

---

到了近,我的意思是它们之间的欧氏距离小于一个阈值,可以由我自己调整.因此右上两个点不会被圈出来.

Answer 1

你可以有一个函数,给定距离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