1404392810 ご相談です。というか頭の体操かもしれません。


・机の上にを5個のおはじきを無造作におきます。

このとき、おはじき同士を結んでできる図形のうちで、一番面積の大きい図形を見つけるアルゴリズムを考えよ。

また、その図形の面積を求めるアルゴリズムを求めよ。

おはじきの座標(X,Y)は分かっているものとする。


一番シンプルで美しい回答がでる事を楽しみしております。

もしかすると常識問題なのかもしれませんが、、
どうぞ宜しくお願い致します。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2014/07/03 22:06:50
  • 終了:2014/07/04 00:16:48

ベストアンサー

id:Sampo No.1

Sampo回答回数556ベストアンサー獲得回数1042014/07/04 00:04:20

一番大きい図形は凸多角形なので、面積を求めるのは簡単です。
凸多角形ABCDEの面積は△ABC+△ACD+△ADEと機械的に分割できますから各三角形をヘロンの公式で求積するだけです。

さて凸包を求めるアルゴリズムを、lang_and_engineさんご紹介のとは別のアプローチで。

こういうイメージでいきましょう。ピンが5本打たれた板に、水平にした定規を上から下ろしてきて、ピンにぶつかったらそこから時計回しに回していきます。ぶつかったことのあるピンに再びぶつかったら計算終了。

最初のピンは、Y座標が最大となるピンですね。ではそれ以降。
平面ベクトルで考えます。記法ですが、ベクトルXを長さで割って単位ベクトルにしたものを[X]と書くことにしましょう。

  1. 定規は初期で水平なので、定規ベクトルRは(1,0)
  2. 最初のピン(Aと名付けます)から各ピンへのベクトル AB, AC, AD, AEはすべて定規ベクトルの左側にはありません。
  3. なので、定規ベクトルの右側直近のものは、Rとなす角θが最小、言い換えればcosθが最大のものです。内積 R・[AB], R・[AC], R・[AD], R・[AE] を調べて最大のものが「次のピン」です。次のピンがBだったとしたら、定規ベクトルRは [AB]になります。
  4. すでに出会った点が出てくるまで3に戻って続けます。
id:hope_is_dream

とても分かりやすい説明をしていただきありがとうございます。
内積でポコポコ探していく様子が頭に浮かびました。
これなら僕でも実装できそうだと感じました。
参考にさせていただきます。
どうもありがとうございました。

2014/07/04 00:16:33
id:Sampo

高校の数学がものすごく実用的なことを教えてくれていることに気づいてもらえたらうれしいです。
図形絡みのプログラミングで迷ったときはベクトルと一言唱えると大抵なんとかなります。

2014/07/04 08:36:36
  • id:language_and_engineering
    問題の表現は,
    5つの座標が作る「凸包」のうち最大のものを求めよ
    という事で言い尽くされているんでしょうかね。
  • id:language_and_engineering
    凸包 アルゴリズム
    でググって,ソースコードが出てきました。
    2次元平面における計算機科学の,入門的な問題ですね。

    http://www40.atwiki.jp/spellbound/pages/2024.html
  • id:language_and_engineering
    計算機科学

    計算幾何学
  • id:hope_is_dream
    なんと!計算幾何学なんて分野があるのですね!
    やっと最近悩んでいた世界に出会えたかもしれません。
    本当にありがとうございます!
  • id:language_and_engineering
    積分幾何学も関係が深く、似た問題がある分野ですよ。
    ビュフォンの針とか…。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません