第3回 平面走査法による線分の交差検出（前編） | gihyo.jp
今回から平面走査法という手法による、線分の交差検出について解説します。この手法を使うことで、多数の線分の中から交点を高速に見つけ出すことができます。 はじめに 計算幾何学では、巨大な入力データを扱う可能性を想定して、計算量の少ない効率的なアルゴリズムの追求が行われます。今回からは、線分の集合から交差を検出する問題を取り上げます。平面走査法と呼ばれるアルゴリズムを使用することで、総当たり式の実装に比べ、計算量を大きく削減できることを見ていきます。 多数の線分から交差を見つける 前回、線分を表すLineSegmentクラスを作成し、2つの線分が交差するかどうかを調べるintersects()メソッドや、交点座標を求めるgetIntersectionPoint()メソッドを実装しました。 さて今後、プログラムの扱う線分が100個、1,000個、あるいはそれ以上に増えたときのことを考えてみましょう
第1回 直線の幾何 | gihyo.jp
計算幾何学とは 小学生や中学生の頃、算数や数学の授業で、台形の面積を求めたり、直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは、コンピュータサイエンスの立場から、こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は、今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか、地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。 本連載では、ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ、Javaプログラムでアルゴリズムを実装しながら、計算幾何学の初歩を学びます。 Blogopolisとボロノイ図 Blogopolisは筆者の開発したWebサイトで、主に日本国内で開設された25万件以上のブログを解析し、「仮想都市景観」として視覚化したサービ
2D衝突編その5 円と線分から多角形と円へ
ホーム < ゲームつくろー！< 衝突判定編 2D衝突編 その５ 円と線分から多角形と円へ 多角形は線で構成された閉じた図形です。多角形と円が衝突しているかどうかを判定できれば、複雑な形状をしたものと球とを正しく衝突判定させる事ができるようになります。効率はあまり良くありませんが、知って損はありません。 ひとつ注意。ここでの多角形は「凸多角形（多角形のどの内側の角度も180度以下である多角形）」です。凹多角形だとうまくいきません。 ① 多角形の定義 まず多角形を定義します。記号化がちょっと面倒なのですが、配列のような書き方にしておきます： 多角形 ： 頂点P[n](x[n], y[n]) 円は言わずもがなですが、中心点の座標と半径で定義できます： 円 ： 中心点C(xc, yc)、半径r では下の図を御覧ください： この図は多角形の一部と幾つかの衝突を起こしている円の状態を示しています。C1
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
線分と楕円が交差する条件
No.1です。 > d=abs((ay2-ay1) *x1+(ax1-ax2)*y1+(ay1*ax2-ax1*ay2 ))/sqrt((ay2-ay1) ^2+(ax1-ax2)^2)・・・(1) > (ax2-ax1)(x1-ax1)+(ay2-ay1)(y1-ay1)>0・・・(2) > (ax1-ax2)(x1-ax2)+(ay1-ay2)(y1-ay2)>0・・・(3) > この 3式の > x1をx1 / |px2-px1| > y1をy1 / |py2-py1| > に置き換えたので宜しいのでしょうか？ それでいいと思います。 他のやり方としては、線分の方程式はtを媒介変数として x=(ax2-ax1)t+ax1, y(ay2-ay1)t+ay1 (0≦t≦1) と表せますから、これを楕円の方程式に代入して、 tの解が0から1の範囲にあるかどうかを調べる手もあります。
幾何アルゴリズム
格子充填曲線の生成プログラム（n×n の２次元格子の、左上隅からはいり右下隅から抜ける、ランダムなハミルトン経路を生成するアルゴリズムで）
ボロノイ図いろいろ - kaisehのブログ
Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。 マンハッタン距離にもとづくボロノイ図 ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。 加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram) 母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。 加法的重み付きべき乗ボロノイ図 (Additivel
凸集合 - Wikipedia
円板のように見える凸集合、（緑色）の凸集合は x と y を繋ぐ（黒色）の直線部分を含んでいる。凸集合の内部に直線の部分の全体が含まれる。 ブーメランのように見える非凸集合、x と y を繋ぐ（黒色）の直線の一部が（緑色）の非凸集合の外側へはみ出ている。 ユークリッド空間における物体が凸（とつ、英: convex）であるとは、その物体に含まれる任意の二点に対し、それら二点を結ぶ線分上の任意の点がまたその物体に含まれることを言う。例えば中身のつまった立方体は凸であるが、例えば三日月形のように窪みや凹みのあるものは何れも凸でない。凸曲線（英語版）は凸集合の境界を成す。 凸集合の概念は後で述べるとおり他の空間へも一般化することができる。 函数が凸であることと、函数のグラフの（緑色の）領域が函数のグラフの上にあるような函数は（下に）凸である。 S は実数体（あるいはより一般に適当な順序体）上のベク
Convex hull - Wikipedia
This article is about the smallest convex shape enclosing a given shape. For boats whose hulls are convex, see Hull (watercraft) § Hull shapes. The convex hull of the red set is the blue and red convex set. In geometry, the convex hull, convex envelope or convex closure[1] of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all conve
Cuboid - Wikipedia
Example of a quadrilateral-faced non-convex hexahedronIn geometry, a cuboid is a hexahedron with quadrilateral faces, meaning it is a polyhedron with six faces; it has eight vertices and twelve edges. A rectangular cuboid (sometimes also called a "cuboid") has all right angles and equal opposite rectangular faces. Etymologically, "cuboid" means "like a cube", in the sense of a convex solid which c
直交座標系 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Cartesian coordinate system|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の
R-tree - Wikipedia
Simple example of an R-tree for 2D rectangles Visualization of an R*-tree for 3D points using ELKI (the cuboids are directory pages) R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984[2] and has found significant use in both th
Hyperplane separation theorem - Wikipedia
In geometry, the hyperplane separation theorem is a theorem about disjoint convex sets in n-dimensional Euclidean space. There are several rather similar versions. In one version of the theorem, if both these sets are closed and at least one of them is compact, then there is a hyperplane in between them and even two parallel hyperplanes in between them separated by a gap. In another version, if bo
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
重心ボロノイ分割 - SourceChord
コルクボード風の壁紙を生成するアプレットを作っているときに， ・平面上に均等にランダムな点を作りたい と思って何かいい方法がないか考えてみました． で，使えるかな，と思った方法が ポワソンディスクサンプリング 各サンプリング点ごとに円盤状の半径を持っていて 新たにサンプリングするときに，それまでに配置されている他のサンプリング点の半径の中に入っていた場合は棄却し，他の点をサンプリングする． というのを繰り返す． 重心ボロノイ分割をして，その重心を用いる 任意の数のサンプル点を適当に生成． その点を用いて，ボロノイ分割をし，各領域の重心を求める． サンプル点の位置をその領域の重心に移動． これを，サンプル点と重心が一致(距離が閾値以内)になるまでくりかえす． 今回はサンプル点がいくつになってもいいようにしたかったので，重心ボロノイ分割を使うことにしました． ポワソンディスクサンプリングでは，
OBB vs AABB - Radium Software Development
This domain may be for sale!
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
線分と円が交差する条件
Rectilinear polygon - Wikipedia
Bounding volume - Wikipedia
Ray Tracing News, Volume 12, Number 2