【先着1,000名様!】1,000円分をプレゼント!

3D空間にある平面多角形で、頂点が1000個ぐらいの多角形を想定しています。
これの多角形の辺同士で交点の有無により、自己交差を判定すると時間がかかってしまいます。

もっと、効率の良い方法はありますか?

A 回答 (2件)

ANo.1のコメントについて



http://softsurfer.com/Archive/algorithm_0108/alg …
浅野「計算幾何学」(朝倉書店)にも載ってます。
    • good
    • 0
この回答へのお礼

再度、ご回答、有難うございます
近くの図書館に行ったら、「計算幾何学」(朝倉書店)は、無かったのですが、同じ著者の「計算幾何 理論の基礎から実装まで」(共立出版)が見つかりました。
有難うございました。

お礼日時:2010/02/21 17:44

n本の線分が交点を持つかどうかを判定する、というのは計算幾何学(computational geometry)の基本的な技法で、Shamos-Hoeyの算法を使うとO(n log n)の時間で答が出せる。

線分同士の全部の組み合わせを調べているとO(n^2)の手間が掛かるのに比べ、かなり速くなります。
    • good
    • 0
この回答へのお礼

回答、有難うございます。
出来れば、参考になるHPもしくは書籍をお教えいただけると助かります

お礼日時:2010/02/20 09:23

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q閉図形の座標の配列が右回りか左回りか調べる方法

以下のような同じ形状の座標があります。
座標Aは、右回り
座標Bは、左回りになっています。
このような座標配列で、右回りか、左回りかを
判断するよい方法はないでしょうか?
よろしくお願いします。

座標A
1: 0,0
2: 7,0
3: 7,3
4: 4,3
5: 4,6
6: 0,6
7: 0,0

座標B
1: 0,0
2: 0,6
3: 4,6
4: 4,3
5: 7,3
6: 7,0
7: 0,0

Aベストアンサー

#1 です.ちょっと訂正.


> ちなみに,|S| は多角形の面積です.

面積は |S| / 2 です.

Qファイルやディレクトリの存在確認を行う方法

ファイルをオープンするのはfopenでOKですが、ファイルやディレクトリの存在確認を行う方法が知りたいです。

何か組み合わせて作るものなのでしょうか?
perlとか便利な演算子があるのですが、C/C++って器用ではないですね。
これは処理系?依存の内容ですか?

私の環境は VC6, VC2005 Windows2000です。

Aベストアンサー

int access(const char* path, int mode);
int stat(const char* path, struct stat* sb);

かな?
MSDN を引くと _access_s() を使えとか書いてあるけど。

Q英語で「個数」「件数」は?

質問は単純です。
英語で「個数」や「件数」をなんというか、です。

とりあえず、思いついたのは、numberでした。
たとえば、「りんごの個数」は"a number of apples"ですか?
でも、"a number of"は「いくつかの」という意味ですよね。

「データの件数」は"a number of data"でしょうか?

私は英語はほとんど出来ませんが、numberは「個数」というよりも「番号」という意味であるような気がしてなりません。

Aベストアンサー

>「個数」や「件数」をなんというか、です。
>とりあえず、思いついたのは、numberでした。
意外に思われるかもしれまんせんが、語の選択はnumberであっています、と思います。

>「りんごの個数」
the number of (the) apples

>「データの件数」
the number of (the) data

>numberは「個数」というよりも「番号」という意味であるような気がしてなりません。
実は、昔、私も、「個数や件数はなんていうのかな、え、number? え、本当?」と、奇異に感じたことを、思い出しました。

QLNK2019: 未解決の外部シンボルのエラーが出る

Microsoft Visual Studio 2008
Version 9.0.21022.8 RTM
Microsoft .NET Framework
Version 3.5 SP1
----------------------------------------------------------------
新しいプリジェクト→Win32 コンソール アプリケーション(ソリューションのディレクトリを作成 チェック外す)→Windows アプリケーション(空のプロジェクト チェック外す)
----------------------------------------------------------------
 プログラム

 mymain.cpp
#include "myhelper.h"
#include "mymain.h"

//自キャラのデータ
Point2D g_jikipos = {40, 400};//自キャラの座標

//画像ハンドル
int g_jikiimage[11];

//色々なファイルの読み込み
int LoadFiles(){
//画像ファイル読み込み
if(LoadDivGraph("media\\player01.bmp",
11,11,1,64,64,g_jikiimage) == -1) return -1;

return 1;
}


 mymain.h
//他から呼び出させるMyMainの関数
void MyMain();
int LoadFiles();


 myhelper.h(サンプルなので打ちミスはない)
#include "DxLib.h"
#include <limits.h>
#include <math.h>

//構造体宣言
//座標またはベクトルを記録する構造体
struct Vector{
float x,y;
};
typedef Vector Point2D;
//線を記録する構造体
struct Line2D{
Point2D startpos, endpos;
float katamuki;//傾きをラジアン値で記録
Vector speed;//移動している場合は速度をセット
};
//球体を記録する構造体
struct Ball2D{
Point2D position;
float hankei;//半径
};
//四角形を記録する構造体
struct Rect2D{
Point2D lefttop;
Point2D rightbottom;
float width;
float height;
};


//ライブラリ関数
Point2D PosInView(Point2D in);
int XInView(float inx);
int YInView(float iny);
void ScrollToLeft(float jikiposx);
void ScrollToRight(float jikiposx);
void ScrollToUp(float jikiposy);
void ScrollToDown(float jikiposy);
void DrawLineInView(float x1, float y1, float x2, float y2, int Color, int Thickness);
void DrawCircleInView(float x, float y, float r, int Color, int FillFlag);
void DrawAnimation(float x, float y, double ExtRate, double Angle,int TurnFlag,
int *imgarray, int allframe, float fps);
//ベクトル関数
Vector CreateVector(Vector in, float veclen);
Vector AddVector(Vector v1, Vector v2);
Vector SubVector(Vector v1, Vector v2);
Vector AddVectorInFrameTime(Vector pos, Vector speed);
Vector AddVectorInFrameTime2(Vector pos, Vector speed, Vector accel);
Vector Normalize(Vector in);
Vector RotateVector(Vector in, float radian);
float VectorLengthSquare(Vector in);
float DotProduct(Vector v1, Vector v2);
float CrossProduct(Vector v1, Vector v2);
void SetLine2DKatamuki(Line2D *in);
void DrawLine2D(Line2D in, int Color, int Thickness);
void DrawBall2D(Ball2D in, int Color, int Fill);
//当たり判定関数
bool HitTestLineAndBall(Line2D linein, Ball2D ballin);
bool IsPointAtLineFace(Line2D linein, Point2D ptin);
bool HitTestLineAndLine(Line2D line1, Line2D line2);
bool HitTestBallAndBall(Ball2D a, Ball2D b);
bool HitTestPointAndBox(Rect2D rect, Point2D pt);
//タイマー関数
void SetSimpleTimer(int idx, int time);
int GetPassedTime(int idx);


//グローバル変数
extern float g_frametime;
extern Rect2D g_framerect;//画面領域(当たり判定)
extern Point2D g_current_field_pos;//現在の左上座標
extern Rect2D g_stagesize;//ステージサイズ

//定数宣言
const float ZEROVALUE = 1e-10f;
const float PIE = 3.1415926f;
const int SCROLL_LIMIT = 200;
----------------------------------------------------------------
 エラー内容
1>myhelper.obj : error LNK2019: 未解決の外部シンボル "void __cdecl MyMain(void)" (?MyMain@@YAXXZ) が関数 _WinMain@16 で参照されました
1>C:\Documents and Settings\Owner\My Documents\Visual Studio 2008\Projects\my\Debug\my.exe : fatal error LNK1120: 外部参照 1 が未解決です
1>my - エラー 2、警告 0
ビルド: 0 正常終了、1 失敗、0 更新不要、0 スキップ
----------------------------------------------------------------
画像を貼り付けときます
(見えにくい場合→http://www.dotup.org/uploda/www.dotup.org154142.jpg.html)
初心者なのでわかりやすくお願いします

Microsoft Visual Studio 2008
Version 9.0.21022.8 RTM
Microsoft .NET Framework
Version 3.5 SP1
----------------------------------------------------------------
新しいプリジェクト→Win32 コンソール アプリケーション(ソリューションのディレクトリを作成 チェック外す)→Windows アプリケーション(空のプロジェクト チェック外す)
----------------------------------------------------------------
 プログラム

 mymain.cpp
#include "myhelper.h"
#include "mymain.h"

//自...続きを読む

Aベストアンサー

ファイル構成から推測するに
mymain.cpp というファイルに
void MyMain(void) {
// ここに処理を書く
}
という関数が必要なようです。

Q空間上の二点を結ぶ直線上に任意の点が存在するかどうかの関数

Cの初心者です。

空間上に存在する2点間を結ぶ直線上に任意の点が存在するかどうかの
関数を作りたいのですがどのような公式を用いて評価すればいいのか分かりません。
どなたかご教示ください。

引数
   始点 A(x,y,z)
   終点 B(x,y,z)
   直線上に存在するであろう任意の点
      C(x,y,z)

 関数のイメージ
   boolean isOnLine (Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz); 配列でもよいです。

返り値
   True、 False  ( 0 or 1 )

よろしくお願いします。

Aベストアンサー

直線ABの式を求め、その式に任意の点Cの座標を代入し、式が成り立つか判定すればOK。

(Cx,Cy,Cz)=(Ax,Ay,Az)+t(Bx-Ax,By-Ay,Bz-Az)
この式が、点Cを通る直線ABの式。

この式をt=の形に直せば
t=(Cx-Ax)/(Bx-Ax)=(Cy-Ay)/(By-Ay)=(Cz-Az)/(Bz-Az)
となる。

2つの点{(Cx-Ax)、(Cy-Ay)、(Cz-Az)}、{(Bx-Ax)、(By-Ay)、(Bz-Az)}は「点Aが原点になるように、直線ABと点Cを並行移動した時の、点Bと点Cの座標」を表わしている。

そして、原点と点Bの延長線上に点Cがあるならば各x、y、zの比は等しくなるので
(Cx-Ax):(Cy-Ay):(Cz-Az)=(Bx-Ax):(By-Ay):(Bz-Az)
が成り立つ。

つまり
(Cx-Ax)/(Bx-Ax)=(Cy-Ay)/(By-Ay)=(Cz-Az)/(Bz-Az)
が成り立つ。

プログラムでは
(Bx-Ax)が0、かつ、(By-Ay)が0、かつ、(Bz-Az)が0
(Bx-Ax)が0、かつ、(By-Ay)が0
(Bx-Ax)が0、かつ、(Bz-Az)が0
(By-Ay)が0、かつ、(Bz-Az)が0
(Bx-Ax)が0
(By-Ay)が0
(Bz-Az)が0
と言う7つの例外条件を取り除いた上
(Cx-Ax)/(Bx-Ax)と(Cy-Ay)/(By-Ay)と(Cz-Az)/(Bz-Az)が等しいかどうかを判定すれば良い。

7つの例外条件では、それぞれ

(Bx-Ax)が0、かつ、(By-Ay)が0、かつ、(Bz-Az)が0
の時
(Cx-Ax)が0、かつ、(Cy-Ay)が0、かつ、(Cz-Az)が0
ならば真(3つの点がすべて同じ座標にある)

(Bx-Ax)が0、かつ、(By-Ay)が0
の時
(Cx-Ax)が0、かつ、(Cy-Ay)が0
ならば真(直線ABがZ軸と並行)

(Bx-Ax)が0、かつ、(Bz-Az)が0
の時
(Cx-Ax)が0、かつ、(Cz-Az)が0
ならば真(直線ABがY軸と並行)

(By-Ay)が0、かつ、(Bz-Az)が0
の時
(Cy-Ay)が0、かつ、(Cz-Az)が0
ならば真(直線ABがX軸と並行)

(Bx-Ax)が0
の時
(Cx-Ax)が0、かつ、(Cy-Ay)/(By-Ay)と(Cz-Az)/(Bz-Az)が等しいならば真(直線ABが「平面(Bx-Ax)=0」上にある)

(By-Ay)が0
の時
(Cy-Ay)が0、かつ、(Cx-Ax)/(Bx-Ax)と(Cz-Az)/(Bz-Az)が等しいならば真(直線ABが「平面(By-Ay)=0」上にある)

(Bz-Az)が0
の時
(Cz-Az)が0、かつ、(Cx-Ax)/(Bx-Ax)と(Cy-Ay)/(By-Ay)が等しいならば真(直線ABが「平面(Bz-Az)=0」上にある)

と判定すればよい。

なお、この判定では「点Cが直線ABの延長線上にあり、点Aと点Bの中間にない場合(線上にあるが外側にある場合)」にも真となる。

点Cが点Aと点Bの中間にあるかどうかは「Ax、Bx、Cxの大小関係」で判定可能なので、上記の判定の前に判定してしまうと良い(Ay、By、Cy、Az、Bz、Czの大小関係は無視して良い)

直線ABの式を求め、その式に任意の点Cの座標を代入し、式が成り立つか判定すればOK。

(Cx,Cy,Cz)=(Ax,Ay,Az)+t(Bx-Ax,By-Ay,Bz-Az)
この式が、点Cを通る直線ABの式。

この式をt=の形に直せば
t=(Cx-Ax)/(Bx-Ax)=(Cy-Ay)/(By-Ay)=(Cz-Az)/(Bz-Az)
となる。

2つの点{(Cx-Ax)、(Cy-Ay)、(Cz-Az)}、{(Bx-Ax)、(By-Ay)、(Bz-Az)}は「点Aが原点になるように、直線ABと点Cを並行移動した時の、点Bと点Cの座標」を表わしている。

そして、原点と点Bの延長線上に点Cがあるならば各x、y...続きを読む

Q3次元空間内での線分の交差判定について

はじめまして。
3D関係のプログラムを組む上で、線分同士の判定を行う必要があるのですが
数学の知識が乏しく困っています。

3次元空間内の線分ABとCDが交差しているか判定し、
交差していればその交点を求めたいのです。
2次元の場合はできたのですが、3次元になるとどうやって計算すればよいのか
わかりません。(交差以外に、ねじれの位置関係があるんですよね?)
どなたか教えていただけると助かります。

Aベストアンサー

1)一般に「捩れの位置」になりますから、互いに最短の位置を求める問題に帰着します。a-kumaさんの言われるような連立一次方程式では未知数が2つ、式がx,y,z3つとなるので解けません。2次元ならyosizoさんの言われるように未知数と式の数が2つで簡単に解けます。

2)線分AB、CDの何れかの長さが<ε以下、または、線分AB、CDはほぼ平行ならゼロ割を起こすか答えが求まっても答えの精度が著しく低下します。このチェックも実際のプログラムでは絶対に必要です。

3)で、以下、2)のチェック済みであると仮定して.....。

4)たまたま最近3D-CAD用に作ったもので数式の求めた方を忘れてしまったが、

// t0:AB方向単位ベクトル、t1:CD方向単位ベクトル、として、
// float spd = <t0・t1>即ち、ベクトルt0とt1の内積

float det= spd*spd - 1.0f; // spd:AB方向単位ベクトル
v01 = C - A; //3Dベクトル (C-A)
u0 = (spd*<v01・t1> - <v01・t0>) / det;
u1 = (<v01・t0> - spd*<v01・t1>) / det;

として、パラメータ、u0,u1が求まります。ここに、
u0:AB方向パラメータ、u0=0の時、q0(u0)=Aで、u0はAからの距離を表わす。
■q0(u0)=A+u0*t0...............Equ.1)
u1:CD方向パラメータ、u1=0の時、q1(u1)=Cで、u1はCからの距離を表わす。
■q1(u1)=C+u1*t1...............Equ.2)

これで、捩れの位置に2点求まるのですが、

・2点が距離の許容誤差よりも離れていたら、エラーとする。
・2点が距離の許容誤差以内なら、2点の中点を取る。
・中点がいやなら、重みを掛ける(場合もある)。

この説明で不十分ならあとで補足します。

1)一般に「捩れの位置」になりますから、互いに最短の位置を求める問題に帰着します。a-kumaさんの言われるような連立一次方程式では未知数が2つ、式がx,y,z3つとなるので解けません。2次元ならyosizoさんの言われるように未知数と式の数が2つで簡単に解けます。

2)線分AB、CDの何れかの長さが<ε以下、または、線分AB、CDはほぼ平行ならゼロ割を起こすか答えが求まっても答えの精度が著しく低下します。このチェックも実際のプログラムでは絶対に必要です。

3)で、以下、2)のチェック済みである...続きを読む

Q多角形ポリゴン同士の衝突判定をしたいのですが。。。

3次元上に2つの多角形ポリゴンをCGで描きました。この2つの物体の衝突判定を
行いたいのですが、数学では、このような問題はどのように解くのでしょうか?

もう少し詳しく述べると、多角形は三角形の集合で描かれています。
2つの多角形をA、Bとすれば、Aをなす三角形とBをなす三角形が
重なる、もしくは、交わらなければAとBは衝突していないことになると思うのですが、どうでしょうか?

2つの三角形が衝突していないということを表す式、考え方がありましたら
教えてください。また、それ以外にベストと思われる式、考え方がありましたら
教えてください。

Aベストアンサー

こんにちは。

三次元シミュレーションなどで実際によく利用されているのは、
点が面の中に収まっているかを判定、点と面の距離を計算
で接触判定はよく行われています。

上記のような計算を行うには、ベクトルによる計算が用いられます。
参考1: http://hp.vector.co.jp/authors/VA013845/algorithm/index.html
参考2: http://osaka.cool.ne.jp/pevips/rg2.shtml

ベクトルによる計算の詳しい説明については、ここでは割愛させて頂きます。

参考URL:http://osaka.cool.ne.jp/pevips/rg2.shtml

QDXFファイルを開くフリーソフトは?

MACで作成されたCAD図面(DXFファイル)をWindowsで開くことは出来るのでしょうか?
もしフリーソフトでそのようなものがあれば非常にうれしいのですが。。
是非とも教えて下さい。
よろしくお願いします。

Aベストアンサー

DXFは、テキスト・ファイルなのでMACで作成したものであってもWindowsで開けるはずです。
(windowsは、そのままではMacで作成したファイルを開けないので、windows用に変換する必要があります。)

DXFを開けるフリーソフトとしては、JW_CADやDWG TrueView(Autodesk)があります。
http://www.jwcad.net/
http://www.autodesk.co.jp/adsk/servlet/index?id=7126351&siteID=1169823

JW_CADは、日本で一番ユーザーの多いCADですが、DXFを読む込むと大きさと位置が不定になり、
自分の思っているイメージとかなり違う場合があります。

TrueViewは、AutoCADを作っているAutodeskが、公開しているソフトです。
読み込めるファイル形式は、DWGとDXFの2種類があります。
(この2つのファイル形式を決めているのがAutodeskです。)
特にDXFは、AutoCAD以外が作成した物はAutodeskの製品で読み込め無い場合が多々ありますので注意が必要です。

windows版のvectorを扱った経験から言うとTrueViewのほうがJW_CADより元データの再現性は良いと思います。

DXFは、テキスト・ファイルなのでMACで作成したものであってもWindowsで開けるはずです。
(windowsは、そのままではMacで作成したファイルを開けないので、windows用に変換する必要があります。)

DXFを開けるフリーソフトとしては、JW_CADやDWG TrueView(Autodesk)があります。
http://www.jwcad.net/
http://www.autodesk.co.jp/adsk/servlet/index?id=7126351&siteID=1169823

JW_CADは、日本で一番ユーザーの多いCADですが、DXFを読む込むと大きさと位置が不定になり、
自分の思っているイメージと...続きを読む

Q直線上にある点の座標の求め方

お世話になります。
点a(x1,y1)と点b(x2,y2)の直線上に点cを設けるとします。
設けた点cの座標を求めるプログラムをVBで作りたいのですが宜しくお願いします。

入力データは、点a(x1,y1)と点b(x2,y2)の座標と点aから点cの距離(k)を入力すると点cのx,yの座標を返すようなプログラムを考えています。

どうか宜しくお願いします。

Aベストアンサー

' abベクトルを求めて、
xv=x2-x1
yv=y2-y1
' ベクトルの大きさを求め、
r=Sqrt(xv^2+yv^2) Sqrt?Sqrかも?
' 点aからabベクトル方向、距離kの点を求める。
x=x1+xv/r*k
y=y1+yv/r*k

とか。

a、bが同じ点だった場合の場合分けとか必要だと思いますが。

QCStringからchar*への型変換について教えてください。

以前の質問に

int型 → CString型/char型

がありましたが、

CString型をchar*型に変換する方法を
教えていただければありがたいです。

MSDNで「LPCTSTRキャスト」が説明されていましたが、
例が載ってないのでよくわかりませんでした。

よろしくお願いします。

Aベストアンサー

目的にもよりますが一時的にchar配列として使いたいならCString::GetBuffer()が利用できます。
char配列としての利用が終わったらCString::ReleaseBuffer()する必要がありますが。

直接CString内の文字列を扱う必要があるならCString::operator LPCTSTRで文字列ポインタが得られます。
ただし、CStringオブジェクトをいじると無効ポインタなる可能性があるので気をつけてください。

MSDNのMicrosoft Foundation Classリファレンス→CString→クラスメンバで確認してください。


人気Q&Aランキング