ベクトルとして定義された形状があります。次に、一連の行で、図形の上に並べる必要がある同じサイズの正方形の数を表す数値が提供されます。行内の各正方形の X 座標は、他の行の X 座標と揃える必要はありません。正方形の必要なサイズと、形状の内部が完全に覆われ、周囲では各正方形の領域の大部分が形状内に収まるように、形状 (X と Y) 上の配置を決定する必要があります。 .
これを計算するために使用できる式を知っている人はいますか? それとも、これを解決することで自分の博士号を取得できますか? :-)
反復プロセスで可能な解決策:
予備的な注意: -後で使用する変数名を記号 <...> でマークしています。変数が配列の場合は、変数の次元を角括弧で囲みます。- 丸括弧の中に、反復カウンターとして通常 "i" を持つ反復パッセージがあります。
与えられた:
I1) 2D 直線エッジ図形の頂点の配列 [2,n]: (1:i:2, 1:j:n)、したがって 2 x n 次元の int の配列。
I2) Figure をカバーするために使用されるメッシュ要素の最大数: 、したがってスカラー値
I3) 2D OCS (直交座標系) は、頂点の配置の基準と見なされます。デフォルトでは、すべての頂点が独自の値で OCS を提供します。事前参照と呼びますが、実際には変数ではありません。
出力：
O1) 与えられた形状をせいぜいカバーする正方形メッシュの辺の長さ: 、つまりスカラー。
O2) 生成された行数: 、別のスカラー
O3) 正方形の各文字列 (行) の X 値の配列。最初の正方形メッシュ要素の左下隅を表します。1:i:R を使用します。ここで、R は前述の出力であるため、生成される行の数はアルゴリズムによって。
O4) 行ごとのメッシュ要素の数を含む整数の配列: with 1:i:R
ヘルパー機能:
//カバーファクターを計算する
ACF: (平均被覆係数)、元の形状全体の面積と、生成されたすべての正方形の配列の合計との間の比率を計算します (正方形の左下隅のリストに辺の長さが追加されている場合)。
SCF: (単一要素被覆係数): 形状によって被覆される (重なり合う) 各単一正方形領域のパーセンテージを計算します。これは注意が必要ですが、有限要素メッシュ スタイルで三角測量を行うことにより、少しの努力で計算できます (オンラインで三角形要素のメッシュ技法を見つけることができます)。
アルゴリズム:
1) 最小境界ボックス (形状全体を含む最初の正方形) を定義します。
1.1) 元の OCS で最も低い Y 形状の点を定義します。つまり、OCS0 と OCS1 の間の垂直オフセットを表すスカラーです。
1.2) 元の OCS で最も左のシェイプ ポイント (頂点の 1 つ) を定義します。
1.3) 剛体線形変換 T:T(x,y) -> (x-dx, y-dy) で形状をシフトします。現在、バウンディング ボックスは新しい座標系の原点の左下隅にあります (これが OCS0 を OCS1 にマップするものです)。
1.4) OCS1 の図全体をシフトします。
1.6) ステップ 0 で平均カバー係数を計算します。
注：これはすでに解決策であり、最善ではありませんが、数学的に受け入れられる解決策です。
1.7) 形状に完全に含まれる要素の数 (この段階では 1 つだけ) を確認し、それを呼び出し (この最初のステップではこれはゼロ)、形状の境界によって完全に除外される要素の数 (この最初のステップではこれはゼロ)、および部分的に重複している数 (この最初のステップではこれは 1)。反復中、これら 3 つの配列の長さの合計は、境界正方形の改良によって生成された正方形の数と等しくなければならないことに注意してください。
1.8) NFULLOUT(0) に属するすべての正方形をグリッドから削除します。ステップ 0 では、ソリューション配列に部分的にカバーする要素が 1 つしかないため、このルーチンは結果を提供していません。
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 つだけ) (この最初のステップではこれはゼロ)、形状の境界によって完全に除外される要素の数 (この最初のステップではこれはゼロ) を確認します。 )、および部分的に重複している数 (この最初のステップでは、これは 1 です)。ここで、「i」は改良のための反復のステップを表します。
2.3.2) NFULLOUT(i) に属するすべての正方形をグリッドから削除します。ステップ 0 では、ソリューション配列に部分要素が 1 つしかないため、このルーチンは結果を提供していません。
2.3.4) RF = M /( QTY(1:R) の合計) によって精製係数を計算します。
2.3.5) L(1) = L(0)/ RF によって正方形の辺の新しい長さを計算します。
2.3.6) L(i) > 0 の場合、2) から再ループします。
3) 休憩の後、改善のための分断と衝動
3.1) グリッドの各行について、行全体を約半分の長さで左右にずらし、効率を計算して、どちらが優れているかを判断します。次に、試して検証した量の線をシフトし、1/4 辺の長さで左右を選択し、前のステップよりも効率が低くなるまで繰り返します。
注: この最後の分割とインペラ セクションは、各部分要素に O と 1 の間の重みを付けた場合にのみ適用されます。部分的なカバー要素を完全なカバー要素と見なす場合、これは改善を提供しません。
最終的な注意: RF に倍率を適用できることを考慮してください。たとえば、最初のパッセージでは、倍率によって RF = M が得られ、制約からすぐに解放される可能性があります。通常の要素数が 100 ～ 1000 要素またはそれ以上の範囲である場合は、RF > 2 を取得するたびに RF に係数 0.8 を適用できます。
FINAL NOTE 2: 四角形がすべて同じ長さでなければならないという制約を取り除くことができれば、はるかに簡単になり、何よりも、境界に近づくだけで洗練されるため、はるかに高速になります。
これが公式ではない場合は申し訳ありませんが、計算分析から取得できる複雑なメッシュアルゴリズムを回避できる最速の要素の 1 つだと思います。また、珍しい表記で申し訳ありません。私は自分自身を説明するために最善を尽くしました.私は標準的な表記法に慣れていません.