平面幾何におけるベクトル演算
ここでは，ACM/ICPC頻出の平面幾何について，基本的なベクトル演算を解説します。 最後にライブラリとしてソースコードを載せているので本番では印刷して持っておくとよいでしょう。 ベクトルの基礎 デカルト座標系とユークリッド空間 スカラーとベクトル 点とベクトル ベクトルの和と差 ベクトルの利用 complex型の導入 絶対値，2点間の距離，単位ベクトル 法線ベクトル，単位法線ベクトル 内積と外積 内積・外積 2直線の直交判定・平行判定 点が線上にあるかないかの判定 直線と線分 直線と点の距離 線分と点の距離 線分の交差判定 線分の交点計算 直線の交点計算 ソースコード $Id: index.shtml 1825 2007-09-23 00:35:10Z SYSTEM $
平面幾何におけるベクトル演算 » 直線と線分
で求まります（ここで |x×y| は実数に対する絶対値， |x| はベクトルに対する絶対値と「絶対値」の意味が異なっている点に注意してください）。 コーディングは以下の通りです*1： // 点a,bを通る直線と点cとの距離 double distance_l_p(P a, P b, P c) { return abs(cross(b-a, c-a)) / abs(b-a); } 線分と点の距離 今度は線分と点の距離を考えてみましょう。 距離としてどのような値が欲しいのか，というのは問題依存なのですが， ここでは一般的な距離の定義に従って，点から「線分のどこか」への最短距離としてみます。 そうすると，線分 ab に垂直な直線で点 a を通る直線と点 b を通る直線に囲まれた領域（下図の左の赤色領域に相当）にある点であれば， 点から直線 ab への垂線が最短距離になります。 また，点 c がこ
気まぐれな戯れ言の部屋 バックナンバー９
各辺の内側判定による内外判定 前回の所で、外積を用いて直線の左側・右側を判定する手法を紹介しました。 これを利用して点の内外判定を行います。 例えば、下のような例を考えるとわかりやすいかと思います。 左の三角形の辺を、AB、BC、CAと右回りになるように辺を見ていきます。 三角形の中の点Pは、各辺の常に右側にあることがわかります。 点QはBC、CAの右側になってはいますが、ABの左側にあります。 逆にAC、CB、BAと左向きに回ったときは点Pは常に左側にあります。 要は、「辺をぐるっと回った時、常に点が同じ側にある→多角形の内側にある」と言うことが出来ます。 左の図の例では、点Pは右回りに辺を回った時常に右側にあります。 右回りに回った時に常に左側にある、と言う事はありえません。 上の図を見て、右回りに回った時常に左側に来るという領域は存在しない事がわかります。 そのため、実際は辺を左回り
月の杜工房 - ポリゴンに対する内外の判定
ある点がポリゴンの中にあるかどうかを調べるには、ポリゴンに対して十分に離れている点とその点を結んだ直線がポリゴンの辺と何回交差したかを調べ、偶数回であれば外、奇数回であれば内側にあると判断できます。 ２つの線分が交差するかどうかを調べるには、一方の線分の２点ともう一方の線分の頂点との回り方向を調べ、異なる回りであれば交差すると判断できます。 ３点が時計回りか反時計回りかを調べるには以下のようにします。 p1；(x1,y1)、p2；（x2,y2）、p3；（x3,y3）とすると、 (x2-x1)*(y3-y1)と(x3-x1)*(y2-y1)を比較して、負なら反時計回り、正なら時計回り、等しければ直線になります。 ただし、ポリゴンの内外を判定するときに判定の対象となる点と十分に遠い点の直線上にポリゴンの頂点がある場合の取り扱いに注意が必要です。 //３点が時計回りかどうかを調べる //時計回り
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
