计数平方算法

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:4

x: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&nbsp; === (toRight && down)// upperRight === (toLeft && down)// lowerLeft&nbsp; === (toRight && up)// lowerRight === (toLeft && up)for pt in points&nbsp; if pt.toRight&nbsp; &nbsp; if pt.down&nbsp; &nbsp; &nbsp; upperLeft.append(pt)&nbsp; &nbsp; end&nbsp; &nbsp; if pt.up&nbsp; &nbsp; &nbsp; lowerLeft.append(pt)&nbsp; &nbsp; end&nbsp; end&nbsp; if pt.toLeft&nbsp; &nbsp; if pt.down&nbsp; &nbsp; &nbsp; upperRight.append(pt)&nbsp; &nbsp; end&nbsp; &nbsp; if pt.up&nbsp; &nbsp; &nbsp; lowerRight.append(pt)&nbsp; &nbsp; end&nbsp; endend注意： a）有些点属于所有4个列表，因此不要else-if用于任何比较b）41个点中，只有26个属于每个列表现在，通过从4个列表中选择点来找到正方形。如果您一直等到选择了一个潜在正方形的所有4个角，则将检查26*26*26*26 (456,976)正方形。您可以拒绝无法立即解决的问题，从而加快流程。例如，一旦有了左上点，便知道右上点必须具有相同的垂直（y值），并且右上值必须在左上值的右边。选择左下点时，它应位于左上点下方（相同的x值），并且距左上点的距离应与左上点距右上点的距离相同（因为寻找正方形）。当您选择右下角点时，它应与左下角点（相同的y值）和右上角点（相同的x值）对齐。squares = 0for ul in upperLeft&nbsp; for ur in upperRight&nbsp; &nbsp; next if ur is not at same vertical and to the right of ul&nbsp; &nbsp; for ll in lowerLeft&nbsp; &nbsp; &nbsp; next if ll is not at same horizontal and below ul&nbsp; &nbsp; &nbsp; next if dist(ul,ll) != dist(ul,ur)&nbsp; // looking for squares&nbsp; &nbsp; &nbsp; for lr in lowerRight&nbsp; &nbsp; &nbsp; &nbsp; next if lr not at same vertical as ll&nbsp; &nbsp; &nbsp; &nbsp; next if lr not at same horizontal as ur&nbsp; &nbsp; &nbsp; &nbsp; squares += 1&nbsp; &nbsp; &nbsp; end&nbsp; &nbsp; end&nbsp; endend这是我用Swift编写的解决方案：typealias GridPoint = (x: Int, y: Int, left: Bool, right: Bool, up: Bool, down: Bool)let points: [GridPoint] = [&nbsp; &nbsp; (0, 0, false, true, false, true),&nbsp; &nbsp; (2, 0, true, true, false, true),&nbsp; &nbsp; (4, 0, true, true, false, true),&nbsp; &nbsp; (6, 0, true, true, false, true),&nbsp; &nbsp; (8, 0, true, false, false, true),&nbsp; &nbsp; (0, 2, false, true, true, true),&nbsp; &nbsp; (2, 2, true, true, true, true),&nbsp; &nbsp; (4, 2, true, true, true, true),&nbsp; &nbsp; (6, 2, true, true, true, true),&nbsp; &nbsp; (8, 2, true, false, true, true),&nbsp; &nbsp; (0, 4, false, true, true, true),&nbsp; &nbsp; (2, 4, true, true, true, true),&nbsp; &nbsp; (4, 4, true, true, true, true),&nbsp; &nbsp; (6, 4, true, true, true, true),&nbsp; &nbsp; (8, 4, true, false, true, true),&nbsp; &nbsp; (0, 6, false, true, true, true),&nbsp; &nbsp; (2, 6, true, true, true, true),&nbsp; &nbsp; (4, 6, true, true, true, true),&nbsp; &nbsp; (6, 6, true, true, true, true),&nbsp; &nbsp; (8, 6, true, false, true, true),&nbsp; &nbsp; (0, 8, false, true, true, false),&nbsp; &nbsp; (2, 8, true, true, true, false),&nbsp; &nbsp; (4, 8, true, true, true, false),&nbsp; &nbsp; (6, 8, true, true, true, false),&nbsp; &nbsp; (8, 8, true, false, true, false),&nbsp; &nbsp; (3, 1, false, true, false, true),&nbsp; &nbsp; (4, 1, true, true, true, true),&nbsp; &nbsp; (5, 1, true, false, false, true),&nbsp; &nbsp; (3, 2, true, true, true, true),&nbsp; &nbsp; (5, 2, true, true, true, true),&nbsp; &nbsp; (3, 3, false, true, true, false),&nbsp; &nbsp; (4, 3, true, true, true, true),&nbsp; &nbsp; (5, 3, true, false, true, false),&nbsp; &nbsp; (3, 5, false, true, false, true),&nbsp; &nbsp; (4, 5, true, true, true, true),&nbsp; &nbsp; (5, 5, true, false, false, true),&nbsp; &nbsp; (3, 6, true, true, true, true),&nbsp; &nbsp; (5, 6, true, true, true, true),&nbsp; &nbsp; (3, 7, false, true, true, false),&nbsp; &nbsp; (4, 7, true, true, true, true),&nbsp; &nbsp; (5, 7, true, false, true, false),]var upperLeft&nbsp; = [GridPoint]()var upperRight = [GridPoint]()var lowerLeft&nbsp; = [GridPoint]()var lowerRight = [GridPoint]()for pt in points {&nbsp; &nbsp; if pt.right {&nbsp; &nbsp; &nbsp; &nbsp; if pt.down {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; upperLeft.append(pt)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if pt.up {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lowerLeft.append(pt)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; if pt.left {&nbsp; &nbsp; &nbsp; &nbsp; if pt.down {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; upperRight.append(pt)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if pt.up {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lowerRight.append(pt)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}print(upperLeft.count)&nbsp; &nbsp;// 26print(upperRight.count)&nbsp; // 26print(lowerLeft.count)&nbsp; &nbsp;// 26print(lowerRight.count)&nbsp; // 26var squares = 0for ul in upperLeft {&nbsp; &nbsp; for ur in upperRight {&nbsp; &nbsp; &nbsp; &nbsp; if ul.y != ur.y || ul.x >= ur.x {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for ll in lowerLeft {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ll.x != ul.x || ll.y <= ul.y || (ll.y - ul.y != ur.x - ul.x) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for lr in lowerRight {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if lr.x != ur.x || lr.y != ll.y {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; squares += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}print(squares)&nbsp; // 40以下是符合左上角的26点：