想像と推論とだろう運転でひらたく構築されたCyrus–Beck algorithm

考え方

凸ポリゴンは半平面の積集合からなる。
ゆえに入力されたN次元直線を半平面で連続的にクリッピングすると、凸ポリゴンでクリッピングしたのと同じことになる。

２次元的にひらたく言うと

ある２次元線分を２次元閉凸多角形で切断（クリッピング）したい。

２次元凸ポリゴンこと２次元閉凸多角形は半平面の積集合からなる。

２次元平面における半平面は２次元平面上の直線によって区切られた２次元空間の半分。直線とは両端のないもので、両端があるものは線分である。

２次元凸ポリゴンを構成する辺の両端を無限に伸ばした直線を考え、これでもって入力された線分を切断したおせば２次元凸ポリゴンでクリッピングしたのと同じことになる。

Cyrus–Beck algorithmの場合、３次元空間中の凸立方体でもって３次元直線をクリッピングすることも考えることができるため、半平面だの超平面だのの言葉を用いて一般化しているのだと思われる。

凸ポリゴン（凸多角形（凸包））とはなにか

ポリゴンの内部に点を２つとって線分を構築すると考える。その時、いかなる２点をとっても線分がポリゴンから外にでないなら、そのポリゴンは凸である。

凸である。

凸でない。

２点の取り方によっては、その２点が構築する線分はポリゴンの外にはみでる。

半平面とは何か

超平面で空間を切断した時の空間の片割れ。超平面上も含むと思われる。
２次元では、２次元平面を直線で分断した時の片方の平面であり、おそらく直線上も含む。

超平面とは何か

２次元なら直線。３次元なら平面。N次元ならN-1次元のやつ。

凸ポリゴンを構成する頂点から見た半平面を数式で表すと

ただしこの定義は法線の向きや、ポリゴンの頂点の向きなどの定義にもよる。

ここでは法線は凸ポリゴンの外に向くことを前提としている。また、凸ポリゴンの頂点はディスプレイ座標において時計回りに並ぶことを前提にしている。

この時、Qは関数の引数であり、空間中のすべての点を入力として受ける。
２次元的には下図参照。この図においてひらたく言うと、法線の裏にある点全部集めた平面がこの場合の半平面。

半平面の式の小なり記号を＝にすると以下のようになって

２次元の場合、これは凸ポリゴンの辺の両端を無限に伸ばした直線の方程式に他ならない（３次元の場合は平面の方程式）。
ひらたく言うと、法線に直交する点全部。法線と内積とってゼロになる点全部。

この法線を用いた直線の式に対してクリッピング対象線分を成す直線の方程式

これは法線用いた直線方程式とは別角度の、t値を用いたパラメトリックな直線方程式で、0<=t<=1ならば線分上の１点を示す便利なやつであるが、これを法線のほうのQに叩き込むと

となって、tについて解くと、クリッピング対象入力線分の始点と、線分のt倍したやつの和が直線と直線の交点を示す。（３次元なら平面と直線の交点）

２次元平面上の直線の交点は２次元疑似外積を用いても求めることができるが、多分Ｎ次元への拡張性を考えて内積を使っているのだと思われる。

交点を求めたり内積外積で位置を判定したりなんだりはこちら。

ところで、古来ユークリッドより、直線というのはひねくれて考えない限り、平行でなければいずれどっかしらで交差する。（下図の入力線分の矢印は線分の向きではなく、矢印の先の方で交差するの意）

このことを用いてt値で入力線分を詰めていく。詰め方には場合分けが必要。

アルゴリズム的には

入力線分と半平面の境界が平行の場合
入力線分が半平面に完全に含まれる場合→入力線分をそのまま返す。
入力線分が半平面にまったく含まれていない場合→ゼロなりnullなり空集合なりを返す。

入力線分が半平面に突入する場合→入力線分の始点をt位置に詰める。

入力線分が半平面から離脱する場合→入力線分の終点をt位置に詰める。

プログラム的には

t値式の分母、法線と線分の内積

を用いて

＝０の場合->入力線分と半平面の境界が平行。
＜０の場合、上式が負値の場合->ポリゴンの外を向く法線と入力線分が逆向き＝入力線分が半平面に突入する。
＞０の場合、上式が正値の場合->ポリゴンの外を向く法線と入力線分が同じ向き＝入力線分が半平面から離脱する。

t値とt値式の分母である位置判定は別なことに注意。

突入線分のt値と0の最大値をとる。
突入線分の始点を詰める。t値が負値ならばポリゴンの辺からなる直線は入力線分の裏側で線分と交差する。つまり半平面は線分を切らんで良い。t値がプラスなら線分は始点より先でポリゴン辺と交差している。つまり半平面でもって線分を切るべき。

離脱線分のt値と1の最小値をとる。
突入の逆。

ただしここに記述してあるすべてのことは実際に実装しておらんため間違っている可能性があります。