2

我有一个定义为向量的形状。然后我会得到一个数字，它代表我需要在我的形状上平铺多少个相同大小的正方形，在一系列行中。行内每个正方形的 X 坐标不需要与其他行的 X 坐标对齐。我需要确定正方形所需的大小，以及它们在形状（X 和 Y）上的位置，以便完全覆盖形状的内部，并且在周边上，每个正方形的大部分面积都在形状内.

有谁知道我可以用来计算这个的任何公式？或者我会通过解决这个问题来获得自己的博士学位吗？:-)

4

1 回答 1

1

迭代过程的可能解决方案：

初步说明：-我正在标记稍后使用符号 <...> 使用的变量名称，如果它是一个数组，我会在方括号中记下变量的维度。- 在圆括号中，您可以找到通常以“i”作为迭代计数器的迭代段落。

给定：

I1) 二维直边图形的顶点数组 [2,n]：(1:i:2, 1:j:n)，因此是一个大小为 2 x n 的整数数组。

I2) 覆盖图形的最大网格元素数： ，所以是一个标量值

I3) 作为顶点定位参考的 2D OCS（正交坐标系）：默认情况下，所有顶点将通过它们自己的值提供 OCS。将其称为前参考，但它并不是真正的变量。

输出：

O1) 提供了最多覆盖给定形状的方形网格的边长： ，所以是一个标量。

O2) 生成的行数： ，另一个标量

O3）每串（一行）方格的X值数组，表示第一个方格网格元素的左下角：用1:i:R，其中R是前面提到的输出，所以生成的行数由算法。

O4）包含每行网格元素数量的整数数组：1：i：R

辅助功能：

//计算覆盖因子

ACF：（平均覆盖因子），计算整个原始形状的面积与生成的所有正方形数组的总和之间的比率（给定正方形的左下角列表加上边长）。

SCF：（单个元素覆盖因子）：计算每个单个正方形区域被（重叠）形状覆盖的百分比。这很棘手，但可以通过以有限元网格划分样式进行三角剖分来计算（您可以在线找到网格划分三角形元素技术）。

算法：

1）定义最小边界框（包含整个形状的第一个正方形）

1.1）定义原始OCS中的最低Y形点：所以一个标量表示OCS0和OCS1之间的垂直偏移。

1.2）在原始OCS中定义最左边的形状点（顶点之一）：

1.3) 用刚性线性变换 T:T(x,y) -> (x-dx, y-dy) 移动形状；现在边界框在新坐标系的原点左下角（这是将 OCS0 映射到 OCS1 的原因）

1.4）在OCS1中移动整个图形；

1.6）在步骤0计算平均覆盖因子；

注意：这已经是一个解决方案，不是最好的，而是一个数学上可接受的解决方案。

1.7）检查有多少元素（在这个阶段只有一个）完全包含在形状中，调用它（在第一步中这是零），有多少元素被形状边界完全排除（在第一步中这是零），以及有多少部分重叠（在第一步中，这是 1）。请注意，在迭代过程中，这三个数组的长度之和必须等于边界正方形的细化生成的正方形数。

1.8) 从网格中删除所有属于 NFULLOUT(0) 的正方形。在第 0 步，该例程不提供任何结果，因为解决方案数组中只有一个部分覆盖的元素。

2）循环细化

2.1）通过RF = M /（QTY（1：R）的总和）计算细化因子

注意：第 2.1 点考虑面积计算中权重为 1 的所有全覆盖元素以及部分元素，更精确的方法是在每个单个部分覆盖正方形上使用 SCF 函数来计算要用于的元素的有效权重网格面积计算。

2.2) 通过L(1) = L(0)/RF计算新的正方形边长；

2.3）如果（方格数低于允许的方格数），通过用新边重新生成方格矩阵来细化网格。

2.3.1）检查有多少元素（在此阶段只有一个）完全包含在形状中（在第一步中为零），有多少元素被形状边界完全排除（在第一步中为零） )，以及有多少部分重叠（在第一步中，这是 1），其中“i”表示迭代的步骤以进行细化。

2.3.2) 从网格中删除所有属于 NFULLOUT(i) 的正方形。在第 0 步，此例程不提供任何结果，因为解决方案数组中只有一个部分元素。

2.3.4）通过RF = M /（QTY（1：R）的总和）计算细化因子

2.3.5) 通过L(1) = L(0)/RF计算新的正方形边长；

2.3.6) if L(i) > 0 then re-loop from 2) else break。

3）休息后，分而治之以求改进

3.1）对于网格的每一行，尝试左右移动大约一半边长的整行，计算效率并决定哪个更好。然后你将尝试和验证的那条线移动得更好，再次选择左右边长为 1/4 的长度，依此类推，直到你得到比上一步更低的效率。

注意：只有当您使用 O 和 1 之间的权重对每个单独的部分元素进行加权时，才应用最后一个 divide et impera 部分。如果您将部分覆盖元素视为完全覆盖元素，这不会为您提供任何改进。

最后注：考虑您可以对 RF 应用比例因子，例如在第一次通过时，比例因子会给您 RF = M，可能会立即使您摆脱约束。每当您获得 RF > 2 时，如果您通常的元素数量在 100-1000 个或更多元素的范围内，则可以对 RF 应用 0.8 因子。

最后注2：如果您可以消除正方形应具有所有相同长度的约束，那么它会变得容易得多，而且最重要的是，当您只接近边界时，它会变得更快。

抱歉，如果这不是一个真正的公式，但我认为它是让您远离可以从计算分析中获取的复杂网格划分算法的最快元素之一。我也为不常见的符号道歉。我尽力解释自己，我不习惯标准符号。

于 2012-07-16T16:01:37.597 回答