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

赤でプロットすると、次のようになります。

ここに画像の説明を入力

私は今、お互いに近いポイントを融合したいと考えています（黒い丸で囲みます）。融合とは、これらのポイントを、それらの座標の平均を持つ 1 つのポイントに置き換えることを意味します。

同様の作業を行うためのクラスタリング手法がたくさんあることは理解しています。ただし、ご覧のとおり、距離のしきい値を調整できれば、これは簡単な作業です。そのため、クラスタリング手法を使用することに消極的です。単純な解決策だけで十分です。

それが役立つ場合、私はPythonを使用しています。

近いとは、それらの間のユークリッド距離が、自分で調整できるしきい値よりも小さいことを意味します。したがって、右上の 2 つの点は丸で囲まれません。

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 に答える