计数平方算法

Question

我正在写算法，该算法必须在此图中计算平方：在数据库中，我有这些列的所有点：x-coordinate，y-coordinate，toRight，toLeft，up和down。toRight，toLeft等等都是布尔和手段，你可以移动到从该点或不是方向。但是我不清楚如何利用方向信息。我现在所拥有的是以下代码：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将点分类为组，然后返回多维数组，这些多维数组具有来自这些分类点的所有可能的垂直边缘。想法是使这些边缘的每一组都循环通过，并检查另一组是否具有相反的边缘。例如edge ，然后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:4x:0 y:0 - x:0 y:6 对于相反的边缘，则必须进一步查看3组： x:6 y:0 - x:6 y:6等等。但是我不清楚如何编写此代码，这看起来像是错误的方法。什么是计数平方算法的更好方法？谢谢

Answer 1

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

这是使用该信息的可能算法：

创建列表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个属于每个列表

现在，通过从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点：