2D图案搜索

Question

4

寻找2D数据数组并创建相同排序数据的边框的好算法是什么？数据将是随机的，因此除了它包含数值之外，没有任何先前的数据可用。

否则，有关此主题的任何好文章/书籍吗？

编辑

以下是我要实现的示例：

enter image description here

两个的情况也是如此

- Alex

你能提供一个小的二维数组例子吗？否则，有许多算法可以适用。 - Regenschein

如果有很多值为1的数据不与其他值为1的数据相邻，那么这是否算作两个独立的区域，还是你想要一个包含它们所有的单一区域？ - Matthew Watson

好的，现在你的边界应该具备什么功能呢？你只是想像示例中那样绘制它吗？还是要用它来表示“2”属于区域“B”之类的分类问题？或者你只是想从坐标中猜测它属于哪个类别... - Regenschein

我想创建一个数据结构，可以创建边界路径，然后将其写入像GDS II这样的文件格式。 - Alex

1

针对每个点进行泛洪填充？ - Bernhard Barker

显示剩余3条评论

3个回答

1

这是一个复杂的问题，我认为它相当于找到一组点的凹壳。

首先，您需要为数据点定义一个相等操作，以便确定“相同排序”的数据点集。

在这样确定一组点后，您需要找到该点集的凹壳。

(我假设您想要凹壳而不是凸壳)。

找到凹壳是一个非平凡的任务。

如果实际上是凸壳您想要的，请参见此处的 C# 实现：

- Matthew Watson

这确实是一个非常好的建议。在原始帖子的编辑之后，似乎找到凹壳确实是必要的。然而，如果像图片所示，输入实际上只是一个2D数组，那么它可能比那更简单，并且（非几何）搜索算法可能会起作用。 - Yellow

在定义凸包时，您需要对多边形定义某种限制（否则，通过连接每个点的线可以实现最小面积为0）。 - Teepeemm

0

一个天真的解决方案（对于小数据集来说可以很好地工作）是定义一个比较运算符，它接受两个参数并返回true如果它们相等，否则返回false，然后简单地比较所有相邻值对（水平和垂直）并在比较返回false时绘制边框。

- PeterK

不幸的是，这适用于相当大的数据集。 - Alex

有多大？你需要多频繁地进行这个计算？即使对于数百万个数据点，这也会非常快，所以除非你有数十亿个数据点并且需要实时处理，否则这应该是可以的。 - PeterK

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aravind · Accepted Answer

广度优先搜索可以帮助您解决问题。首先按以下方式构造图G：

当且仅当第u个单元格的值=第v个单元格的值时，图G具有边缘(u,v)。

然后执行BFS可得到图的好部分，您可以方便地使用单元格的值标记这些部分已被访问过。