العثور على مجموعات من كتلة في مصفوفة نقطية

Question

هذا هو في استمرار مع مسألة نشر هنا:العثور على مركز الكتلة على 2D نقطية التي تحدثت عن العثور على مركز الكتلة في منطقية مصفوفة كما في المثال أعطيت.

لنفترض الآن أننا توسيع المصفوفة إلى هذا الشكل:

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 . . .

كما ترون لدينا الآن 4 مراكز الشامل ، 4 مجموعات مختلفة.

نحن نعلم بالفعل كيفية ايجاد مركز الكتلة بالنظر إلى أن واحدة فقط موجود, إذا كنا تشغيل هذه الخوارزمية على هذه المصفوفة سوف تحصل على نقطة في منتصف المصفوفة التي لا تساعدنا.

ماذا يمكن أن تكون جيدة وصحيحة سريع خوارزمية لإيجاد هذه المجموعات ؟

Answer 1

وأعتقد أنني سوف تحقق كل نقطة في المصفوفة، ومعرفة أنها تقوم كتلة على الجيران انها. كتلة للحصول على نقاط ستقع مع تقول مربع المسافة. يمكنك بعد ذلك اختيار أعلى أربع نقاط مع مسافة لا تقل عن بعضها البعض.

وفيما يلي بعض التعليمات البرمجية بايثون I جلد معا في محاولة لتوضيح النهج لمعرفة كتلة لكل نقطة. بعض الإعداد باستخدام مصفوفة المثال الخاص بك:

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

لحساب كتلة لنقطة معينة:

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

ملحوظة: أنا باستخدام مانهاتن مسافات (الملقب Cityblock، ويعرف أيضا باسم سيارة الأجرة الهندسة) هنا لأنني لا أعتقد أن الدقة المضافة باستخدام المسافات الإقليدية يستحق تكلفة الاتصال الجذر التربيعي ().

وبالتكرار عبر مصفوفة لدينا وبناء قائمة من المجموعات مثل (س، ص، كتلة (س، ص)):

point_mass = []
for y in range(0, HEIGHT):
  for x in range(0, WIDTH):
    point_mass.append((x, y, mass(matrix, x, y)))

وفرز القائمة على كتلة لكل نقطة:

from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)

وإذا نظرنا إلى أعلى 9 نقاط في تلك القائمة التي تم فرزها:

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

إذا كنا العمل من الأعلى إلى الأدنى وتصفية بعيدا النقاط التي هي قريبة جدا من النقاط التي ستحصل على (أنا أفعل ذلك يدويا منذ ان كنت نفاد الوقت الآن للقيام بذلك في التعليمات البرمجية رأينا بالفعل .. .):

(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)

والذي هو نتيجة بديهية جدا من مجرد النظر في مصفوفة (لاحظ أن الإحداثيات صفر مقرها عند مقارنة مع المثال الخاص بك).

Answer 2

وتحتاج خوارزمية التجميع، وهذا أمر سهل لأن لديك فقط شبكة الأبعاد 2، والإدخالات المتاخمة بعضها البعض. يمكنك استخدام مجرد ملء فيضاني خوارزمية . وبمجرد الانتهاء من كل مجموعة، يمكنك العثور على مركز كما في مركز 2D المادة الجماعية. .

Answer 3

هنا سؤال مماثل مع خوارزمية يست سريعة جدا، والعديد طرق أخرى أفضل للقيام بذلك.

Answer 4

فكرتي الأولى أن يكون أول من العثور على أي خلية مع قيمة غير صفرية.من هناك بعض الفيضانات ملء الخوارزمية و حساب مركز الكتلة من الخلايا الموجودة.التالي صفر وجدت الخلايا من المصفوفة ، والبدء من جديد من أعلى.

هذا بالطبع ليس مقياس وكذلك طريقة من جوجل ، tuinstoel مرتبطة ، ولكن سيكون من الأسهل لتنفيذ أصغر المصفوفات.

تحرير:

منفصلة مجموعات (باستخدام مسار وضغط الاتحاد-قبل-رتبة) يمكن أن تكون مفيدة هنا.لديهم O(α(n)) تعقيد وقت الاتحاد و تجد مجموعة ، حيث

α(n) = min { k :A_k(1) ≥ n }.

A_k(n) هو أكرمان وظيفة α(n) سوف تكون أساسا O(1) أي قيم معقولة.المشكلة الوحيدة هي أن مجموعات منفصلة هي واحدة-طريقة رسم الخرائط من البند ولكن هذا لن يهم إذا كنت تسير الحوض الصغير جميع البنود.

هنا هو بسيط بيثون السيناريو مظاهرة:

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() يمكن أن تتم ترقية إلى شيء أكثر قوة.

المراجع

• مقدمة إلى الخوارزميات. 2nd ed.Cormen وآخرون.al.