点位置決定問題

を、高速に求めましょうという問題。

総当たり

ポリゴン数をN、1ポリゴン当たりの平均辺数をMとしたとき、$O(NM)$になる。
N=10000、M=100くらいならやってやれなくは無い。

ポリゴンごとに、バウンディングボックス（自身をぴったり覆う、辺がXY軸に平行な矩形）を事前計算
- 点がその矩形に入っていないなら、当然ポリゴンにも入っていない
まず矩形との内外判定を行う。これは単なる数値比較で済む
矩形に入っていたらポリゴンの内外判定を行う

最悪オーダーは$O(NM)$のまま。
例えば使用前の蚊取り線香のように渦巻きが互いに組み合わさった図形など、どのポリゴンもバウンディングボックスが大きくて絞れない、というようなケースも作れるため、万能ではない。

市区町村のような地理的境界など、まぁ、あまりそういう変なことになってない自然界の多数のケースでは、実装が単純でそれなりに有効。

「単純な高速化」でも、とりあえず全ポリゴンのバウンディングボックスとの内包関係は調べなくてはいけないが、ポリゴン数が多い場合、無駄が多い。

二分木・四分木を事前に構築しておくと、1つの点クエリの応答時間は速くなる。
ただし「単純な高速化」と同様、ある程度“自然”な分布である場合に有効であり、バウンディングボックスが大きいポリゴンが多くを占める場合は効果が薄い（むしろ余計な計算が増えるので悪化する）。

ここでの二分木・四分木とは、全領域を表すノードを根とし、空間を分割しながら子をたどっていくデータ構造である。

二分木を例に取ると、ノード $u$ から、$x=k$ の線で分割した領域を2つの子 $v,w$ にするとしたとき、バウンディングボックスがこの線にまたがるポリゴンを $u$ に登録しておく。

クエリでは、点 $(x,y)$ が含まれる領域を表すノードを上から辿っていき、辿ったノード中に登録されていたポリゴンが、点を含んでいる可能性のあるポリゴンである。

これにより、離れたポリゴンは、そもそもバウンディングボックスとの内包関係すら調べなくてよくなる。

ただ、根に近いノードを分割するときは多くのポリゴンをまたいでしまい、登録数が多くなりやすい。
登録するのが「点」である場合、階層が深くなりにくい四分木がよく使われるが、バウンディングボックスのような「領域」を登録する場合、この観点から、二分木の方が不要にまたぐポリゴン数をなるべく抑えられるかな。

ノード毎に分割する線を決める方法としては、ポリゴンがだいたい均等に分布するなら、単純に領域を半分ずつに区切っていく実装がやりやすい。

均等でないとか、もう少し効率を突き詰めたければ、「なるべく子に均等に要素が行き渡り、かつ、あまり自身に登録されるポリゴンが多くならない」線を決定するのが望ましい。

Spaghetti Source - 点位置決定 (スラブ地図)
http://i-health.u-aizu.ac.jp/CompuGeo/2017/handouts/chapter5/Chapter5S.pdf
全てのポリゴン頂点の $x$ 座標で、空間をぶった切る
できた縦に細長い領域を「スラブ」と呼ぶ
スラブ内にあるポリゴン境界の線を列挙する
- スラブ内に交点は存在しないので、この線たちの上下関係は左端から右端まで変わらない
点 $(x_i,y_i)$ が与えられたとき、まず $x_i$ で二分探索によりスラブを特定する
- そのスラブで、$y_i$ が属する線の間を二分探索で特定する
- 線の間の領域が元々属していたポリゴンを取得する

上記は最悪ケースの計算量だが、“自然”なケースでは計算時間・空間量はそこまで大きくならず、実装が比較的単純で有効な方法となる。

たとえば $\frac{P}{2}$ 個の点が左に、$\frac{P}{2}$ 個の点が右に（少しずつ $x$ 座標が変わりながら）あって多数のポリゴンが層状になっている場合、 $O(P)$ 個のスラブそれぞれに、平均して $O(P)$ 個の線が存在することになってしまい、計算時間がかかる。

N. Sarnak and R.E. Tarjan, “Planar Point Location Using Persistent-Search Trees,” Communications of the ACM, 29 (1986), 669-679.

スラブ法の改良？全部を持たず、赤黒木で更新していくらしい。