線分集合の交点列挙： Bentley-Ottmann のやり方
今回は、線分集合の交点列挙について Bentley-Ottmann のやり方を調べたので、そのメモです。よろしくお願いします。 現在、気が向いたときに平面性テストのデバッグをしているのですけど、ある平面描画に対して、辺対の交差チェックができたら良いなぁって思っていました。そもそも、いまのところ、ちっちゃいグラフが対象なので、\(O(n^2)\) で良いし、無理する必要なかったのですけど、軽い気持ちで Bentley-Ottmann のやり方に着手してしまいました。 まだ、きちんとテストしきれてないので、バグバグだと思いますけど、際どい境界条件とかじゃない限り動いていそうなので「モウイヤニナッタヨ」で切り上げました。よろしくお願いします。 python コード 今回のもやっぱり未完成で暫定的なものですけど、github に置きました。参考になるとは思いませんけど、もし腹が立ったら、ごめんあそ
ポリゴンリダクションの例 [Quadric Error Metric] - ワナビから貴方へ 独り言の吐き溜め：楽天ブログ
2012.09.27 ポリゴンリダクションの例 [Quadric Error Metric] テーマ：今日の理系(395) カテゴリ：理系 最近試してみたポリゴンリダクションの方法は Quadratic Error Metricという手法を使って、元の形の歪みを評価する方法。 http://www.riken.go.jp/lab-www/V-CAD/kokai/No200202.pdf ↑ 元の論文 単純に説明すると ポリゴンリダクションによって移動した頂点の、『元の面からの距離の2乗和』を値とする 当然最初は面上に頂点が載っているわけなので0 頂点数が減少して移動すると、元の面から距離が生じる。 それの2乗の和が最小になるように頂点を移動させていく そうすれば元の形からあまり歪まずに頂点数減らせるよね、って話 具体的にはちょっと数学的になるけれど 一つの面の正規化法線ベクトル（a,b,c
![ポリゴンリダクションの例 [Quadric Error Metric] - ワナビから貴方へ 独り言の吐き溜め：楽天ブログ](https://cdn-ak-scissors.b.st-hatena.com/image/square/af0292b21d3d5e0ca4dcc6523352c371b59b5279/height=288;version=1;width=512/http%3A%2F%2Fplaza.jp.rakuten-static.com%2Fimg%2Fcommon%2Fblog_logo_ogp.png){kind=logo}
凸包の頂点数の話 - 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),...となります。 これ
球面上に均等な点を配置したい - 驚異のアニヲタ社会復帰の予備
球面上に均一な点を配置したい。約N個ならばこんな感じでやれるが、厳密にN 個おきたい。 実装が簡単なこれをやってみる。 そもそも、なぜ均一な点を球面上に配置したいかというと、基準点集合として扱えるからである。計算機では3次元データは離散的に持っており、ある球面上の点と別の物体の球面上の点を比較したいときに、両者で揃っていて、なおかつ有限個でありながら無数の点があれば離散でも連続っぽく扱えるため、比較がなんとかできるようになる。だから均一な点をたくさん発生させたい。 しかしながら、数学的に厳密な球面上の均一配置は不可能である。正多面体を考えて、その頂点に点を配置させれば、厳密に均一な点が配置できるが、正多面体は四、六、八、十二、二十に限られているので、たくさん均一な点を置きたいときには不便である。 球面上にランダムに点を発生させたときは、球面全体で見れば均一だが、局所的には疎だったり密だった
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) と置く．ただ
行列式の計算
const int N = 3; double determinant(const double x[][N]) { double tmp[N][N]; memcpy(tmp, x, sizeof(tmp)); // make pivots non-zero numbers for (int i = 0; i < N; i++) { if (tmp[i][i] != 0) continue; int k; for (k = 0; k < N; k++) if (tmp[k][i] != 0) break; if (k == N) // all numbers in a column is zero return 0; for (int j = 0; j < N; j++) tmp[i][j] += tmp[k][j]; } // make a triangular matrix for (
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
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
その19 直線同士の最接近距離と最接近点を知る
２円の交点を通る円・直線の方程式
geometry.txt
Mesh Smoothing
Virtual Arena: Room 1680
三角形の面積を外接円の半径を使って求める
任意の３点を通る円を求める方法
Sweep and prune - Wikipedia