線分集合の交点列挙： 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)させました。 重なり合いは解消されましたが、必ずしも見やすくはありません。 （これはこれで活用方法がありそうですが） ラベル開始位置をずらす 母点からボロノイ領域の中心点の方角へ、ラベルの開始位置を少しずらして配置した例です。
情報幾何学講義 【チャンネルA】
甘利俊一先生 情報幾何学講義 （チャンネルA) 統計数理研究所 夏期大学院 の講義のうち 甘利俊一先生の担当部分を配信しました。 当分の間、録画を公開する予定です。 投影資料は http://www.ism.ac.jp/shikoin/summer-school/2013.html のリンクからダウンロード可能です。 なお、以下のうち、スマートフォンや一部のタブレットでは1のみしか視聴できません。2,3は配信時にブロードキャスターを使ったためで、これはUSTREAM側の仕様のようです。お手数ですがPC・マックからの視聴をお願いします。 【甘利先生講義１ 午前冒頭】 録画のトラブルで欠けていた最初の部分を別の録画から補充しました。配信技術未熟のため冒頭に空白が、また末尾にループして冒頭がそれぞれ少し入っておりますがご容赦ください。この冒頭部分では講師の表情をとらえることに主眼をおいた撮影をし
行列式の計算
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 (
円と円の交点
半径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 若干計算量削減
平面幾何におけるベクトル演算 » 直線と線分
で求まります（ここで |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 がこ
[C#]多角形の正確な凸包判定
どうも、脳内で Template Metaprogramming が流行っている melt です。こんばんは。 といいつつも今日は Template Metaprogramming は全く関係なくて、凸包判定についてのお話です。 自分は最近ゲームプログラミングのためのリアルタイム衝突判定という本を読み進めています。 当然内容なんてほとんど分かっていないのですが、ちょっとだけ理解できる部分に面白いことが書いてありました。 多角形が凸かどうかを判定する方法をネット上で調べてみると、各線分ベクトルの外積の符号が全て同じ（内角が１８０度未満）であれば凸多角形として判断している場合が多いのだけれども、この判断だけだと十分ではない、ということが書かれていました。 五芒星なんか考えると分かりやすいと思います。 確かに内角が全て１８０度未満ですが、明らかに凸多角形では無いです。 で、これはどうやって解決す
主成分分析を使ってバウンティボックスを作る - Pashango’s Blog
以前にnumpyを使った主成分分析を公開しましたが、今回はそれを使ってバウンティボックスを作ってみます。 ある頂点集合に対して、適切なバウンティボックスを求めたいとしましょう。簡単に思いつく方法としては、基底軸X,Yごとに最大値＆最小値を求め、それらの頂点を囲む方法です。 しかし、その方法では最適なバウンティボックスにならない場合があります（下左図参照）、頂点集合に対して適切な基底軸を求めれば最適に「近い」バウンティボックスを得ることができます。 主成分分析(principal component analysis) 適切な基底軸を求めるために登場するのが「主成分分析」です。 これはもともと統計学や経済学で発明された分析手法で、似たものに「因子分析」がありますが、これはまたの機会に・・・ 主成分分析は特に難しい話ではありません、高校数学レベルの知識があれば十分理解可能です。 まず頂点集合を
もっと高速に－線分交差判定－
線分交差判定といっても、すべての与えられた線分に対して、同様な計算を 行って判定していたのでは、無駄が多いように見えます。場合によっては もっと単純な軽い判定で行えるはずです。そこで、 『場合分けによるラフチェック』を もっと簡単に－線分交差判定－のプロシージャ に追加して、次のように変更します。 '構造体 Private Type POINT x As Double y As Double End Type '座標 p1,p2 を結ぶ線分と座標 p3,p4 を結ぶ線分が交差しているかを調べる 'ただし、線分が重なっている場合(3点,4点が一直線上にある)、「交差している」、と判定します。 Private Function intersectionEX(p1 As POINT, p2 As POINT, _ p3 As POINT, p4 As POINT) As Boolean 'x座標
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Michael Garland - QSlim 2.0
geometry.txt
Mesh Smoothing
Sweep and prune - Wikipedia
Virtual Arena: Room 1308
Quickhull 3D | Heinrich Fink
レンダリングサンプル6 - 誤差の最小化を基準とする基本的なアルゴリズムで円を描く - Windows Live