典型タグ

方向別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そのものとは区別する。

    学習成果と学習単位

    代表問題

    この典型の考え方を具体的な問題で確かめるための入口です。

    関連問題

    この典型が主タグまたは補助タグとして付いている問題です。