algorithm - 用点图案填充矩形

Question

在下面的图片中有一些特定的图案。它最好在第一张图片上可见。我有标有小圆圈并用线连接的点。他们制作一些网状图案。有些点是错误的，不符合模式(标记在第一张图片上)。 目标是填充整个标有红色的矩形(矩形是从极值点创建的 - 模式坐标系中具有极值坐标的点)。

问题是应该采取什么方法来用点填充矩形，并消除错误的点。第二张图片的情况是极端的，但主要是点数较多的情况。

图像仅用于可视化。我有带点坐标的向量。无需检测点。

我会在找到解决方案后立即添加。

我目前的方法是创建平行于具有已知图案偏移的较长矩形边的线。然后在线附近寻找具有一定delta距离的点，并填充其余点。

Answer 1

总的来说，我要做的是首先确定网格，然后很容易检查该网格上是否有东西。

这些是步骤:

• 旋转所有内容，以便只有水平线和垂直线。

• 每个 x 值计算您有多少分。

• 每个值计算你有多少分。

伪代码:

xcount is array of int
ycount is array of int

for x=0 to width-1 do
  for y=0 to height-1 do
    foreach point do
      if point.x = x then
        xcount[x]++
      if point.y = y then
        ycount[y]++ 

对于你的最后一张图片，结果应该是这样的:

x-count:1,0,0,0,3,0,2,0,1,0,0,0,4,0,0,0,3,0,0,0,4
y-count:2,0,0,0,6,0,0,0,4,0,1,0,3,0,1,0,1

• 现在检测网格大小:

  匹配 = 0 对于 i=1 到 10 做 foreach xcount 做 如果 xcount mod i=0 那么 匹配[i]++

现在我们有一个数组，其中包含 10 种不同网格大小的分数(匹配的点数)。它可能看起来像这样:

gridscores[] = 5,5,0,5,34,5,0,5

XgridSize = index of greatest gridSore

• 34 显然是最佳匹配，它位于索引 5，因此网格大小为 5。

• 既然您知道了网格大小，就可以轻松找到哪些点不在该网格上:

  foreach点做 wrongpoint = (point.x mod XgridSize != 0) 或 (point.y mod YgridSize != 0)

即使有很多错误点，这仍然有效。我没有详细介绍如何旋转以及如何找到网格的偏移量，但也许这可以帮助您找到正确的方向。