php - 计数方 block 算法

Question

我正在编写必须计算该图中正方形的算法:

在数据库中我有这些列的所有点:x-coordinate, y-coordinate, toRight, toLeft、向上和向下。 toRight、toLeft 等是 bool 值，表示您是否可以从该点向该方向移动。

但是我不清楚如何利用有关方向的信息。我现在拥有的是这段代码:

public function count(array $points)
{ 
    $pointsGroupedByX = array();
    $edges = array();

    foreach ($points as $point) {
        $key = $point->getX();

        if (!in_array($key, array_keys($pointsGroupedByX))) {
            $pointsGroupedByX[$key] = array();
        }

        if (!in_array($point, $pointsGroupedByX[$key])) {
            $pointsGroupedByX[$key][] = $point;
        }
    }

    foreach ($pointsGroupedByX as $group) {
        for ($i = 0; $i < count($group) - 1; $i++) {
            for ($j = 0; $j < count($group) - 1; $j++) {

                if ($group[$i] === $group[$j + 1] || $group[$i] > $group[$j + 1]) {
                    continue;
                }

                $edge = array($group[$i], $group[$j + 1]);
                $key = $group[$i]->getX();

                if (!in_array($key, array_keys($edges))) {
                    $edges[$key] = array();
                }

                $edges[$key][] = $edge;
            }
        }   
    }
}

它首先按 x-coordinate 将点分组，然后返回多维数组，其中包含这些排序点的所有可能的垂直边。

想法是遍历每组这些边并检查另一组是否有相反的边。例如边 x:0 y:0 - x:0 y:2，下一组必须有 x:2 y:0 - x:2 y:2，然后:

x:0 y:0 - x:0 y:4 对边必须进一步看 2 组:x:4 y:0 - x:4 y:4

x:0 y:0 - x:0 y:6 对边必须进一步看 3 组:x:6 y:0 - x:6 y:6

等等。

但是我不清楚如何写这个，而且看起来是错误的方法。

什么是计算平方算法的更好方法？谢谢

编辑:

按照 vacawama 的回答中的算法，现在我有了这段代码 (php):

$upperLeft = array();
$upperRight = array();
$lowerRight = array();
$lowerLeft = array();
$squares = 0;

foreach ($points as $point) {
    if ($point->getToRight()) {
        if ($point->getDown()) {
            $upperLeft[] = $point;
        }

        if ($point->getUp()) {
            $lowerLeft[] = $point;
        }
    }
    if ($point->getToLeft()) {
        if ($point->getDown()) {
            $upperRight[] = $point;
        }

        if ($point->getUp()) {
            $lowerRight[] = $point;
        }
    }
}

foreach ($upperLeft as $ul) {
    foreach ($upperRight as $ur) {
        if ($ur->getY() !== $ul->getY() || $ur->getX() > $ul->getX()) { // ur is not at same vertical as ul or not to the right of ul
            continue;
        }
        foreach ($lowerLeft as $ll) {
            if ($ll->getX() !== $ul->getX() || $ll->getY() < $ul->getY()) { // ll is not at same horizontal as ul or not bellow ul
                continue;
            }
            if ($ll->getY() - $ul->getY() !== $ur->getX() - $ul->getX()) {
                continue;
            }
            foreach ($lowerRight as $lr) {
                if ($lr->getY() !== $ll->getY()) {
                    continue;
                }
                if ($lr->getX() !== $ur->getX()) {
                    continue;
                }
                $squares++;
            }
        }
    }
}
return $squares;

但是它返回错误的答案。

有 17 个点，而不是 26 个点属于所有 4 个列表，并且此代码以某种方式返回 17 作为正方形计数。

Answer 1

您可以使用这些属性来判断一个点是否是有效的 upperLeft、upperRight、lowerLeft 或 lowerRight点。

这是一个使用该信息的可能算法:

1. 创建 upperLeft、upperRight、lowerLeft 或 lowerRight 点的列表。

   // Attributes for inclusion:
   // upperLeft  === (toRight && down)
   // upperRight === (toLeft && down)
   // lowerLeft  === (toRight && up)
   // lowerRight === (toLeft && up)
   
   for pt in points
     if pt.toRight
       if pt.down
         upperLeft.append(pt)
       end
       if pt.up
         lowerLeft.append(pt)
       end
     end
     if pt.toLeft
       if pt.down
         upperRight.append(pt)
       end
       if pt.up
         lowerRight.append(pt)
       end
     end
   end
   

   注意: a) 有些点属于所有 4 个列表，所以不要使用 else-if 进行任何比较 b) 在 41 个点中，只有26个属于每个列表

2. 现在，通过从 4 个列表中选择点来找到正方形。如果您等到您选择了一个潜在正方形的所有 4 个角，您将检查 26*26*26*26 (456,976) 正方形。您可以通过拒绝不能立即起作用的点来加快该过程。例如，一旦你有一个左上点，你就知道右上点必须有相同的垂直(y 值)并且你的右上值必须在左上值的右边。当你选择左下点时，它应该在左上点下方(相同的 x 值)并且它与左上点的距离应该与左上点与右上点的距离相同(因为你是寻找正方形)。当您选择右下点时，它应该与左下点(相同的 y 值)和右上点(相同的 x 值)对齐。

   squares = 0
   for ul in upperLeft
     for ur in upperRight
       next if ur is not at same vertical and to the right of ul
       for ll in lowerLeft
         next if ll is not at same horizontal and below ul
         next if dist(ul,ll) != dist(ul,ur)  // looking for squares
         for lr in lowerRight
           next if lr not at same vertical as ll
           next if lr not at same horizontal as ur
           squares += 1
         end
       end
     end
   end
   

---

这是我用 Swift 编写的解决方案:

typealias GridPoint = (x: Int, y: Int, left: Bool, right: Bool, up: Bool, down: Bool)

let points: [GridPoint] = [
    (0, 0, false, true, false, true),
    (2, 0, true, true, false, true),
    (4, 0, true, true, false, true),
    (6, 0, true, true, false, true),
    (8, 0, true, false, false, true),
    (0, 2, false, true, true, true),
    (2, 2, true, true, true, true),
    (4, 2, true, true, true, true),
    (6, 2, true, true, true, true),
    (8, 2, true, false, true, true),
    (0, 4, false, true, true, true),
    (2, 4, true, true, true, true),
    (4, 4, true, true, true, true),
    (6, 4, true, true, true, true),
    (8, 4, true, false, true, true),
    (0, 6, false, true, true, true),
    (2, 6, true, true, true, true),
    (4, 6, true, true, true, true),
    (6, 6, true, true, true, true),
    (8, 6, true, false, true, true),
    (0, 8, false, true, true, false),
    (2, 8, true, true, true, false),
    (4, 8, true, true, true, false),
    (6, 8, true, true, true, false),
    (8, 8, true, false, true, false),
    (3, 1, false, true, false, true),
    (4, 1, true, true, true, true),
    (5, 1, true, false, false, true),
    (3, 2, true, true, true, true),
    (5, 2, true, true, true, true),
    (3, 3, false, true, true, false),
    (4, 3, true, true, true, true),
    (5, 3, true, false, true, false),
    (3, 5, false, true, false, true),
    (4, 5, true, true, true, true),
    (5, 5, true, false, false, true),
    (3, 6, true, true, true, true),
    (5, 6, true, true, true, true),
    (3, 7, false, true, true, false),
    (4, 7, true, true, true, true),
    (5, 7, true, false, true, false),

]

var upperLeft  = [GridPoint]()
var upperRight = [GridPoint]()
var lowerLeft  = [GridPoint]()
var lowerRight = [GridPoint]()

for pt in points {
    if pt.right {
        if pt.down {
            upperLeft.append(pt)
        }
        if pt.up {
            lowerLeft.append(pt)
        }
    }
    if pt.left {
        if pt.down {
            upperRight.append(pt)
        }
        if pt.up {
            lowerRight.append(pt)
        }
    }
}

print(upperLeft.count)   // 26
print(upperRight.count)  // 26
print(lowerLeft.count)   // 26
print(lowerRight.count)  // 26

var squares = 0

for ul in upperLeft {
    for ur in upperRight {
        if ul.y != ur.y || ul.x >= ur.x {
            continue
        }
        for ll in lowerLeft {
            if ll.x != ul.x || ll.y <= ul.y || (ll.y - ul.y != ur.x - ul.x) {
                continue
            }
            for lr in lowerRight {
                if lr.x != ur.x || lr.y != ll.y {
                    continue
                }
                squares += 1
            }
        }
    }
}

print(squares)  // 40

---

以下是符合左上角条件的 26 个点: