0

给定一个网格图，其中每个单元格可以用一对来描述(x, y)，以及这些单元格的向量，我如何（很好地）检查该向量中的单元格是否形成“隧道”，即。它们都是垂直排列还是水平排列？但是，如果我只想查看它们中的大多数是否排成一列（而不是全部）怎么办？

All are lines up             Most are lined up      Not lined up

                             C                       C C C
 C C C C C C C C             C C C C C C C C         C   C C C
                                 C                   C C C C
                                                         C C
4

3 回答 3

2

您可以制作单元格的 x 和 y 坐标的直方图。如果所有单元格水平排列，则在直方图中您只会得到一个 y 值和许多连续的 x 值，这些都只出现一次。垂直与 x 和 y 翻转相同。

如果要检查，如果它们中的大多数都排成一行，请在直方图中搜索出现次数最多（可能的隧道最长）的值，并检查具有该 x 或 y 坐标的单元格，如果它们排成一行（也就是说：它们的 y 或 x 坐标（取决于上一步中使用的是 x 还是 y）是连续的，没有间隙（可能首先对它们进行排序））如果不是，则搜索第二高的出现值，.. .

于 2012-04-13T19:01:25.127 回答
1

您可以通过首先检查它们的y坐标是否相等来检查它们是否构成水平隧道，然后按x坐标排序并从左到右遍历以检查间隙。使用相反的坐标检查垂直隧道。

对于近似检查，您必须澄清“大多数”的含义。

于 2012-04-13T18:58:47.143 回答
1

您可以计算 X 和 Y 坐标的标准偏差。您的单元格越“隧道”，X 或 Y 的标准偏差就越低。

例如，在 Python 中：

import numpy

def is_tunnelled(cells):
    # given cells=[(x,y), (x,y),...]
    x_values, y_values = zip(*cells)
    lowest_std_dev = min(numpy.std(x_values), numpy.std(y_values))
    return lowest_std_dev < STD_DEVIATION_THRESHOLD

由您决定 STD_DEVIATION_THRESHOLD 的值应该是多少。

于 2012-04-13T19:05:36.593 回答