Нахождение кластеров массы в матрице/битовом массиве

Вам нужен кластеризирующийся алгоритм, это легко, так как у Вас просто есть 2 размерных сетки, и записи ограничивают друг друга. Можно просто использовать floodfill алгоритм. После того как у Вас есть каждый кластер, можно найти центр как в 2D центре массовой статьи..

Моя первая мысль состояла бы в том, чтобы сначала найти любую ячейку с ненулевым значением. Оттуда сделайте некоторый алгоритм заливки и вычислите центр массы найденных ячеек. Затем обнулите найденные ячейки от матрицы и начните с вершины.

Это, конечно, не масштабировалось бы, а также метод от Google, который связанный tuinstoel, но будет легче реализовать для меньших матриц.

Править:

Непересекающиеся наборы (использующий сжатие пути и объединение разрядом) могли быть полезными здесь. У них есть O (α (n)) временная сложность для объединения и установленный на находку, где

α (n) = минута {k: _Ak (1) ≥ n}.

_Ak (n) является функцией Ackerman, таким образом, α (n) по существу будет O (1) для любой рыночной стоимости. Единственная проблема состоит в том, что непересекающиеся наборы являются односторонним отображением объекта для установки, но это не будет иметь значения, идете ли Вы канавка все объекты.

Вот простой сценарий Python для демонстрации:

from collections import defaultdict

class DisjointSets(object):
    def __init__(self):
        self.item_map = defaultdict(DisjointNode)

    def add(self,item):
        """Add item to the forest."""
        # It's gets initialized to a new node when
        # trying to access a non-existant item.
        return self.item_map[item]

    def __contains__(self,item):
        return (item in self.item_map)

    def __getitem__(self,item):
        if item not in self:
            raise KeyError
        return self.item_map[item]

    def __delitem__(self,item):
        del self.item_map[item]

    def __iter__(self):
        # sort all items into real sets
        all_sets = defaultdict(set)
        for item,node in self.item_map.iteritems():
            all_sets[node.find_set()].add(item)
        return all_sets.itervalues()

class DisjointNode(object):
    def __init__(self,parent=None,rank=0):
        if parent is None:
            self.parent = self
        else:
            self.parent = parent
        self.rank = rank

    def union(self,other):
        """Join two sets."""
        node1 = self.find_set()
        node2 = other.find_set()
        # union by rank
        if node1.rank > node2.rank:
            node2.parent = node1
        else:
            node1.parent = node2
            if node1.rank == node2.rank:
                node2.rank += 1
        return node1

    def find_set(self):
        """Finds the root node of this set."""
        node = self
        while node is not node.parent:
            node = node.parent
        # path compression
        root, node = node, self
        while node is not node.parent:
            node, node.parent = node.parent, root
        return root

def find_clusters(grid):
    disj = DisjointSets()
    for y,row in enumerate(grid):
        for x,cell in enumerate(row):
            if cell:
                node = disj.add((x,y))
                for dx,dy in ((-1,0),(-1,-1),(0,-1),(1,-1)):
                    if (x+dx,y+dy) in disj:
                        node.union(disj[x+dx,y+dy])
    for index,set_ in enumerate(disj):
        sum_x, sum_y, count = 0, 0, 0
        for x,y in set_:
            sum_x += x
            sum_y += y
            count += 1
        yield 1.0 * sum_x / count, 1.0 * sum_y / count

def main():
    grid = [[('.' != cell) for cell in row if not cell.isspace()] for row in (
        ". X X . . . . . .",
        ". X X X . . X . .",
        ". . . . . X X X .",
        ". . . . . . X . .",
        ". X X . . . . . .",
        ". X . . . . . . .",
        ". X . . . . . . .",
        ". . . . X X . . .",
        ". . . . X X . . .",
    )]
    coordinates = list(find_clusters(grid))
    centers = dict(((round(x),round(y)),i) for i,(x,y) in enumerate(coordinates))
    for y,row in enumerate(grid):
        for x,cell in enumerate(row):
            if (x,y) in centers:
                print centers[x,y]+1,
            elif cell:
                print 'X',
            else:
                print '.',
        print
    print
    print '%4s | %7s %7s' % ('i','x','y')
    print '-'*22
    for i,(x,y) in enumerate(coordinates):
        print '%4d | %7.4f %7.4f' % (i+1,x,y)

if __name__ == '__main__':
    main()

Вывод:

. X X . . . . . .
. X 3 X . . X . .
. . . . . X 4 X .
. . . . . . X . .
. X X . . . . . .
. 2 . . . . . . .
. X . . . . . . .
. . . . X X . . .
. . . . X 1 . . .

   i |       x       y
----------------------
   1 |  4.5000  7.5000
   2 |  1.2500  4.7500
   3 |  1.8000  0.6000
   4 |  6.0000  2.0000

Точка этого должна была продемонстрировать непересекающиеся наборы. Фактический алгоритм в find_clusters() мог быть обновлен до чего-то более устойчивого.

Ссылки

• Введение в алгоритмы. 2-й редактор Cormen et.al.