用最大数量的网格正方形填充多边形
Filling a polygon with maximum number of grid squares
我有一个二维多边形。
我将它放在一个正方形网格上并标记完全在形状内的正方形。
我需要找到最大化标记方块数量的位置。多边形方向固定，只能平移
我该怎么做？
多边形很大，网格方块的尺寸很小（例如 10x10 像素）？
然后有一个简单的暴力解决方案：
- 从一个格子开始，数一数方格。
2.1-2.10 将网格向右移动1px，统计并更新最好成绩。
将网格向上移动 1px，如果需要则计算并更新最佳分数。
重复又名转到 2.1，直到检查所有可能的解决方案...
检查正方形是否在多边形内很容易。你可以实现一个沿着边缘的算法...
如果我们只能将多边形 P 向右移动并且单元格的宽度等于 w[=60= ，那么让我们解决这个问题].
首先，注意在[0中探索距离dP的位移就足够了; w)，因为如果我们将P向右移动到w，我们会得到与没有移动相同的情况完全没有。
设SP为当前在P中的单元格数量。假设我们将 P 移动了一点。会发生什么？好吧，现在网格的一些顶点可能在 P 之外（我们称这个集合为 O），一些新的顶点现在可能在在 P 中（设置 I）。如何确定我们是否丢失或获得了任何细胞？如果一个单元格在 P 并且有角，在 O，那么我们应该减少 S P。相反，如果一个单元格在 I 中有角，而其他角已经在 P 中，那么我们应该增加 S P.
现在让我们通过增加与 P 初始位置的距离来对这些事件（获取和丢失顶点）进行排序。因此，我们在算法中形式化了 "little steps" 的顺序。
现在我们可以写一些伪代码了：
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
方法接近于sweep line。
UPD: 为了概括这一点，我们需要注意对于 P 的任何最佳位置存在另一个最佳位置 P 在一条边上有一个网格顶点。所以解决方案是固定一些网格顶点 G 并移动 P "around" 所以 P 总是有 G 一步一步地在边缘上，其中步骤是由发生的事件产生的，如上所述。算法取 O(|P| / w).
我有一个二维多边形。
我将它放在一个正方形网格上并标记完全在形状内的正方形。
我需要找到最大化标记方块数量的位置。多边形方向固定，只能平移
我该怎么做？
多边形很大，网格方块的尺寸很小（例如 10x10 像素）？
然后有一个简单的暴力解决方案：
- 从一个格子开始，数一数方格。
2.1-2.10 将网格向右移动1px，统计并更新最好成绩。
将网格向上移动 1px，如果需要则计算并更新最佳分数。
重复又名转到 2.1，直到检查所有可能的解决方案...
检查正方形是否在多边形内很容易。你可以实现一个沿着边缘的算法...
如果我们只能将多边形 P 向右移动并且单元格的宽度等于 w[=60= ，那么让我们解决这个问题].
首先，注意在[0中探索距离dP的位移就足够了; w)，因为如果我们将P向右移动到w，我们会得到与没有移动相同的情况完全没有。
设SP为当前在P中的单元格数量。假设我们将 P 移动了一点。会发生什么？好吧，现在网格的一些顶点可能在 P 之外（我们称这个集合为 O），一些新的顶点现在可能在在 P 中（设置 I）。如何确定我们是否丢失或获得了任何细胞？如果一个单元格在 P 并且有角，在 O，那么我们应该减少 S P。相反，如果一个单元格在 I 中有角，而其他角已经在 P 中，那么我们应该增加 S P.
现在让我们通过增加与 P 初始位置的距离来对这些事件（获取和丢失顶点）进行排序。因此，我们在算法中形式化了 "little steps" 的顺序。
现在我们可以写一些伪代码了：
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
方法接近于sweep line。
UPD: 为了概括这一点，我们需要注意对于 P 的任何最佳位置存在另一个最佳位置 P 在一条边上有一个网格顶点。所以解决方案是固定一些网格顶点 G 并移动 P "around" 所以 P 总是有 G 一步一步地在边缘上，其中步骤是由发生的事件产生的，如上所述。算法取 O(|P| / w).