方向別grid scanによる長距離効果の前計算
各行・各列を効果の向きにscanし、最後のblockerまたはactive emitterだけを保って、直線状に続く監視・照射・到達禁止効果を全体線形時間で印付ける。
この典型を扱う単元: 方向別grid scanによる長距離効果の前計算
検索別名: directional grid scan、ray sweep、四方向scan、方向別グリッド走査
未知問からこの典型を見つける手掛かり
- 扱う対象
- affected cells
- blocker
- directed emitter
- grid rows and columns
- 使う手掛かり
- rayを個別に伸ばすと二乗
- 方向種類が定数個
- 直線効果がblockerまで続く
- 保つ不変量
- blocker属性と禁止属性の分離
- 各cellを定数回処理
- 現在activeな方向
- 求めるもの
- 全効果領域の線形時間marking
- 後段探索の静的障害化
- 適用しない条件
- 効果の向きが状態ごとに変わるray tracing
- 単なる全cell走査
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- event・値順のオフライン走査: 順序に沿って進みながら少数のactive状態だけを更新する発想は共通する。一方、固定方向scanにはeventのsort・追加・削除がなく、event sweepそのものとは区別する。
学習成果と学習単位
各行・各列でactiveな向きだけを更新し、blockerと通行禁止条件を混同せず、定数方向へ伸びる全効果領域をgrid全体の線形時間で印付けられる。
方向別grid scanによる長距離効果の前計算で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。