レコードの並べ替え(Sort)(管理)の仕組み

[レコードの並べ替え(Sort)] ツールで大切なのは、フィーチャを空間的に並べ替える機能です。空間的に並べ替えると、空間またはジオメトリック処理の効率が高まります。

フィーチャを空間的(つまり場所によって)並べ替えるには、[フィールド] パラメータで [形状] を選択する必要があります。[形状] フィールドを選択すると、[空間的な並べ替え方法] パラメータが有効になり、5 つのドロップダウン オプションの中から並べ替えのアルゴリズムを設定できます。これらのオプションは、UL、UR、LL、LR、PEANO です。

UL、UR、LL、LR を使用した空間的な並べ替え

最初の 4 つのオプションは、並べ替えの開始ポイントの略語で、たとえば、UR は右上(Upper Right)、LR は左下(Lower Left)です。これらのオプションは、プロッタやプリンタのようにフィーチャをスキャンします。UR オプションを選択した場合、右上からスキャンが開始され、一番上のフィーチャが最初に選択されます。上から下に移動するとき、複数のフィーチャが同じ水平ラインにあった場合、右から左の順序になります。スキャンは、反対方向(この場合は左下)に到達するまで、下および左方向に続けられます。フィーチャは、スキャンの移動方向と同じ順序に並べ替えられます(DESCENDING が選択された場合は反対の順序になります)。

UR 並べ替えオプションは、入力として均一に分散されたポイントのセットを考えるとわかりやすくなります。

UR オプションを使用した空間的な並べ替え

上の図の数字は、UR オプションで並べ替えられる順序を表しています。LL オプションが選択された場合、フィーチャの順序は逆になります。

上と右の順序設定の仕組みを示した簡単な例を以下に示します。

上と右を区別する並べ替えの図

U(上)は R(右)に優先することに注意してください。R(右)は、複数のフィーチャが同じ水平レベルにある場合のみ考慮されます。

PEANO による空間的な並べ替え

PEANO オプションは、ペアノ曲線アルゴリズムを使用します。このアルゴリズムは、小さな近傍のすべての場所を検索してから、次の近傍へ移動します。そのため、隣接した場所は曲線(またはパス)上で近くなります。範囲全体を検索する代わりに、小さな近傍を 1 つずつ検索し、大きな領域(5 ~ 8 の小さな近傍)が完了したら、別の大きな領域に移動し、その領域内にある小さな近傍で並べ替えを再開します。

PEANO による並べ替えの図

上の図では、スキャンの順序が矢印で示されています。4 つの四角形の近傍は、個別にスキャンされています。領域がこれより大きければ、この検索は別の近傍に対して続行されます。ポイントの密度がこれより高い場合は、より小さな近傍が検索されます。

空間を埋め尽くす曲線アルゴリズムの利点は次のとおりです。これは高速で、場所間の距離を計算する必要がなく、並列処理が可能です。このアルゴリズムの応用としては、巡回セールスマン問題、ルート システムの構築、およびマップ描画の際のペンプロッタの制御などが挙げられます。

7/28/2014