C言語関係掲示板

過去ログ

No665 四角形を内包する多角形

[戻る] [ホームページ]
No.7372

アルゴリズムをおしえてください。
投稿者---hana(2003/06/13 09:32:44)


次のようなプログラムを作りたいのですが、どうやっていいのか
わかりません。とりあえず、アルゴリズムだけでもおしえていただけ
ないでしょうか?よろしくお願い致します。

入力データは多角形の座標のデータ、出力は四角形の座標のデータです。
四角形は多角形に内包されるように作っていきます。座標は多角形の
座標の一部と必ず一致します。一致というのは、x座標のみ、y座標のみ、
あるいは両方が多角形の頂点の座標と一致するということです。

最終的には複雑な凹凸のある多角形を比較的凹凸の少ない多角形に変形
したいと考えています。とりあえずは四角形から。。。
いまは多角形から四角形にするわけだから、頂点の数を減らして4つにする
という方向なのかな?って思ってます。

どうかよろしくお願い致します。

No.7375

Re:アルゴリズムをおしえてください。
投稿者---こん!(2003/06/13 11:31:14)


>最終的には複雑な凹凸のある多角形を比較的凹凸の少ない多角形に変形
>したいと考えています。とりあえずは四角形から。。。

まず多角形と四角形の定義をはっきり決めないとアルゴリズムも決まらないので
はないですか?
多角形
                A
                **
                * ****
               *      **** B
               *          **
               *            *
              H*             *
              *               *
            ***                *
      ******                    *
 G****                           *
   *                             **C
    *                         ***
     *                     ***
      *                 ***
       *              **D
        *              *
         *             *
         F**            *
            ****        *
                ****     *
                    **** *
                        ***E
 
 
こんな多角形が有ったらどの頂点を選択するのですか。
A−B−C−H?
A−B−C−G?
H−C−D−G?
・・・

その仕様を決めるのはあなたです。
『複雑な』とか『比較的』とかいう抽象的な表現ではあまりにも的が絞りきれな
いと思います。


No.7376

Re:アルゴリズムをおしえてください。
投稿者---hana(2003/06/13 11:51:14)


>まず多角形と四角形の定義をはっきり決めないとアルゴリズムも決まらないので
>はないですか?
多角形
              5****4
               *  *
      7       6*  *
       *********  *
       *          *
       *     **** * 3
       *     *2
       * *****
       0     1
 


>その仕様を決めるのはあなたです。
>『複雑な』とか『比較的』とかいう抽象的な表現ではあまりにも的が絞りきれな
>いと思います。
今はこのような多角形を考えています。座標の値はファイルに書いてあって、それを読み込むような形にしたいのです。四角形は小さくなるように
作っていきこの多角形に内包されることが条件です。四角形は作れる最大の面積のものを作ることも条件となります。


No.7377

Re:アルゴリズムをおしえてください。
投稿者---ちぇっこり(2003/06/13 12:07:31)


>
多角形
              5****4
               *  *
      7       6*  *
       *********  *
       *          *
       *     **** * 3
       *     *2
       * *****
       0     1
 

>

この多角形の例だと、どのような四角形になりますか?


>>作っていきこの多角形に内包されることが条件です。
>>四角形は作れる最大の面積のものを作ることも条件となります。

内包 とは、、すいません・・具体的に・・



No.7381

Re:アルゴリズムをおしえてください。
投稿者---hana(2003/06/13 13:13:39)


>>
多角形
              5****4
               *  *
      7       6*  *
       ---------  -
       -          -
       ------------ 3
       *     *2
       * *****
       0     1
 

>>
>
>この多角形の例だと、どのような四角形になりますか?
>
>
これだと真ん中の長方形の部分、わかりずらいですが-のぶぶんです。
内包とは内接するということで、外にできる四角形ではないということです。

>多角形とは何か。hanaさんが示した図を言葉で表してましょう。
>そしてその多角形をどのように変形していき最終的にはどのような
>形にしたいのでしょうか。それを言葉で表してみましょう。


 
多角形とは今はこのような形になっていますが、いろいろな形に応用させていきたいので、座標値をファイルから読み込んで座標を結んでつくるようにしたいです。内接するということは座標が一致するところに四角形の頂点があるということになります。一致するというのは、x座標のみ、y座標のみ、あるいは両方が一致するということです。
こんな感じでいいのでしょうか?

No.7378

Re:アルゴリズムをおしえてください。
投稿者---こん!(2003/06/13 12:13:50)


多角形
              5****4
               *  *
      7       6*  *
       *********  *
       *          *
       *     **** * 3
       *     *2
       * *****
       0     1
>今はこのような多角形を考えています。座標の値はファイルに書いてあって、そ

辺は必ず水平垂直?
この例でいうとどの頂点を取るのでしょうか?

と、ここまで書いて気がつきましたがここはC言語の掲示板でしたね。

アルゴリズムはご自分で考えた方がよろしいかもしれません。

このままやりとりを続けていてもなかなかC言語にはたどりつきそうにありませ
んので。考えたアルゴリズムをC言語で実現するには?の質問の方がここでは適
しているかもしれません。

或いは
『このアルゴリズム実現のためにここまでプログラムを組みましたがここが分か
りません。』の方がよろしいかもしれません。

No.7379

Re:アルゴリズムをおしえてください。
投稿者---hana(2003/06/13 12:18:28)



>アルゴリズムはご自分で考えた方がよろしいかもしれません。
>
>このままやりとりを続けていてもなかなかC言語にはたどりつきそうにありませ
>んので。考えたアルゴリズムをC言語で実現するには?の質問の方がここでは適
>しているかもしれません。
>
>或いは
>『このアルゴリズム実現のためにここまでプログラムを組みましたがここが分か
>りません。』の方がよろしいかもしれません。
わかりました。アルゴリズムを考えてからプログラムについての質問をするように致します。ありがとうございました。
またアルゴリズムが出来次第書き込みします。

No.7380

Re:アルゴリズムをおしえてください。
投稿者---TDa(2003/06/13 12:24:05)


>わかりました。アルゴリズムを考えてからプログラムについての質問をするように致します。ありがとうございました。
>またアルゴリズムが出来次第書き込みします。

やりとりをみていたんですが、アルゴリズムのアドバイスはできると思いま
すよ。
仕様を決めて下さい。

多角形とは何か。hanaさんが示した図を言葉で表してましょう。
そしてその多角形をどのように変形していき最終的にはどのような
形にしたいのでしょうか。それを言葉で表してみましょう。

実はその時点でアルゴリズムもできている気がします。



No.7388

Re:アルゴリズムをおしえてください。
投稿者---たいちう(2003/06/13 17:05:50)


かなり興味深い話題ですね。

辺は水平と垂直に限ると解釈して、既出の図形では、
0,1,7を含む長方形
3,6,7を含む長方形
3,4,5,6を含む長方形
の3つを調べ、最大の面積のものを見つけるということかな?

最大の長方形の頂点か辺は、元の頂点のどれかに接しているはずです。
そこで元の全ての頂点についてそれぞれ第1〜4象限を考えます。

例えば点6について第1象限を考えると、
6の第1象限の近傍を含む最大の長方形は3,4,5,6の長方形になります。
第2象限は多角形外なので除外。
第3象限では3,6,7の長方形。
第4象限では3,4,5,6か3,6,7のいずれか。

全ての頂点について調べると、最大の長方形は1度以上は出てきます。

これをソースにするのも一仕事でしょうけど。
私の間違っているところやより洗練された方法はあるでしょうか。

No.7390

Re:アルゴリズムをおしえてください。
投稿者---こん!(2003/06/13 17:14:44)


>辺は水平と垂直に限ると解釈して、既出の図形では、
>0,1,7を含む長方形
>3,6,7を含む長方形
>3,4,5,6を含む長方形
>の3つを調べ、最大の面積のものを見つけるということかな?
>
>最大の長方形の頂点か辺は、元の頂点のどれかに接しているはずです。
>そこで元の全ての頂点についてそれぞれ第1〜4象限を考えます。

ちなみに例の図以外に以下のような図の場合(A)や(C)は対象外になるのでしょう
かね?
      5********4         5********4        5xxxxxxxx4
       *      *           *      *          x      x
  7   6*      *      7   6*      *     7   6x      x
   xxxxxxx    *       ・・・・・・・・・・・・      ****x      x
   x     x    *       ・          ・      *   x      x
   x     x*****3      ・・・・・・・・・・・・3     *   xxxxxxxx3
   x     x2           *     *2          *     *2
   xxxxxxx            *******           *******
   0     1            0     1           0     1
 
       (A)                (B)               (C)
 
hanaさんいかがでしょう?

No.7391

Re:アルゴリズムをおしえてください。
投稿者---hana(2003/06/13 17:21:11)


>そこで元の全ての頂点についてそれぞれ第1〜4象限を考えます。
>
>ちなみに例の図以外に以下のような図の場合(A)や(C)は対象外になるのでしょう
>かね?
      5********4         5********4        5xxxxxxxx4
       *      *           *      *          x      x
  7   6*      *      7   6*      *     7   6x      x
   xxxxxxx    *       ・・・・・・・・・・・・      ****x      x
   x     x    *       ・          ・      *   x      x
   x     x*****3      ・・・・・・・・・・・・3     *   xxxxxxxx3
   x     x2           *     *2          *     *2
   xxxxxxx            *******           *******
   0     1            0     1           0     1
 
       (A)                (B)               (C)
 
hanaさんいかがでしょう?
対象外にならないです。頂点がすべてもとの多角形の中に入っているので・・・。


No.7392

返事が遅れると思います。
投稿者---hana(2003/06/13 17:33:40)


すみませんが、時間がなくなりました。
家でネットにつないでいないので次に書き込めるのは
月曜日になるかもしれません。
申し訳ありませんが、アドバイスなど、どんどん
お願い致します。