幾何の基本判定と座標変換

概要

幾何の基本判定・配置・座標変換

交差・方向・距離・接触条件を、外積、端点順、格子占有または変換後座標の局所判定にする。

考え方

向きは二つのベクトルの外積、角度の大小は半平面と外積、射影は内積で表す。向きの符号から交差条件を導けば、atan2や平方根を使わず幾何条件を比較できる。平行・共線は別の境界として扱う。

平面ベクトルa=(a_x,a_y),bについてcross(a,b)=a_x b_y−a_y b_x、dot(a,b)=a_x b_x+a_y b_y。三点P,Q,Rの向きはcross(Q−P,R−P)の符号で、正なら反時計回り、0なら共線となる。

閉線分PQとRSの交差は、R,Sが直線PQの同じ側に厳密にはなく、P,Qも直線RSの同じ側に厳密にはないことに、x,y両軸のbounding intervalが重なる条件を加えて判定する。符号の積を使わず符号比較すればさらに大きい積を作らず済む。共線では前者だけが常に真なので後者が重なりを決め、長さ0の線分と端点接触も含められる。

非零ベクトルの偏角sortは、上半平面(y>0またはy=0,x≥0)を先にし、同じ半平面ではcross(a,b)>0をa<bとする。同方向を区別するなら長さやIDでtieを決める。原点ベクトルは角度が未定義なので先に分ける。射影の係数はdot(X−P,Q−P)/dot(Q−P,Q−P)で、線分への最近点なら[0,1]へclampする。P=Qは点との距離で処理する。距離の大小だけなら二乗を使える。

座標u=x+y,v=x−yでは |Δx|+|Δy|=max(|Δu|,|Δv|)。符号が同じ場合は和、異なる場合は差の絶対値が左辺になることから証明できる。逆変換x=(u+v)/2,y=(u−v)/2に戻す際はu,vのparityが同じという整数格子条件も残す。

射影で落とした座標も検査する

3D直線を平面へ射影して得た交点は、元の交点の候補に過ぎない。二直線の残りの座標が違えば、ねじれの位置である。また射影した二直線が重なっていても、3Dでは平行な場合と一点で交わる場合がある。射影の退化を分け、元の全座標の式を同時に確認する。

方向のx成分が非零なら、直線はy=ax+b,z=cx+dで一意に表せる。有理数の分母を正、分子・分母を互いに素、0を0/1にして、四係数を一致判定のキーにできる。二直線のaが違えばyの式からxを求めzを確認、aが同じでcが違えばzからxを求めyを確認する。両傾きが同じなら切片も同じ場合だけ一致、違えば平行である。ABC301 Gでは有効な全直線がこの条件を満たすので、交点の有理数キーまで具体化できる。一般の3D直線でx成分が0なら、別の媒介座標またはベクトルによる式が必要となる。

成立条件と計算量

一つの判定は固定長の算術ならO(1)。座標の最大値から外積の型を選び、差を取る前のoverflowにも注意する。浮動小数点では誤差のスケールを考え、epsilon付き比較をそのままsortの比較関数にしない。

下位単元

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。外積・端点順・座標変換を用い、退化ケースを含む位置関係を判定する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 幾何・凸最適化。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-geometry-primitives

習得する技能

  • 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: 凸包・支持方向・境界候補、円環順序・chord交差、半平面制約・凸領域の共通部分。

座標と外積・距離式で向きや交差を代数判定し、凸幾何へ進む前提を作る。

このUnitでは扱わないもの

  • 凸包の境界候補列挙・半平面交差。

根拠