どちらさまか、凸包問題と言うのを知りませんか?
多数ある点を取り囲む多角形を求めるというものです。
現実的な話で言うと、
壁に多数の釘が刺さっていて、その一番外側を囲むように
輪ゴムを引っ掛けたときにできる多角形の角の座標を求め、
その座標すべてを出力するといったものです。

具体的なアルゴリズムはこちらを見ると詳しく載っています。
よろしくお願いいたします。
http://www.race.u-tokyo.ac.jp/~masuda/jugyo/prog …

このQ&Aに関連する最新のQ&A

A 回答 (3件)

 解答とはいきませんがちょいと手助け。


一応このソースでは変数を宣言して、ファイルからデータを受け取るところまで書いてあります。

データファイルの形式は
[x1],[y1]
[x2],[y2]
.
.
.
と、カンマ区切りで縦に書いてください。(ちなみに[]はいりません)

一番下の/* ここから先が大切 */以下にグリグリかいていくわけです。
コンパイル時には -lm をつけましょう。

cc -lm Convex_Closure.c とかだったかな?

それでは。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

/* 座標データ最大数 */
#define MAX_NUM 64

/* バッファサイズ */
#define BUF_SIZ 256

/* 円周率 */
#define PIE 3.14159265358979

/* 構造体宣言 */
typedef struct{
double x;
double y;
} point;

FILE *fp;

int main(int argc, char *argv[])
{
int i, j;
int last = 0;
int wp, len, min, nxt;
char rBuff[BUF_SIZ];
char Temp[64];
point p[MAX_NUM], tp;
double rad[2];

/* ソース内でのデータ指定は面倒くさいのでファイルで渡すことにします。*/
if(argc == 1){
printf("データファイルがありません。\n");
return 0;
}

/* ファイルを開きましょう。*/
if( (fp = fopen(argv[1], "r")) == NULL ){
printf("ファイルのオープンに失敗しました。\n");
return 0;
}

/* p[]の初期化 */
for(i = 0 ; i < MAX_NUM ; i++)
p[i].x = p[i].y = 0;

/* ファイルの中身を1行ずつ読みます。 */
last = 0;
while( fgets(rBuff, BUF_SIZ, fp) != NULL){

/* 読み込んだバイト数 */
len = strlen(rBuff);

/* 座標データのセット */
for( i = 0, wp = 0 ; i < len ; i++ ){

/* X */
if(rBuff[i] == ','){
Temp[wp] = 0;
wp = 0;
p[last].x = atof(Temp);
continue;
}

/* Y */
if(rBuff[i] == '\n' || rBuff[i] == 0){
Temp[wp] = 0;
p[last].y = atof(Temp);
break;
}
Temp[wp++] = rBuff[i];
}

last++;
}
fclose(fp);

/******************************************************************/
/* ここから先が大切 */

return 0;
}
    • good
    • 0

 凸多面体の基底を求めるアルゴリズムを拝見しましたが


書いてあることをそのままするだけですね。

書けませんでは何が書けないのかわからないのでアドバイスのしようがありません。

1.点データをセットするやり方がわからない。とか
2.どうやってΘを求めるかがわからない。とか
3.ループ文の条件がわからない。とか

こうゆうのでしたら答えようもあるんですが。。。
いかかがなもんでしょう?

この回答への補足

最初からすべてわかりません。
cは一通りやったのですが、
どうやら向いていないようで・・・・。

補足日時:2001/07/18 14:19
    • good
    • 0

えーと、一体何が聞きたいのでしょうか。


必要な情報はすべて出そろっているようですが。

凸包問題を知っている人と友達になりたいとか?

この回答への補足

凸包問題のアルゴリズムはわかったのですが、
プログラムが書けません。cで。
非常に困ってます。
お願いいたします。

補足日時:2001/07/16 12:01
    • good
    • 0

このQ&Aに関連する人気のQ&A

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

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

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

Q凸レンズと凹レンズの問題

焦点距離fの凹レンズと2fの凸レンズを配置して、
凸レンズの方から入射する平行光線が、凹レンズを通った後も、
平行光線のままになるためにはどのようになるか図で示せ

という問題で、
「焦点からfの位置に凹レンズ、そこから更にfの位置に凸レンズ」
という答えになっているんですが、

凸レンズから2f離れた位置に凹レンズを置かない限り、
凹レンズの中心を通らないから、
全部平行光線になると思っていたんですが、
何故「焦点からfの位置に凹レンズ、そこから更にfの位置に凸レンズ」
という配置じゃないとダメなんでしょうか?

Aベストアンサー

答の
「焦点からfの位置に凹レンズ、そこから更にfの位置に凸レンズ」
の、最初の「焦点」は、どのレンズの焦点なのでしょうか。ちょっとよくわからない答です。
 レンズは凹レンズ凸レンズがそれぞれ1枚ではないのでしょうか?

 以下、凹凸各1枚の場合の回答です。

 凹レンズは、後ろの焦点に向かう光が、レンズ通過後に光軸に平行になりますから、凸レンズによる光が凹レンズの後ろの焦点に集まるようになればいいわけです。
 凸レンズに平行に入射した光線は凸レンズの後ろの焦点に集まりますので、凸レンズの後ろの焦点と凹レンズの後ろの焦点が一致すればいいことになります。

 凸レンズの後ろ 2f が後ろの焦点なので、ここに凹レンズの後ろの焦点が来るようにすると、凹レンズの焦点距離は f なので、凸レンズから凹レンズまでの距離は f になります。

 ということで、凸レンズの後ろ f のところに凹レンズを置けば、凸レンズに入射する平行光線が、凹レンズ通過後、平行光線になります。

 レンズが凹凸各1枚ではないのなら、この回答は無視してください。
 

答の
「焦点からfの位置に凹レンズ、そこから更にfの位置に凸レンズ」
の、最初の「焦点」は、どのレンズの焦点なのでしょうか。ちょっとよくわからない答です。
 レンズは凹レンズ凸レンズがそれぞれ1枚ではないのでしょうか?

 以下、凹凸各1枚の場合の回答です。

 凹レンズは、後ろの焦点に向かう光が、レンズ通過後に光軸に平行になりますから、凸レンズによる光が凹レンズの後ろの焦点に集まるようになればいいわけです。
 凸レンズに平行に入射した光線は凸レンズの後ろの焦点に集まります...続きを読む

Q凸型の多角形の座標

凸型の多角形が作れるような座標があります。
それぞれの座標を

P(0),P(1)・・・P(n)

とします。今それぞれの座標はバラバラで

P(0)→P(1)→P(2)→・・・→P(n)→P(0)

と結んでも凸型の多角形になりません。
これを凸型の多角形が作れるように時計回りか反時計回りに並び替えるプログラムは
どのように書いたらいいでしょうか?

Aベストアンサー

凸多角形になることが保証されているなら, 例えば
1. y座標が最小の点を見つける
2. その点から他の各点を結んだ直線の, x軸からの偏角を求める
3. 偏角の小さい順にソートする
でできるはず.

一般的には Jarvis march (ジャービスの行進) とかで調べてくれ.

Q凸集合の定義ってなんですか?

2題よろしくお願いします。
1.平面上の集合kが凸集合である定義を述べよ。
2.xy平面上の凸集合、凸でない集合をそれぞれ例示せよ。
この2題です。さっぱり分かりません。よろしくお願いします。

Aベストアンサー

つまりy=xのような直線は凸集合
n角形で一つの辺が内側にはいりこんでいれば凸集合ではない。
ん?まてよ…
さらに盛った目玉焼きを上からだけみると凸集合だ。(へこみがない場合です)
しかし、横からみると凸集合ではない。
つまり、目玉焼きは3次元的にみると凸集合ではない。
どうも線形計画法の問題みたいですね。

Qスクリーン座標からワールド座標への座標変換について

こんにちは。
現在自作で3Dゲームを制作しています。
ワールド座標からスクリーン座標への変換に成功したので
今度は逆にスクリーン座標からワールド座標への変換に挑戦していたのですが
どうにもうまくいかずに詰まってしまい、質問にきました。

ワールド→スクリーン変換にて得たスクリーン座標(sx, sy, sz)を使用して
スクリーン→ワールド変換を行うと成功するのですが
直接スクリーン→ワールド変換を行おうとすると失敗します。
というのも、直接スクリーン→ワールド変換時には sz にあたる値を
どうしたらいいものか・・・となってしまったからです。

今回、手計算(ヘルプ関数は使わず)で行っているのですが、計算していることは
ビューポート行列、プロジェクション行列、ビュー行列の逆行列を使用し
スクリーン座標(とりあえずszを0にして対応)に対して座標変換をおこなっています。
何か計算が足りていないのか、はたまた勘違いをしているのか・・・


詳しいご教授お願いいたします。


ワールド行列:単位行列
ビュー行列:視点と視線は動的に変動、上向き(0,1,0)
プロジェクション行列:視野角45度、アスペクト比 800/600
画面サイズ:800×600
テストに使用しているスクリーン座標:(200,300)

こんにちは。
現在自作で3Dゲームを制作しています。
ワールド座標からスクリーン座標への変換に成功したので
今度は逆にスクリーン座標からワールド座標への変換に挑戦していたのですが
どうにもうまくいかずに詰まってしまい、質問にきました。

ワールド→スクリーン変換にて得たスクリーン座標(sx, sy, sz)を使用して
スクリーン→ワールド変換を行うと成功するのですが
直接スクリーン→ワールド変換を行おうとすると失敗します。
というのも、直接スクリーン→ワールド変換時には sz にあたる値を
どうしたらい...続きを読む

Aベストアンサー

そもそもスクリーンに映っているのは奥行き情報が消えた「2D な絵」ですよね. だとしたら, 「視点から当該スクリーン座標に向かう (無限に長い) 視線」の上にある点はすべて「3D なワールド座標」の候補になってしまいます. そして, そのうちのどれが「正しいワールド座標」なのかをこれだけの情報から求めることは不可能です.

夜空に光る星までの距離を求めるには, 「ここで光ってる」という情報だけでは不足ですよね.

もちろん, スクリーンに映っている画像を作る元になった (ワールド座標における) オブジェクトの配置がすべてわかっているなら, 「視線の先にあるオブジェクト」を調べることはできます. もっと難しくして鏡面反射とか屈折とかを考慮すると, 結局レイトレになっちゃいますがここではそこまでの処理は不要でしょう.

Q∀B⊂R^nに対し,Bを含む最小の凸集合Aが存在の証明

[問]Rは実数体で∀B⊂R^nに対し,Bを含む最小の凸集合Aが存在する事を示せ。
[証]
Bを含む凸集合の共通部分A:=∩[C∈{C;B⊂C:凸集合}]C
を考えたのですが
∀x,y∈A,∃C∈{C;B⊂C:凸集合} such that x,y∈C.
所が∀λ∈[0,1],λx+(1-λ)y∈Cは言えるが
λx+(1-λ)y∈Aとは必ずしも言えないと思います。
どうすればλx+(1-λ)y∈Aが言えますでしょうか?

Aベストアンサー

共通部分だから。∃C じゃなくて∀C ですね。
そして論理記号の使い方がかなりあやふやと見ました。普通に日本語で論述しましょう。

Q多角形の座標を定義

RECT 構造体は四角形の左上隅と右下隅の座標を定義するものではあると思いますが

多角形の座標を定義する構造体はないのでしょうか?

Aベストアンサー

> RECT構造体は四角形の左上隅と右下隅の座標を定義するものではあると思いますが

これは、正しいとも間違いとも言えません。

C標準にはRECT構造体なるものはありません。
あなたの言う「RECT構造体」は何かのライブラリやAPI用に追加されたもので、その定義として「四角形の左上隅と右下隅の座標」としているだけです。
例えば、↓このRECT構造体はWindowsAPI用に用意されたものです。
MacやLinuxのCではそのままでは使えません。
Windowsでも、#includeで適切なヘッダを読み込まなければ使えません。
http://msdn.microsoft.com/ja-jp/library/a5ch4fda%28v=VS.80%29.aspx

他のライブラリで別の定義をしても構いません。
対応した関数等をちゃんと用意できれば、「四角形の右上隅と左下隅の座標」とか「四角形の左上隅座標と大きさ」とかで「RECT構造体」を作っても構わないわけです。


> 多角形の座標を定義する構造体はないのでしょうか?

これも同様に、C言語にはありません。
そのRECTが定義されているライブラリのマニュアル等を調べて、無いのなら「そのライブラリには」存在しないのでしょう。

無いのなら、適当に作ればいいのです。
どう定義するか、は、それをどう使いたいかを考え、都合のいいものにすればいいです。

例えば、上記のMFCを使って、Windowsの画面に多角形を書きたい、といった場合は、CDC::Polygon で簡単に使えるものがよいと考えられます。
http://msdn.microsoft.com/ja-jp/library/hhkhd4xz%28v=VS.80%29.aspx
そうすると、引数にあった型で POINT構造体の配列と、点の数を記憶できるようなものがよいでしょう。

> RECT構造体は四角形の左上隅と右下隅の座標を定義するものではあると思いますが

これは、正しいとも間違いとも言えません。

C標準にはRECT構造体なるものはありません。
あなたの言う「RECT構造体」は何かのライブラリやAPI用に追加されたもので、その定義として「四角形の左上隅と右下隅の座標」としているだけです。
例えば、↓このRECT構造体はWindowsAPI用に用意されたものです。
MacやLinuxのCではそのままでは使えません。
Windowsでも、#includeで適切なヘッダを読み込まなければ使えません。
http://ms...続きを読む

Q端子 凸 を USB端子 凸 にする器具

.
外径2.35mm/内径0.7mmの端子 凸→ USB端子 凸

に出来るインターフェース 凹凸 が見つかりません。

ご存知のかた、どうかご教示くださいませ。

Aベストアンサー

http://www.amazon.co.jp/COMON-USB%E2%86%92DC-%E5%A4%96%E5%BE%842-35mm%E5%86%85%E5%BE%840-7mm-%E9%9B%BB%E6%BA%90%E4%BE%9B%E7%B5%A6%E3%82%B1%E3%83%BC%E3%83%96%E3%83%AB/dp/B0040PBKSC/ref=cm_cr_pr_product_top

Q2次関数の最小値をC言語と遺伝的アルゴリズム(GA)を用いて求めたいです汗

私は機会系の大学生のものです。

今回は
2次関数の最小値をプログラムのC言語と遺伝的アルゴリズム(GA)を用いて求めたいのですが
私がC言語が素人のためプログラムを作れません...。例として教えていただけると幸いです。

よろしくお願い致します。

Aベストアンサー

作ってみた
https://gist.github.com/otaks/3c6eebea260ce1296da2b9a2d03fd421

各遺伝子は5要素の配列から成っており、
[3][2][1][0]を2進数に見立てて、これを10進数に変換し
[4]を元に符号をつけている。

ユーザ入力は以下を参考に。
(平方完成後の値を入力するようになっています)
y=a(x+q)2+q
(minx<=x<=maxx)

50世代ぐらい回せば正解が出そう。

中学校当たりの問題は解けそうだけど、今の作りだとxが-15~15しか
表現できないし、精度は整数レベルなので、より難しい問題を解くならば
改造が必要。

Q凸多面体について

3次元凸多面体で、任意の二頂点が隣り合ってる多面体は四面体のみですが、
4次元凸多面体で同様の性質を持つものはどれくらいあるのでしょうか?

Aベストアンサー

>「3次元凸多面体で、任意の二頂点が隣り合ってる多面体は四面体のみ」

そうですねえ・・・どうやるんでしょうか


頂点の個数をV,辺の数をE,面の数をVとすれば
任意の二点が隣接するというのは
任意の二つの頂点を選べば,それが辺になるということで
E = V(V-1)/2
ということだから

V-V(V-1)/2 + F = 2
F=(V^2-3V+4)/2

実はさらに

三つの整数の組(V,E,F)に対して
頂点の個数がV,辺の数がE,面の数がVである
3次元凸多面体が存在するための必要十分条件は
V-E+F=2
V<=2F-4
F<=2V-4

という定理があったりして(証明略,ぐぐったら出てきた)
これをつかうと
(V^2-3V+4)/2 <= 2V-4
これをとくと
3<=V<=4
になるが,V>3としてよいので V=4
このとき,
F = (16-12+4) = 4
E = 6
よって,
頂点4,辺6,面4となり
これは「四面体」である

こんな感じかなあ・・まあ,
「定理」の簡単な帰結でしょう.

残念なことに,「定理」の高次元版は分かってないといううわさ.

ついでにいうと,「定理」の証明は
同じ質問者の質問の「三角形分割」とかそういう近辺の問題なのと
オイラーの公式(V-E+F=2)の初等的な証明と似たような
操作的な処理を帰納的につかうとできるようだけど
私は証明を追いかけてません.たぶんそんなに難しくはなさそうで
少なくとも「オイラーの公式(V-E+F=2)の初等的な証明」の内容を知ってれば
きっとできるんじゃないかなと勝手に思ってる.

次元があがると変数が増えて
一気に自由度が上がるから
超越的な手法(ホモロジーとかそういうの)がないと厳しいように
思うけどどうなんだろう.

>「3次元凸多面体で、任意の二頂点が隣り合ってる多面体は四面体のみ」

そうですねえ・・・どうやるんでしょうか


頂点の個数をV,辺の数をE,面の数をVとすれば
任意の二点が隣接するというのは
任意の二つの頂点を選べば,それが辺になるということで
E = V(V-1)/2
ということだから

V-V(V-1)/2 + F = 2
F=(V^2-3V+4)/2

実はさらに

三つの整数の組(V,E,F)に対して
頂点の個数がV,辺の数がE,面の数がVである
3次元凸多面体が存在するための必要十分条件は
V-E+F=2
V<=2F-4
F<=2V-4

という定理があった...続きを読む

Q多角形の描画。(VC++)

三角形を描画したいと考えていますが、多角形を書くための関数で「Polygon」というものがあると知りました。
ヘルプを読んで早速、やってみようとしたのですがどうにも上手く行きません。

Polygonを使って描画する例などありましたら教えてください。

Aベストアンサー

Polygon関数(API)は指定したデバイスコンテキストに対して多角形を描画します。

多角形の描画の前には、
ペンの設定
ブラシの設定
描画モードの設定
塗り潰しモードの設定
等が必要です。

ペン、ブラシの設定はSelectObject関数で
描画モードの設定はブラシやペンの作成時のモードで(CreatePen関数、CreateSolidBrush関数など)
塗り潰しの設定はSetPolyFillMode関数で
それぞれ設定する必要があります。

そして、POINT構造体を頂点分だけ並べた配列が必要です。

API関数のみで書くと、かなり大きなソースコードになるので、サンプル例までは無理です。

上記説明に出てきた関数のヘルプを読んで実験してみて下さい。


人気Q&Aランキング

おすすめ情報