Finding Cluster von Masse in einer Matrix / Bitmap
https://stackoverflow.com/questions/411837
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Dies ist in Fortsetzung mit der Frage hier gepostet: Suche nach der Mitte der Masse auf einem 2D-Bitmap die sprach über die Mitte der Masse in einer booleschen Matrix zu finden, wie das Beispiel gegeben wurde.
Nehmen wir nun an wir die Matrix auf diese Form erweitern:
0 1 2 3 4 5 6 7 8 9
1 . X X . . . . . .
2 . X X X . . X . .
3 . . . . . X X X .
4 . . . . . . X . .
5 . X X . . . . . .
6 . X . . . . . . .
7 . X . . . . . . .
8 . . . . X X . . .
9 . . . . X X . . .
Wie Sie sehen, haben wir jetzt vier Zentren der Masse, für 4 verschiedene Cluster.
Wir wissen bereits, wie ein Zentrum der Masse zu finden gegeben, dass nur ein solches vorhanden ist, wenn wir diesen Algorithmus auf dieser Matrix führen wir einen Punkt in der Mitte der Matrix erhalten, die uns nicht helfen.
Was kann ein guter, korrekter und schneller Algorithmus sein, diese Cluster von Masse zu finden?
Lösung
Ich glaube, ich würde jeden Punkt in der Matrix überprüfen und herauszufinden, es Masse basiert auf seine Nachbarn. Die Masse für die Punkte mit fallen würde sagen, das Quadrat der Entfernung. Sie könnten dann die ersten vier Punkte mit einem minimalen Abstand voneinander wählen.
Hier ist ein Python Code, den ich zusammen gepeitscht zu versuchen, den Ansatz zu veranschaulichen, um für jeden Punkt der Masse herauszufinden. Einige Setup mit Ihrem Beispiel Matrix:
matrix = [[1.0 if x == "X" else 0.0 for x in y] for y in """.XX......
.XXX..X..
.....XXX.
......X..
.XX......
.X.......
.X.......
....XX...
....XX...""".split("\n")]
HEIGHT = len(matrix)
WIDTH = len(matrix[0])
Y_RADIUS = HEIGHT / 2
X_RADIUS = WIDTH / 2
Um die Masse zu einem bestimmten Punkt zu berechnen:
def distance(x1, y1, x2, y2):
'Manhattan distance http://en.wikipedia.org/wiki/Manhattan_distance'
return abs(y1 - y2) + abs(x1 - x2)
def mass(m, x, y):
_mass = m[y][x]
for _y in range(max(0, y - Y_RADIUS), min(HEIGHT, y + Y_RADIUS)):
for _x in range(max(0, x - X_RADIUS), min(WIDTH, x + X_RADIUS)):
d = max(1, distance(x, y, _x, _y))
_mass += m[_y][_x] / (d * d)
return _mass
Hinweis: Ich verwende Manhattan Entfernungen (aka Cityblock, aka Taxicab Geometrie) hier weil ich denke, dass die zusätzliche Genauigkeit mit euklidischen Entfernungen nicht wert ist, die Kosten des Aufrufs sqrt ().
Iterieren durch unsere Matrix und den Aufbau einer Liste von Tupeln wie (x, y, Masse (x, y)):
point_mass = []
for y in range(0, HEIGHT):
for x in range(0, WIDTH):
point_mass.append((x, y, mass(matrix, x, y)))
Die Sortierung der Liste auf die Masse für jeden Punkt:
from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)
Mit Blick auf die Top-9 Punkte in dieser sortierten Liste:
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 1, 4.6736111111111107)
(1, 4, 4.5938888888888885)
(2, 0, 4.54)
(4, 7, 4.4480555555555554)
(1, 5, 4.4480555555555554)
(5, 7, 4.4059637188208614)
(4, 8, 4.3659637188208613)
Wenn wir vom höchsten zum niedrigsten und Filter entfernt Punkte funktionieren würden, die zu nahe an bereits Punkte gesehen wir bekommen (ich mache es manuell, da ich jetzt, es zu tun in Code aus der Zeit ausgeführt habe .. .):
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)
, die sie von einem Blick auf Ihrer Matrix ein ziemlich intuitives Ergebnis ist (beachten Sie, dass die Koordinaten Null basieren, wenn sie mit Ihrem Beispiel zu vergleichen).
Andere Tipps
Sie müssen ein Cluster-Algorithmus, so einfach ist, da Sie nur eine 2-dimensionale Gitter haben, und die Einträge grenzen sich gegenseitig. Sie können nur ein Floodfill Algorithmus . Sobald Sie jeden Cluster haben, können Sie das Zentrum, wie in der 2D Massenmittelartikel. .
Hier eine ähnliche Frage mit einem nicht so schnellen Algorithmus, und mehrere andere bessere Möglichkeiten, es zu tun.
Mein erster Gedanke wäre, zunächst jede Zelle mit einem Nicht-Null-Wert zu finden. Von dort einig Flut-Fill-Algorithmus, zu tun und das Zentrum der Masse der gefundenen Zellen berechnen. die gefundenen Zellen aus der Matrix Next Null aus, und beginnt von oben über.
Dies würde natürlich nicht so gut wie die Methode von Google skalieren, dass tuinstoel verbunden, aber wäre einfacher für kleinere Matrizen zu implementieren.
EDIT:
disjunkte Mengen (mit Weg Kompression und Union-by-Rang) hier nützlich sein könnten. Sie haben O ( α ( n )) Zeitkomplexität für die Vereinigung und finden-Set, wobei
α ( n ) = min { K A K ( 1) ≥ n }.
A K ( n ) ist die Ackerman-Funktion, so α ( n ) wird im wesentlichen sein O (1) für alle vernünftigen Werte. Das einzige Problem ist, dass disjunkte Mengen eine Einbahn Abbildung von Punkt zu setzen, aber das wird keine Rolle, ob Sie Trog alle Elemente gehen.
Hier ist ein einfacher Python-Skript für die Demonstration:
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()
Ausgabe:
. 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
Der Punkt war disjunkte Mengen zu demonstrieren. Der eigentliche Algorithmus in find_clusters() etwas robusten aufgerüstet werden kann.
Referenzen
- Einführung in Algorithmen. 2nd ed. Cormen et.al.
