ピックの定理 - Wikipedia
頂点が全て格子点上にある多角形 ピックの定理（-ていり、Pick's theorem）は等間隔に点が存在する平面上にある多角形の面積を求める公式である。この場合の多角形の頂点は全て右図のように、最も近い点同士の間隔を1とする正方格子点（等間隔に配置されている点）上にあり、内部に穴は開いていないものとする。多角形の内部にある格子点の個数を i、辺上にある格子点の個数を b とするとこの種の多角形の面積 S は以下の式で求められる。 例えば図の六角形なら内部にある点が i = 39 個、辺上にある点が b = 14 個なので S = 39 + 14/2 − 1 = 45 と簡単に計算できる。 この定理は 1899 年に ゲオルグ・アレクサンダー・ピックによって初めて示され、エルハート多項式により三次元以上に拡張して一般化することができる。 同公式はまた、多面体上の図形に対して一般化することもで
円と円の交点
半径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 若干計算量削減
平面幾何におけるベクトル演算 » 内積と外積
内積・外積 ベクトルの内積 (inner product, dot product, scalar product) と外積 (outer product, cross product, vector product) という演算を用いると幾何の問題を解く考え方が簡単になります。 幾何学における内積や外積はもともと3次元空間上で定義されるものなので，まずは3次元空間上で幾何学的な内積・外積を導入し， それらが線形代数的なベクトル演算と等価であることを利用し，内積・外積を2次元平面上に拡張（縮小？）します。 3次元空間上において，ベクトルの内積（ドット積）は a⋅b で表され， 以下の式で定義されます： 内積はcosを使って定義されている点と，内積の結果は単一の値＝スカラーになる点に注意してください。 また，ベクトルの外積（クロス積）は a×b で表され， その大きさ |a×b| は で与え
lucille 開発日記: タイトフィット OBB
タイトフィット OBB OBB(Oriented Bounding Box, 有向バウンディングボックス)は、たぶんコンピュータグラッフィクスの世界では、 SIGGRAPH 1996 で発表された論文がその起源として有名かと思います。 OBB-Tree: A Hierarchical Structure for Rapid Interference Detection この論文を発表した UNC(ノースカロライナ大学) の Gamma(Geometric Algorithms for Modeling, Motion and Animation) 研究グループは、ジオメトリの研究で有名ですね(なんか昔は違うグループ前だった気がするけど気のせいかな...) 点群(CGの場合ではポリゴンの頂点群)から、それをタイトフィットに囲むような OBB を求めるカギは、点群の直径(Diameter of
凸集合 - Wikipedia
円板のように見える凸集合、（緑色）の凸集合は x と y を繋ぐ（黒色）の直線部分を含んでいる。凸集合の内部に直線の部分の全体が含まれる。 ブーメランのように見える非凸集合、x と y を繋ぐ（黒色）の直線の一部が（緑色）の非凸集合の外側へはみ出ている。 ユークリッド空間における物体が凸（とつ、英: convex）であるとは、その物体に含まれる任意の二点に対し、それら二点を結ぶ線分上の任意の点がまたその物体に含まれることを言う。例えば中身のつまった立方体は凸であるが、例えば三日月形のように窪みや凹みのあるものは何れも凸でない。凸曲線（英語版）は凸集合の境界を成す。 凸集合の概念は後で述べるとおり他の空間へも一般化することができる。 函数が凸であることと、函数のグラフの（緑色の）領域が函数のグラフの上にあるような函数は（下に）凸である。 S は実数体（あるいはより一般に適当な順序体）上のベク
Minimum bounding rectangle - Wikipedia
A series of geometric shapes enclosed by its minimum bounding rectangle In computational geometry, the minimum bounding rectangle (MBR), also known as bounding box (BBOX) or envelope, is an expression of the maximum extents of a two-dimensional object (e.g. point, line, polygon) or set of objects within its x-y coordinate system; in other words min(x), max(x), min(y), max(y). The MBR is a 2-dimens
OBB vs AABB - Radium Software Development
This domain may be for sale!
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
２円の交点を通る円・直線の方程式
Amazon.co.jp: 計算幾何: 理論の基礎から実装まで (アルゴリズム・サイエンスシリーズ 10 数理技法編): 浅野哲夫: 本
http://gamma.cs.unc.edu/users/gottschalk/main.pdf
Ray Tracing News, Volume 12, Number 2