計算幾何の基礎と領域探索 の編集履歴

nishikawa が 2015-07-25 16:20 に編集

--- Ver.3	2015-07-25 11:32:12+09:00
+++ Ver.4	2015-07-25 16:20:41+09:00
@@ -14,7 +14,7 @@
 
 # 図形の定義
 
-今回扱う図形は平面上の幾何学的図形とします。今回扱う図形、点、線分、多角形を以下のように定義します:
+今回扱う図形は平面上の幾何学的図形とします。今回は点、線分、多角形を以下のように定義します:
 
 ```c++
 // 点
@@ -114,7 +114,7 @@
 y = (a2*c1 - a1*c2) / (a1*b2 - a2*b1)
 ```
 
-が得られます。どちらの分母は共通です。この分母が 0 のとき、2 直線は平行であり、交点は存在しません。これを踏まえてプログラムに落とせば、
+が得られます。どちらの分母は共通です。この分母が 0 のとき、2 直線は平行であり、交点は存在しません。また、2 直線が完全に重なる場合も分母が 0 になります。今回はこれも平行と同じように扱うことにします。これを踏まえてプログラムに落とせば、
 
 ```c++
 bool intersection_point(line l1, line l2, point* p) {
@@ -189,6 +189,8 @@
 これでようやく所望のプログラムを得ることができました。当初の発想としては直感的な方法を採ったつもりが、このように複雑な実装が必要になってしまいました。こういった点が幾何学的アルゴリズムの難しい点であると言えます。
 
 ちなみにこのプログラム、 `intersection_point` 関数で求める 2 直線の交点を求めた結果を整数にしているので、正確な交点を求めることができていません。つまり、少なくともこの方法では、点の X, Y 座標を整数で持つことはできません。
+
+また、 `intersection_point` 関数に完全に一致する 2 直線を渡した場合、正確な交点を求めることができないため、`FALSE` を返しています。本来であれば、同関数から `FALSE` が返ってきた場合でも、平行する 2 線分が交わるかどうかの例外処理を組む必要があるでしょう。
 
 ## 第二の解
 
@@ -232,15 +234,15 @@
 
 という判定文が得られます。
 
-傾きが等しいとき、3 点は反時計回りでも時計回りでもなく、直線上に存在します。 `ccw` 関数の基本的な使われ方として、線分上の両端点を第一、第二引数とし、線分とは別の点を第三引数とし、三点の位置関係を調べるというものがあります。ここではそのような使い方を前提として、線分 A と線分 B が重なるかどうかを境界として、重なるときは `0` 以下の数値, 重ならないときは正の数値を返すようにします。
-
-まず `p0` が線分B上にあるとき `-1` を返すことにします。
+傾きが等しいとき、3 点は反時計回りでも時計回りでもなく、直線上に存在します。 `ccw` 関数の基本的な使われ方として、線分上の両端点を第一、第二引数とし、線分とは別の点を第三引数とし、三点の位置関係を調べるというものがあります。ここではそのような使い方を前提として 3 値のとり方を考えます。`p1` から `p2` を結ぶ線分を線分 C とし、線分 A と線分 C が重なるかどうかを境界として、重なるときは `0` 以下の数値, 重ならないときは正の数値を返すようにします。
+
+まず `p0` が `p1` と `p2` の間にあるとき `-1` を返すことにします。
 
 ```c++
 if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
 ```
 
-`p0` が線分 B 上にあれば、線分 A と線分 B は重なります。このとき `dx1`, `dx2` または `dy1`, `dy2` の符号が異なるはずですので、それを利用して判定します。
+`p0` が `p1` と `p2` の間にあれば、線分 A と線分 C は重なります。このとき `dx1`, `dx2` または `dy1`, `dy2` の符号が異なるはずですので、それを利用して判定します。
 
 次に `p2` が線分 A の延長線上にあるとき `+1` を返すことにします。
 
@@ -278,7 +280,6 @@
  3. 2 で求めた角度が小さい順に並べる
 
 `dx` を 2 点の水平方向の距離、`dy` を 2 点の垂直方向の距離とするとき、基準点と各点とを結んだ線分がなす角度は、逆正接関数 (atan) を用いて次のように求めることができます。C の標準関数だと、 `atan2` 関数がより使いやすいので、今回はこちらを利用します:
-
 
 ```c++
 atan2(dy, dx)
@@ -342,7 +343,7 @@
 
 ここでもやはり考慮すべき例外があります。テスト線分が多角形の辺を含む場合です。
 
-上の図において、例外を考慮せずにテスト線分が多角形の点のちょうど上を通る場合も交点の数を 1 とすると、交点の数は 4、つまり偶数となります。しかし図を見れば点が多角形に含まれていることは明らかであり、やはり例外を考慮する必要性があることが分かります。
+図中の 3 において、例外を考慮せずにテスト線分が多角形の点のちょうど上を通る場合も交点の数を 1 とすると、交点の数は 4、つまり偶数となります。しかし図を見れば点が多角形に含まれていることは明らかです。また、図中の 4 はその逆が成り立ちます。やはり例外を考慮する必要性があることが分かります。
 
 この例外を考慮して、テスト線分が多角形の点のちょうど上を通るとき、交点の数を 1 とするか 0 とするかを場合分けする必要があります。
 
@@ -384,7 +385,7 @@
 
 基本ルートは (1) と (2) の両条件を満たした場合です。つまり、多角形の頂点がテスト線分上にない場合です。多角形の各辺とテスト線分とが交差するかどうかを判定し、交差していれば交点の数 `count` を `+1` します。
 
-例外ルートを考えます。(1) の条件を満たさない場合、頂点 `p[i]` はテスト線分上にあると判定できます。その場合には `j` を更新せずに次の頂点を調べます。このように `j` を更新しなかった後で (1) の条件を満たすと、(2) の条件を満たさず、else 節に入ります。多角形の頂点 `p[i]` と `p[j]` はどちらもテスト線分上に存在しない点です。この両点がテスト線分の両側に位置するときにのみ、交点の数を +1 します。
+例外ルートを考えます。(1) の条件を満たさない場合、頂点 `p[i]` はテスト線分上にあると判定できます。その場合には `j` を更新せずに次の頂点を調べます。このように `j` を更新しなかった後で (1) の条件を満たすと、(2) の条件を満たさず、(3) の処理に流れます。(3) では `p[i]` と `p[j]` についてテスト線分との `ccw` を取っています。`p[i]` と `p[j]` はいずれもテスト線分上に存在しない点であり、これらがテスト線分の両側に位置するときのみ、交点の数を `+1` します。
 
 この解では、与えられる多角形 `poly` の頂点が反時計回りに並んでおり、かつ `poly[0]` が、全頂点のうち Y 座標がもっとも小さく、かつその内でもっとも X 座標がもっとも小さい点をであることを前提としています。
 
@@ -410,7 +411,7 @@
 
 長方形は左下と右上の頂点座標で表現します。`x1`, `y1` は左下の頂点の X 座標と Y 座標を、`x2` と `y2` は右上の頂点の X 座標と Y 座標を持つものとします。点の X 座標と Y 座標の両方が、長方形の上下左右の X 座標、Y 座標の範囲内におさまっているかどうかをしています。至って自明なプログラムです。
 
-一般的な多角形の場合と比べると、ずいぶん簡単なプログラムになりました。長方形は一般的な多角形に比べて極めて単純であるため扱う例外の数が少ないため、このように単純なプログラムに落としこむことができます。
+一般的な多角形の場合と比べると、ずいぶん簡単なプログラムになりました。長方形は一般的な多角形に比べて極めて単純であり扱う例外の数が少ないため、このように単純なプログラムに落としこむことができます。
 
 # 領域探索
 
@@ -485,6 +486,8 @@
 ```
 
 と導くことができます。 `座標の最大値` とは、すべての点の X および Y 座標のうち、もっとも大きい数値のことを指します。平面の座標空間が広くなければ、平面の縦幅、横幅のうち長いほうを採用するという方法で選んでもいいかもしれません。 `N` は問題により与えられる値であり、 `G`, `S` は上記の式から導くことができました。 `M` は自分で適当な値を決める必要があるでしょう。
+
+以下のプログラムでは、`G` および `S` があらかじめ定数として定義されていると仮定しています:
 
 ```c++
 class Range {
@@ -561,7 +564,7 @@
  2. 点 B を木に追加します。第二階層を X 座標で分かつため、垂直方向に直線を引きます。このとき点 A の Y 座標より上側については気にしません
  3. 点 C を木に追加します。第三階層を Y 座標で分かつため、水平方向に直線を引きます。このとき点 B の X 座標より右側については気にしません
  4. 点 D を木に追加します。第二階層を X 座標で分かつため、垂直方向に直線を引きます。このとき点 A の Y 座標より下側については気にしません
- 5. 点 E を木に追加します。第三階層を Y 座標で分かつため、水平方向に直線を惹きます。このとき点 D の X 座標より左側については気にしません
+ 5. 点 E を木に追加します。第三階層を Y 座標で分かつため、水平方向に直線を引きます。このとき点 D の X 座標より左側については気にしません
 
 こうしたプロセスを得て構築された 2D 木は、次のようになります:
 
@@ -586,7 +589,7 @@
   int search(rect range);
 
 private:
-  int search_r(node* n; rect range, int d);
+  int search_r(node* t, rect range, int d);
 };
 
 Range::Range() {
@@ -624,7 +627,7 @@
   return search_r(head->r, range, 1);
 }
 
-int Range::search_r(node* n, rect range, int d) {
+int Range::search_r(node* t, rect range, int d) {
   if (t == z)
     return 0;
 

nishikawa が 2015-07-25 11:32 に編集

--- Ver.2	2015-07-25 11:29:20+09:00
+++ Ver.3	2015-07-25 11:32:12+09:00
@@ -579,7 +579,6 @@
     node *l, *r;
   };
   node *z, *head;
-  point dummy;
 
 public:
   Range();

nishikawa が 2015-07-25 11:29 に編集

--- Ver.1	2015-07-25 11:23:49+09:00
+++ Ver.2	2015-07-25 11:29:20+09:00
@@ -394,8 +394,6 @@
 
 先の問題では、与えられた点が任意の数の頂点を持つ多角形に含まれているかどうかを判定しました。このような一般的な多角形ではなく、長方形のようなより単純で特徴のある多角形であれば、より単純な実装方法が考えられます。
 
-長方形の頂点を反時計回りにめぐりつつ、各辺の端点と質問点で `ccw` 関数を評価し、4 辺すべてで `ccw` 関数の結果が反時計回りであれば、点は長方形の中に含まれていると判定できます。
-
 ```c++
 // 長方形
 struct rect {
@@ -403,20 +401,16 @@
 };
 
 bool insiderect(point t, rect r) {
-  point lb = { r.x1, r.y1 };
-  point rb = { r.x2, r.y1 };
-  point rt = { r.x2, r.y2 };
-  point lt = { r.x1, r.y2 };
-  return ccw(lb, rb, t) <= 0
-      && ccw(rb, rt, t) <= 0
-      && ccw(rt, lt, t) <= 0
-      && ccw(lt, lb, t) <= 0;
-}
-```
-
-長方形は左下と右上の頂点座標で表現します。`x1`, `y1` は左下の頂点の X 座標と Y 座標を、`x2` と `y2` は右上の頂点の X 座標と Y 座標を持つものとします。これらの座標から左下、右下、右上、左上の頂点を得て、頂点を反時計回りにめぐりながら、与えられた点との位置関係を `ccw` 関数で調べます。
-
-一般的な多角形の場合と比べると、ずいぶん簡単なプログラムになりました。長方形は一般的な多角形に比べて極めて単純であるため扱う例外の数が少なく、かつ `ccw` 関数のようなよく練られた関数を使っていることにより、このように単純なプログラムに落としこむことができます。
+  return p.x >= r.x1
+      && p.x <= r.x2
+      && p.y >= r.y1
+      && p.y <= r.y2;
+}
+```
+
+長方形は左下と右上の頂点座標で表現します。`x1`, `y1` は左下の頂点の X 座標と Y 座標を、`x2` と `y2` は右上の頂点の X 座標と Y 座標を持つものとします。点の X 座標と Y 座標の両方が、長方形の上下左右の X 座標、Y 座標の範囲内におさまっているかどうかをしています。至って自明なプログラムです。
+
+一般的な多角形の場合と比べると、ずいぶん簡単なプログラムになりました。長方形は一般的な多角形に比べて極めて単純であるため扱う例外の数が少ないため、このように単純なプログラムに落としこむことができます。
 
 # 領域探索
 

nishikawa が 2015-07-09 23:51 に投稿