用最多的网格方块填充多边形

Question

用最多的网格方块填充多边形

algorithm2dpolygonrectangles

4

我有一个二维多边形。

我将它放在一个正方形网格上，并标记完全在形状内的正方形。

我需要找到能够最大化标记的正方形数量的位置。多边形方向已固定，只能进行平移。

怎样才能实现这个目标？

- Hubert OG

2个回答

1

如果多边形很大，网格方块的大小很小（例如10x10像素）？

那么有一个简单的暴力解决方案：

从一个网格开始，计算方块数。

2.1-2.10将网格向右移动1个像素，计算并更新最佳得分（如果需要）。

将网格向上移动1个像素，计算并更新最佳得分（如果需要）。
重复即进入2.1，直到检查完所有可能的解决方案...

很容易检查一个正方形是否在多边形内。您可以实现沿着边缘走的算法...

- Adrian Kowol

谢谢，但不幸的是这不是情况。我拥有的多边形可以被任意距离平移，而不仅仅是整数距离。 - Hubert OG

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

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

- Paul · Accepted Answer

让我们解决一下这个问题：如果我们只能将多边形 P 向右移动，且单元格的宽度为 w。

首先，注意到只需要探索距离 [0; w) 中的 d_P 距离的移位，因为如果我们将 P 向右移动了 w，那么和不移动它是相同的情况。

设 S_P 是当前在 P 中的单元格数。假设我们稍微移动了一下 P。会发生什么？嗯，网格的一些顶点现在可能已经不在 P 中了（我们称这个集合为 O），有些新的顶点现在可能在 P 中（集合 I）。如何确定是否失去或获得任何单元格？如果一个单元格在 P 中，并且具有在 O 中的角，则应该减少S_P。如果相反，一个单元格的角在 I 中，而其他角已经在P中，则应该增加 S_P。

让我们现在按其距离从 P 的初始位置递增地对这些事件（获取和失去顶点）进行排序。这样，我们就将算法中“小步骤”的顺序形式化了。

现在我们可以写一些伪代码：

def signedDistance(vertex, edge):
    p = [ closest point of edge to vertex ]
    return vertex.x - p.x

Events = { (vertex, edge) : 0 <= signedDistance(vertex, edge) < w }
sort(Events, [ by increasing signedDistance ])
EventsEquiv = { E' : E' is subset of Events and
                    for any a, b from E'
                    signedDistance(a.vertex, a.edge) = signedDistance(b.vertex, b.edge) }
S = [ cells in P initially ]
maxS = S
for E' in EventsEquiv:
    for e in E':
        if e is loss: S -= 1
        else if e is acquirement: S += 1
    if S > maxS:
        maxS = S

该方法类似于扫描线算法。

更新：为了推广这个解决方案，我们需要注意到对于任何最优的P位置都存在另一个最优位置，使得P在边缘上具有网格顶点。因此，解决方案是固定一些网格顶点G，并将P“在”它周围移动，使得P始终按照步骤移动，其中步骤由上述事件产生。该算法花费O(|P| / w)时间。