線分集合の交点列挙： 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),...となります。 これ
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) | $$ で
ボロノイ図を使ってラベルの重なり合いを解消する
画像をクリックすると、デモページに飛びます。 見づらいラベル 地図上に沢山のラベルを並べると、位置によっては重なり合ってとても見ずらくなります。 このラベルの配置位置をボロノイ図を利用して重なり合わないように配置してみます。 母点から中心点へ まず、ポイントを母点としたボロノイ図を描きます。 各ボロノイのセル（ボロノイ領域）の中心点を求め、母点から中心点へのラインを引きました。 ボロノイ領域の中心点は、母点から見て空きスペースの方角となります。 この角度を利用してラベルを配置します。 中心点に向けてラベルを配置 単純にラインに沿う角度でテキストを回転(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・マックからの視聴をお願いします。 【甘利先生講義１ 午前冒頭】 録画のトラブルで欠けていた最初の部分を別の録画から補充しました。配信技術未熟のため冒頭に空白が、また末尾にループして冒頭がそれぞれ少し入っておりますがご容赦ください。この冒頭部分では講師の表情をとらえることに主眼をおいた撮影をし
.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では初となる計算幾何学の問題を寄稿させて頂きました。いきなりの難問だったにも関わらず２４名もの方に挑戦して頂き、中には当方が驚かされるような回答もあったりして、達成感を噛み締めている今日この頃です。さて、挑戦者が
平面幾何におけるベクトル演算 » 直線と線分
で求まります（ここで |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 がこ
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
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
TTL