- 1 名前：デフォルトの名無しさん mailto:sage [2012/03/21(水) 06:40:59.10 ]
- データ構造とアルゴリズムに関する総合スレ。
【関連スレ】
3Dアルゴリズム全般
toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
toro.2ch.net/test/read.cgi/tech/1217773415/
- 116 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 00:17:18.82 ]
- diffの動作原理を知る〜どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社
ttp://gihyo.jp/dev/column/01/prog/2011/diff_sd200906
これ全然理解できない・・・
- 117 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 09:26:36.11 ]
- >>116
「編集距離」で検索すれば分かりやすいページがたくさん
10年位前にOCRの認識率を計測するために色々とインプリメントしたな〜
- 118 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 09:35:41.80 ]
- 単純なアルゴリズム（長さMとNの文字列に対して計算量MNになるアルゴリズム）の
解説をすっとばして、実用的なアルゴリズムの解説になってるなぁ。
理解するためにはまず単純なアルゴリズムの解説を探すといいと思う。
- 119 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 11:11:01.86 ]
- >>116
技術評論社のサイト初めて見たけど、中々興味深い記事があるな。
- 120 名前：デフォルトの名無しさん [2012/06/05(火) 11:41:07.31 ]
-
【問１】
ある点が三角形abcの中にあるかどうかを判定する簡潔な方法を俺に教えよ
- 121 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 11:56:58.65 ]
- ぼくのかんがえたさいきょうの(ry
ある点をdとすると、
abc＝abd+acd+bcd（面積）
どうやって実装するのかはシラネ
- 122 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 11:58:14.51 ]
- ・重心とその点を結んで各辺と交わるかどうか調べる
- 123 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 12:10:29.02 ]
- いや結ぶのは三角形の一点でいっか
- 124 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 12:14:58.41 ]
- 0 < ↑ab・↑ap かつ 0 > ↑ab・↑bp かつ
0 < ↑bc・↑bp かつ 0 > ↑bc・↑cp かつ
0 < ↑ca・↑cp かつ 0 > ↑ca・↑ap ならば、点pは△abcの中。
なお、計算に無駄がある。
- 125 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 12:17:49.79 ]
- ごめん、嘘。でもベクトルの内積の符号を調べる方法で良かったはず。
- 126 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 12:38:23.40 ]
- 0 > (↑ab・↑ap)(↑ac・↑ap) かつ
0 > (↑bc・↑bp)(↑ba・↑bp) かつ
0 > (↑ca・↑cp)(↑cb・↑cp)
- 127 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 13:04:37.41 ]
- class Triangle
{
public Point PointA { get; set; }
public Point PointB { get; set; }
public Point PointC { get; set; }
public bool PointIsInsideOfThis(Point target)
{
return 宿題か(target);
}
}
- 128 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 13:39:43.07 ]
- 目視で確認が一番簡素
- 129 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 13:49:07.51 ]
- >>121
これ？
upload.wikimedia.org/wikipedia/ja/math/3/2/f/32f967328ca04765e6804a07e6d1dbc7.png
- 130 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 17:15:26.77 ]
- ヘロンの式だな
- 131 名前：デフォルトの名無しさん mailto: １２０ [2012/06/06(水) 10:50:47.34 ]
-
A. ありがとうございました
- 132 名前：デフォルトの名無しさん mailto:sage [2012/06/06(水) 17:46:11.37 ]
- 1. VRAMに三角形を描画して中を赤とかで塗る
2. 点に対応するアドレスの値を読み、背景色か赤か判定
BASICならたぶん2行で書ける
- 133 名前：デフォルトの名無しさん mailto:sage [2012/06/06(水) 17:49:59.95 ]
- えらい無駄が多いな
- 134 名前：デフォルトの名無しさん mailto:sage [2012/06/06(水) 19:49:12.59 ]
- □□
□ ・ □
□ □□
□
こういうコーナーができたときに、「・」の場所は塗り潰せないからアウトだな。
- 135 名前： ◆QZaw55cn4c mailto:sage [2012/06/06(水) 21:20:34.03 ]
- >>134
詰め碁か？
二眼確保で安泰型にみえてしまうのだが？
- 136 名前：デフォルトの名無しさん mailto:sage [2012/06/07(木) 04:44:03.28 ]
- 一発なら>>126
もしくは２点から特定の角度範囲内
何度も判定するなら>>132みたくマップを作ったほうがいいな
>>134
塗りつぶしを自作すれば可能
- 137 名前：デフォルトの名無しさん [2012/06/07(木) 10:13:32.12 ]
- アンチエイリアスつきの塗りつぶし三角形を計算で出そうとすると
www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=ana.html
- 138 名前：片山博文MZボット ◆0lBZNi.Q7evd [2012/06/08(金) 11:57:52.99 ]
- >>137 これすげー。出版しろよ。
- 139 名前：デフォルトの名無しさん mailto:sage [2012/06/08(金) 13:37:48.75 ]
- wikiの内容とは何の関係もないんだな
- 140 名前：デフォルトの名無しさん [2012/06/08(金) 13:57:23.20 ]
- ただのアフィじゃねーか
死ねよ
- 141 名前：じゃがりきん [2012/06/09(土) 09:34:10.60 ]
- このコードじゃ出版できないぜ〜
- 142 名前：デフォルトの名無しさん mailto:sage [2012/06/09(土) 22:58:18.07 ]
- ワイルドだろぉ〜？
- 143 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 00:39:33.38 ]
- ダイクストラ法のwikipediaでの説明が日本語と英語のページで全然違うんだけど
なぜ？
- 144 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 00:43:39.84 ]
- 公用語の違いかな
- 145 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 19:25:30.28 ]
- 書いた人が違うから
- 146 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 19:31:34.41 ]
- 不特定多数が編集するから
あまり信用ならない
悪意ある改変とかマイナーな記事なら修正される機会も少ないだろうし
- 147 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 19:42:39.47 ]
- >>146
そういう思い込みを吹き込むのは如何なものか。
- 148 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 19:59:55.31 ]
- 「いくらなんでもwikipを書き換えるなんてことはしないだろう」という思い込み
- 149 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 20:14:16.52 ]
- どこか１サイトの情報だけ見ようとするからダメなんだよ
個人サイトでもその人の勘違いや間違いで誤った事が書かれてることもあるし
wikipedia含めいくつかのサイトで情報見比べることが大事
- 150 名前：デフォルトの名無しさん mailto:sage [2012/06/10(日) 20:34:12.90 ]
- >>143
翻訳記事じゃないんだから構成が違っていて当然だが、何か問題でも？
- 151 名前：uy mailto:sage [2012/06/11(月) 04:31:24.08 ]
- Wikipediaとか
2chで信者とアンチが争ってるようなカテゴリーの記事だと改変されまくり
Wikipediaと、Wiki以外のサイトの最低2つは情報見ろよゴミカス死ねと思う
- 152 名前：デフォルトの名無しさん mailto:sage [2012/06/11(月) 05:42:43.76 ]
- 基地外コテｷﾀｰ
- 153 名前：デフォルトの名無しさん [2012/06/12(火) 14:09:24.92 ]
- detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1488984684
お願いします
- 154 名前：デフォルトの名無しさん mailto:sage [2012/06/12(火) 16:15:20.50 ]
- 英語が読めないアホはどうぞインチキ情報に騙されてくださいねｗ
- 155 名前：デフォルトの名無しさん mailto:sage [2012/06/12(火) 21:12:15.06 ]
- 概要の、まずビー玉と紐を用意し・・・
擬似コード
こんな説明でわかるやつ天才や
- 156 名前：デフォルトの名無しさん mailto:sage [2012/06/17(日) 05:10:41.60 ]
- trieすら自力実装できない自分の頭に悪さに絶望してます
死んだ方がいいですか?
- 157 名前：デフォルトの名無しさん mailto:sage [2012/06/17(日) 05:42:29.75 ]
- うん。
- 158 名前：デフォルトの名無しさん mailto:sage [2012/06/17(日) 05:47:14.55 ]
- プログラミングの才能がないと、いくら努力しても土方止まり
他の才能を持っている分野で頑張った方がいいよ
アルゴリズムの説明すると、すぐ理解する後輩がすげーと思ったら、
まわりの大半がそうだった。死にたい。
- 159 名前：デフォルトの名無しさん mailto:sage [2012/06/17(日) 09:01:12.14 ]
- 培養菌の数をカウントするのってどうやるんだろう？
画像から直径と中心を判別するには？
- 160 名前：デフォルトの名無しさん [2012/06/21(木) 01:34:04.14 ]
- >>159
羊と狼を数えるアルゴリズム
www2c.comm.eng.osaka-u.ac.jp/~alcon2009/overview.php
- 161 名前：デフォルトの名無しさん mailto:sage [2012/06/21(木) 01:39:31.54 ]
- コロニーだから丸？
輪郭抽出→クロージング→オープニング→連続してるのを数える
- 162 名前：デフォルトの名無しさん mailto:sage [2012/06/21(木) 03:30:23.41 ]
- >>159
単純に色の違うピクセル数をカウントして１ピクセルあたりいくらってのをかけてやるんじゃダメ？
- 163 名前：デフォルトの名無しさん mailto:sage [2012/06/21(木) 09:27:55.64 ]
- 大きさの異なる円が２つ以上重複していてもカウントできなくちゃダメだろ
- 164 名前：デフォルトの名無しさん mailto:sage [2012/06/22(金) 02:20:12.99 ]
- サメガメの判定で処理負荷が問題になる状況ってどんなだよ。しかも揚げ足取りで揉めてるし。
- 165 名前：デフォルトの名無しさん mailto:sage [2012/06/22(金) 07:32:19.63 ]
- 亀
- 166 名前：デフォルトの名無しさん mailto:sage [2012/06/22(金) 08:00:23.50 ]
- ほとんど重複だから
輪郭の一部である弧から直径と中心を拾うアルゴリズムかな・・・
で、どうやるの？
- 167 名前：デフォルトの名無しさん mailto:sage [2012/06/22(金) 08:36:03.17 ]
- OpenCV を使う。
というか画像処理スレの話題。
- 168 名前：じゃがりきん [2012/06/27(水) 13:58:41.44 ]
- >>137の一部がカラパイアに載ったぜ〜
- 169 名前：デフォルトの名無しさん mailto:sage [2012/06/27(水) 14:06:45.24 ]
- 本人いたのかいな
- 170 名前：デフォルトの名無しさん [2012/06/28(木) 13:15:54.50 ]
- 円の内部（円周上を含む）に点を指定した数だけ打ちたい
それぞれの点の距離を最大化するように打つにはどうすればいい？
- 171 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 13:29:06.42 ]
- 最適化問題むずかしす
- 172 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 13:39:35.73 ]
- n=1 どこでも
n=2 2点を繋ぐ線分が円の中心を通るような円周上の2点
n=3〜6 円に内接する正n角形の頂点
n=7 円に内接する正6角形の頂点と円の中心
n>=8 これの求め方を教えてってこと
- 173 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 13:42:50.29 ]
- 予想としては
同心円の円周上に点を取っていくことになる
- 174 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 13:43:23.14 ]
- なかなか面白い問題
- 175 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 13:46:30.74 ]
- 正三角形による円充填になりそう。
- 176 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 13:54:51.33 ]
- １．円内にランダムに点をばらまく。
２．全ての点についてそれぞれ最近傍の点を見つける
３．その点から離れる方向に移動。移動量はXXX。
４．３の移動量の総和が閾値以下になるまで２へ戻って繰り返す。
みたいなのを考えたんだけど移動量はどうすればいいか
- 177 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 13:55:12.35 ]
- 充填問題の一種だろうな。
ja.wikipedia.org/wiki/%E7%90%83%E5%85%85%E5%A1%AB#.E5.86.86.E5.85.85.E5.A1.AB
に
1940年、マジャル人数学者 László Fejes Tóth は、六方格子が正規も非正規も含めたあらゆる円充填の中で最も高密度であることを証明した。
とあるが参考になるだろうか。
- 178 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 14:02:08.92 ]
- >>176
1番目と2番目に近い点と自身で正三角形を作るように移動してはどうか
移動量と移動方向が決まる
- 179 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 14:03:00.53 ]
- >>176
振動しまくって終わる予感。
- 180 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 14:56:24.90 ]
- hydra.nat.uni-magdeburg.de/packing/cci/cci.html
- 181 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 15:29:41.61 ]
- 球ならどうなんの？
４次元以上なら？
- 182 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 16:17:59.04 ]
- >>176
単純に (距離)^-2 の斥力がはたらくようにしてみた
www.dotup.org/uploda/www.dotup.org3139871.png
円周部の密度が高くなってしまう
- 183 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 16:20:30.94 ]
- >>182
それって再近傍の点からの斥力？
全ての点から r^-2 の斥力を受けたらどうなるかね。
- 184 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 16:21:38.62 ]
- >>183
すまんこ
全ての点からの斥力にしてる
- 185 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 16:27:49.50 ]
- 毎ターン、各点の再近傍の点からの距離の平均を求め、その平均値との差の二乗に比例して引力／斥力を受けたらどうなるだろうか。
- 186 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 16:32:57.36 ]
- >>182
円周部から中心方向に移動する力が働かないからかな
- 187 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 16:43:40.74 ]
- 点Aの座標 P(A)
点Aと点Bの2点間距離 D(A,B) = D(B,A)
点の集合 Z = {A,B,C, ....}
D(a,b) ≧ D(c,d) ∧ P(x)≠P(y) [x≠y; ∀x,y∈{a,b,c,d}; ∀a,b,c,d∈Z;]
を満たすZを求める
- 188 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 17:24:25.85 ]
- >>182
円周部を端点じゃなくて無限にしてみたらどうだろう
- 189 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 17:29:54.11 ]
- >>187
定式化がめちゃくちゃじゃないの？
例えば4点でそれを満たすユークリッド平面上の点の例があるの？
- 190 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 18:00:35.89 ]
- >>188
無限に飛んでいくだけだな
- 191 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 18:05:33.70 ]
- 逆に考えるんだ。
mathnokai.seesaa.net/image/hex_circle.gif
こういう正三角形のメッシュを考えて、
ちょうど求める数の頂点が円内部に入るように、円の半径と中心を動かすんだ。
- 192 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 18:48:26.53 ]
- >>191
点の数が多いときは圧倒的によさそう
- 193 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 23:25:07.62 ]
- 常に格子点に来るわけじゃないと思うけど
- 194 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 23:30:50.22 ]
- 何が？
- 195 名前：デフォルトの名無しさん mailto:sage [2012/06/28(木) 23:57:54.20 ]
- 最適解が
- 196 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 01:35:35.32 ]
- >>191
ちょうど数をとっても隙間ができる
その分まだ距離は広がれる
- 197 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 03:44:55.03 ]
- いや、無理だろ
- 198 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 03:54:38.76 ]
- >>191の場合、４，５，６のケースで>>172と違いがでてくる
8以上でも不都合があるかもしれん
- 199 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 04:38:18.99 ]
- >>176で粒子法もどきでFA
- 200 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 04:40:13.84 ]
- 外縁部は円周上にへばりつかせて残りを内部にばらけさせるほうがいい
- 201 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 08:30:00.42 ]
- >>190
いや
無限遠という意味ではなく
無限循環？的な意味だった
「無限だけど閉じた宇宙」
みたいな
専門用語知らんのですまそ
- 202 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 10:50:05.35 ]
- >>196
無理。外周で幾つか点を動かせるかも知れんが、内部は動かせない。
- 203 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 11:22:06.93 ]
- >>191
8個の場合円はどこにどの大きさで取るの？
- 204 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 11:27:55.32 ]
- 円に内接する、正六角形に正三角形を一つたした、↓の図形の頂点が解になるだろうな。
＿＿＿
／ ＼／
＼＿／
これより頂点間距離が大きいのがあったら提示してくれ。
- 205 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 12:11:49.17 ]
- 隙間だらけじゃん
www.dotup.org/uploda/www.dotup.org3142869.png
例えばこれらの点をこう動かせばどの点との距離をとっても広がるか変わらないかだね
狭まる箇所は無いね
- 206 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 12:15:14.96 ]
- 存在しないファイル。
- 207 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 12:21:33.24 ]
- すまんうｐし直した
www.dotup.org/uploda/www.dotup.org3142891.png
- 208 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 12:26:58.00 ]
- >>207
一番下の二つの頂点も動かさないと、距離変わらないぞ。
そして全部動かした後で、距離が広がってるかも確認してくれ。
- 209 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 12:28:41.92 ]
- >>204
その図形を円に内接させた状態で、外周に近い一部の頂点は更に円周方向に移動できそうだよ。
要は>196か。
でもまぁ、>176で闇雲に求めるよりも>176の1で与えるべき初期値としてはいいのか。
- 210 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 12:40:20.28 ]
- 最小距離を最大化すればいいという考え方と
全ての点の組み合わせの距離の総和を最大化するという考え方の違いか
- 211 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 12:45:37.56 ]
- 帰ったら俺も作ってみるか
- 212 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 14:59:49.66 ]
- >>208
下二つも広げられるよ
- 213 名前：デフォルトの名無しさん mailto:sage [2012/06/29(金) 15:26:31.30 ]
- >>204
正七角形の頂点＋中心点
- 214 名前：デフォルトの名無しさん mailto:sage [2012/06/30(土) 00:07:19.12 ]
- >>170これは何に使うアルゴリズムなのかな
- 215 名前：デフォルトの名無しさん mailto:sage [2012/06/30(土) 00:10:50.60 ]
- サンプリングとか？
- 216 名前：デフォルトの名無しさん mailto:sage [2012/06/30(土) 00:25:55.72 ]
- どんなＮ角形も三角形に分割できるわけで２点の距離を同じにするなら近隣の３点を結ぶと正三角形になるような形が理想的だが
どんな２点でも等距離である必要はなく、すべての点の中で２点間距離が最小となる距離を円の範囲内で最大化するって問題だから
単純に正三角形の敷き詰めからの切り抜きでは実現できないってことか
ある正円Rがあり
Rの内側と円周上に合わせてＮ個の点が存在し
Ｎ個の点のうち任意の２点間の距離Ｄp [p=1,2,...,N*(N-1)/2]と定義したとき
Min(Dp)を最大にするＮ個の点の位置を求める
|
 |
