線分集合の交点列挙： Bentley-Ottmann のやり方
今回は、線分集合の交点列挙について Bentley-Ottmann のやり方を調べたので、そのメモです。よろしくお願いします。 現在、気が向いたときに平面性テストのデバッグをしているのですけど、ある平面描画に対して、辺対の交差チェックができたら良いなぁって思っていました。そもそも、いまのところ、ちっちゃいグラフが対象なので、\(O(n^2)\) で良いし、無理する必要なかったのですけど、軽い気持ちで Bentley-Ottmann のやり方に着手してしまいました。 まだ、きちんとテストしきれてないので、バグバグだと思いますけど、際どい境界条件とかじゃない限り動いていそうなので「モウイヤニナッタヨ」で切り上げました。よろしくお願いします。 python コード 今回のもやっぱり未完成で暫定的なものですけど、github に置きました。参考になるとは思いませんけど、もし腹が立ったら、ごめんあそ
凸包の頂点数の話 - notブログ
まとめ のグリッドに収まる格子点を頂点とする凸多角形の頂点数は。 詳しい話は論文を読んでください。 On the maximal number of edges of convex digital polygons included into an m × m-grid はじめに 凸包を取ると考慮すべき点の数が減って嬉しい、という問題が競プロでたまに出題されます。 この類の問題の解説で頂点数のオーダーがと書いてあることがある*1のですが、実際はだよという話です。*2 方針 頂点数を大きくするにはマンハッタン距離が短い辺から使うのが最適です。 マンハッタン距離が以下の辺を使うと、頂点数がの凸多角形がのグリッドに収まります。 計算 めんどうなので、成分が正の部分だけ考えます。*3 そうすると使う辺は(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...となります。 これ
点の集合を包含する球
IPSJ Magazine Vol.43 No.9 Sep. 2002 1009 点の集合を包含する球 ishihata@cs.meiji.ac.jp 3 (x1, y1), (x2, y2), (x3, y3) S = � � (y3y1)(x2x1)(y2y1)(x3x1) (y3y1)(x2x1) (y2y1)(x3x1) 3 1 2 3 (convex hull) 1 3 2001 11 H ■幾何の問題に関する一般論 1 1 2 20% 2 3 3 x-y 3 2 43 9 2002 9 1010 1 ■問題：点の集合を包含する球 3 n n 4 30 x-y-z x y z 0 100 0.01 5 0.00001 6 10 7 typedef struct { double x, y, z; } pos; int n; pos point[30]; p
Codeforces Round #339 (Div. 1) A. Peter and Snow Blower - pekempey's blog
※問題をエスパーしたので問題を勘違いしています。 問題文 codeforces.com 問題概要 点P と 多角形 S が与えられる。 点 P を中心とした円を 2 つ描き、多角形 S がその円の間に挟まれるようにする。 この 2 つの円に囲まれる領域の面積の最小値を求めよ。 解法 点と多角形の距離の最小値・最大値を求めれば面積の最小値が求められる。 点と多角形の距離の最小値は、点と多角形のそれぞれの辺の距離の最小値になる。 そのため、点と線分の距離を求めたい。 点と線分の距離は、点が緑色の領域内部にあるかどうかで求め方が変わる。 以降、直線の単位方向ベクトルを $d=(q-p)/|q-p|$ とする。 緑色の領域の内部にある場合 図でいうと r1 がこのケースになる。これは点と直線の距離を求めればいい。 点と直線の距離は外積を用いて、 $$ | d \times (r-p) | $$ で
正射影ベクトルの公式の証明と使い方 | 高校数学の美しい物語
物に光を当てたときにできる像を射影と言います。点光源を考える（点射影）ことも平行光線（無限遠点に光源があるとみなせる）を考えることもあります。特に，スクリーンに垂直な光線による射影を正射影と言います。 この記事ではベクトルを直線に射影したものを考えます。ベクトル aundefined\overrightarrow{a}a が定める直線とは，aundefined\overrightarrow{a}a （に対応する有向線分）を含む（向きのついた）直線 lll のことです。 lll はスクリーンの役割を果たします。例えば薄い青ベクトルの正射影は青いベクトル，薄い赤ベクトルの正射影は赤いベクトルです。 正射影ベクトルの公式は，ベクトル aundefined\overrightarrow{a}a とベクトル bundefined\overrightarrow{b}b が与えられたときに射影したベクト
ボロノイ図を使ってラベルの重なり合いを解消する
画像をクリックすると、デモページに飛びます。 見づらいラベル 地図上に沢山のラベルを並べると、位置によっては重なり合ってとても見ずらくなります。 このラベルの配置位置をボロノイ図を利用して重なり合わないように配置してみます。 母点から中心点へ まず、ポイントを母点としたボロノイ図を描きます。 各ボロノイのセル（ボロノイ領域）の中心点を求め、母点から中心点へのラインを引きました。 ボロノイ領域の中心点は、母点から見て空きスペースの方角となります。 この角度を利用してラベルを配置します。 中心点に向けてラベルを配置 単純にラインに沿う角度でテキストを回転(rotate)させました。 重なり合いは解消されましたが、必ずしも見やすくはありません。 （これはこれで活用方法がありそうですが） ラベル開始位置をずらす 母点からボロノイ領域の中心点の方角へ、ラベルの開始位置を少しずらして配置した例です。
ピックの定理 - Wikipedia
頂点が全て格子点上にある多角形 ピックの定理（-ていり、Pick's theorem）は等間隔に点が存在する平面上にある多角形の面積を求める公式である。この場合の多角形の頂点は全て右図のように、最も近い点同士の間隔を1とする正方格子点（等間隔に配置されている点）上にあり、内部に穴は開いていないものとする。多角形の内部にある格子点の個数を i、辺上にある格子点の個数を b とするとこの種の多角形の面積 S は以下の式で求められる。 例えば図の六角形なら内部にある点が i = 39 個、辺上にある点が b = 14 個なので S = 39 + 14/2 − 1 = 45 と簡単に計算できる。 この定理は 1899 年に ゲオルグ・アレクサンダー・ピックによって初めて示され、エルハート多項式により三次元以上に拡張して一般化することができる。 同公式はまた、多面体上の図形に対して一般化することもで
情報幾何学講義 【チャンネルA】
甘利俊一先生 情報幾何学講義 （チャンネルA) 統計数理研究所 夏期大学院 の講義のうち 甘利俊一先生の担当部分を配信しました。 当分の間、録画を公開する予定です。 投影資料は http://www.ism.ac.jp/shikoin/summer-school/2013.html のリンクからダウンロード可能です。 なお、以下のうち、スマートフォンや一部のタブレットでは1のみしか視聴できません。2,3は配信時にブロードキャスターを使ったためで、これはUSTREAM側の仕様のようです。お手数ですがPC・マックからの視聴をお願いします。 【甘利先生講義１ 午前冒頭】 録画のトラブルで欠けていた最初の部分を別の録画から補充しました。配信技術未熟のため冒頭に空白が、また末尾にループして冒頭がそれぞれ少し入っておりますがご容赦ください。この冒頭部分では講師の表情をとらえることに主眼をおいた撮影をし
三角形の内接円と傍接円 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "三角形の内接円と傍接円" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年5月) 三角形（黒） 内接円（青）と内心(I) 傍接円（オレンジ）と傍心(JA,JB,JC) 内角の二等分線（赤）と外角の二等分線（緑） 初等幾何学において三角形の内接円（ないせつえん、英: incircle / inscribed circle (of a triangle)）とは、その三角形の内部にあり3辺に接する円である。三角形の内部にある円の中で最も面積が大きい円である。内接円の中心を内心（ないしん、incenter）と呼ぶ。 傍接円（ぼうせつえ
.htm)
「ロボットの運動学と力学」
「詳説ロボットの運動学」補足説明１ ロボットの運動解析に必要な数学と力学 ２００８．４．１ １． ベクトル演算 ２． ロボットの運動解析によく使う関数 ３． 剛体の運動 ４． 剛体の静力学 ５． 剛体の動力学 ロボットの運動を論じることは，幾何学的な運動解析をすることと静力学・動力学解析をすることである．ここで述べるのはロボットの解析に必要な基本的なベクトル演算と力学である． ロボットの解析を理解するためにもっと必要なことは専門書を参照して戴きたい． １． ベクトル演算(vector analysis)と図形のベクトル表現 ロボットの運動で扱う数学は３次元ベクトル演算が大半である．ここではベクトル演算の基本を述べる． ３次元ベクトルを (1.1) と置く．ただ
円と円の交点
半径r1 中心(x1,y1) の円と半径r2 中心(x2,y2) の円との交点。 連立方程式による解法 円の方程式は (x-x1)^2+(y-y1)^2-r1^2 = 0 …(1) (x-x2)^2+(y-y2)^2-r2^2 = 0 …(2) (1)-(2): (2 x2-2 x1)x + (2 y2 - 2 y1)y + (x1-x2)(x1+x2)+(y1-2)(y1+y2)-(r1-r2)(r1+r2) = 0 …(3) これは円と円の2つの交点を通る直線になっているので、円と直線の交点の問題に帰着できる。(3)の係数を a = 2(x2-x1) b = 2(y2-y1) c = (x1-x2)(x1+x2)+(y1-y2)(y1+y2)-(r1-r2)(r1+r2) と計算しておくとax+by+c = 0の形になる。 解法 : 直線と円の交点 JavaScript 若干計算量削減
計算幾何学問題「キュラゲの最小包含円を求めよう」の解説記事です！キーワードは「乱択アルゴリズム」 #ゲーム開発 - CodeIQ Blog
CodeIQ中の人、millionsmileです。 出題者のstakemuraさんによる「計算幾何学」問題の解説記事です。 アクションゲームなどでキャラクターを攻撃するとき、ナイーブに１キャラクターごとに１ピクセル単位で処理していたら、計算時間は大変なことになります。さて、どうやったら物理演算を軽くできるのでしょうか？キーワードは「乱択アルゴリズム」です。 ゲーム開発をしている方は必見の記事です。 =============================== 高速化の秘訣は乱数にあり stakemuraです。 先月、「キュラゲの最小包含円を求めよう」というタイトルで、CodeIQでは初となる計算幾何学の問題を寄稿させて頂きました。いきなりの難問だったにも関わらず２４名もの方に挑戦して頂き、中には当方が驚かされるような回答もあったりして、達成感を噛み締めている今日この頃です。さて、挑戦者が
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Matt Dzugan on Twitter: "Typically the voronoi-polygons of Lloyd's Algorithm closely resemble hexagons, but aren't quite perfect. I'm playi… https://t.co/Ssy9pyyeid"
Michael Garland - QSlim 2.0
２円の交点を通る円・直線の方程式
geometry.txt
Mesh Smoothing
Virtual Arena: Room 1680
三角形の面積を外接円の半径を使って求める
Sweep and prune - Wikipedia