任意の点が4つあります。

その4つの点を線分で結ぶとき、各線分が交わらないようにしたいです。(凸四角形を作りたい)

これを、プログラム言語で実装する場合、どういう風にすればよいのでしょうか。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/10/31 23:16:49
  • 終了:2006/11/01 16:24:16

ベストアンサー

id:natsuakane No.1

natsuakane回答回数22ベストアンサー獲得回数22006/11/01 00:30:19

ポイント100pt

こんな方法があるかと思います。

まず、任意の一点Aを選びます。

点Aを原点とした相対座標(平行移動させる)で各点と原点の角度のsin,cosから角度を求め、一番小さい角度になった点をBとします。

次に点Bを原点とした相対座標で残りの点の角度を求め、角度が小さい方の点をCとします。

残った点をDとします。

A→B→C→Dと線を結んでいけば、X軸が右方向でY軸が下方向の座標系であれば時計回りに線を結べます。

説明がざっくりで分かりにくくて申し訳ありません。

http://q.hatena.ne.jp/1162304205

URLはダミーです。

id:ymlab

回答ありがとうございます。

角度からラジアンを求めていくのですね。

同じラジアンの場合は、どっちでもよいという処理を加えるとうまく実装できそうです。

ありがとうございます。

試してみることにします。

2006/11/01 16:15:59

その他の回答(2件)

id:natsuakane No.1

natsuakane回答回数22ベストアンサー獲得回数22006/11/01 00:30:19ここでベストアンサー

ポイント100pt

こんな方法があるかと思います。

まず、任意の一点Aを選びます。

点Aを原点とした相対座標(平行移動させる)で各点と原点の角度のsin,cosから角度を求め、一番小さい角度になった点をBとします。

次に点Bを原点とした相対座標で残りの点の角度を求め、角度が小さい方の点をCとします。

残った点をDとします。

A→B→C→Dと線を結んでいけば、X軸が右方向でY軸が下方向の座標系であれば時計回りに線を結べます。

説明がざっくりで分かりにくくて申し訳ありません。

http://q.hatena.ne.jp/1162304205

URLはダミーです。

id:ymlab

回答ありがとうございます。

角度からラジアンを求めていくのですね。

同じラジアンの場合は、どっちでもよいという処理を加えるとうまく実装できそうです。

ありがとうございます。

試してみることにします。

2006/11/01 16:15:59
id:smoking186 No.2

186回答回数74ベストアンサー獲得回数62006/11/01 00:32:52

ポイント50pt

言語の指定もなくプログラムを書くのが面倒なのでアルゴリズムの概要だけ答えます.

4点をpi(i=1,2,3,4)とします.

逆の発想で線分が交わるかどうかを考えます.

線分p1-p2と線分p3-p4が交わりかつ重なっていない場合には, 四角形p1 p3 p2 p4は凸四角形になります (証明は幾何学か計算幾何学の本に載っていると思います).

なので線分p1-p2と線分p3-p4, 線分p1-p3とp2-p4, 線分p1-p4と線分p2-p3が交わるかどうかを調べて交わっているものがあればそれを採用し凸四角形を作ります.

アルゴリズムをまとめると

  1. p1-p2とp3-p4の交差判定
    • 交わったら凸四角形p1 p3 p2 p4を描く
    • 交わらなかったら次へ
  2. p1-p3とp2-p4の交差判定
    • 交わったら凸四角形p1 p2 p3 p4を描く
    • 交わらなかったら次へ
  3. p1-p4とp2-p3の交差判定
    • 交わったら凸四角形p1 p2 p4 p3を描く
    • 交わらなかったら凸四角形が作れないと判断する

となります.

線分交差判定アルゴリズムは, http://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/Intersectio...

等を参照してください. 参照先のアルゴリズムは重なっているものを交差していると判定しないので使いやすいかと.

id:ymlab

回答ありがとうございます。

その方法を最初に考えたのですが、もっとエレガンスな方法はないのかなぁ。と思って、

調べてみたのですがなかなか発見できなかったので、質問をしました。

自分では、それぞれ点の中点を原点として、象限で考えたらいけるのかな。とか、中点より、複素平面上で回転させていけばよいのか。とか思ったりしたのですが・・・。

角度を求める方法が上手く作ることができなかったら、試してみます。

ありがとうございました。

ーーー

言語は、特に指定せず、プログラミングで実装しようとしていることを明確にするために書いたのです。

ちなみに、言語は、VC6.0 SDK です。

2006/11/01 16:20:24
id:hkrhr1 No.3

hkrhr1回答回数235ベストアンサー獲得回数122006/11/01 15:52:11

ポイント50pt

http://q.hatena.ne.jp/1162304205

urlはダミーです。

 各点のxy座標がわかっているものとして、数学などを使わずに判断します。

--------------------------------------

1) x座標の最も小さい方から順番に点1,2,3,4とする。

case1) 点2のy座標が点1のy座標より大きいとき

       点3,4の内y座標が大きい方を点3

           y座標が小さい点を点4

   とする

case2) 点2のy座標が点1のy座標より小さいとき

       点3,4の内y座標が大きい方を点4

           y座標が小さい点を点3

   とする

できた点1,2,3,4の順に線を引く。

4から1に線を引く

--------------------------------------

 以上。この場合、凹(矢印形)となってしまう場合も含まれています。

id:ymlab

回答ありがとうございます。

一度試してみることにします。

皆さんありがとうございました。

皆さんの貴重な意見を参考にしてがんばってみます。

2006/11/01 16:23:33
  • id:smoking186
    1番のアルゴリズムは
    p1=(0,0), p2=(4.0), p3=(0,4), p4=(1,1)
    の場合どう処理するんでしょうか?
    この例だとどうやっても凹四角形が出来るんですが.
  • id:natsuakane
    実は、1番のアルゴリズムは、その場の閃きで思いついたものです…
    p1=(0,0), p2=(4.0), p3=(0,4), p4=(1,1)の場合、
    どうやっても凹四角形が出来る=全ての線分は交わりません。
    この場合、1番のアルゴリズムだと各点を結んで出来る凹四角形の3パターンのうちの1つになります。
    凹四角形になってしまうか凸四角形が出来るかを判定する方法は、
    どの3点を結んで三角形を作っても4点目が三角形の外側にあれば凸四角形が出来る、
    というくらいしか閃きません。
    閃きで思いついただけのアルゴリズムなので、他にも致命的欠陥があるかもしれません。
    3番のアルゴリズムが一番単純で良さそうですね。
  • id:smoking186
    角度を覚えておいて, 四角形を作った後に内角に180度を超えるものがあったら開始する点を変えてやり直し.
    4点どこから開始してもダメだったら凹四角形と判断.

    "角度が小さい"の定義が分からないので正当性は確認できませんが. こんな感じでどうでしょう.
  • id:hkrhr1
     一般に4点を任意に選んだ場合、凹四角形もその中に含まれてしまうのは自明です。こうした事をさけるため、Adobeは、PostScriptにおいて、多角形は三角形の集まりと見なし、3点で定義を繰り返して表す様にしています。三角形なら例外無く塗り絵が可能ですから...。
  • id:ymlab
    たくさんの参考になるご意見ありがとうございます。

    私なりにも考えてみまして、こんな方法を考えてみました。

    任意の点を4つ取ったとき、それぞれを結ぶ線分を引いたとき、線分の和が一番短い組み合わせを取る。

    です。この命題が成立するか、今証明中です・・・。
    とりあえず、平行四辺形、長方形(正方形)、台形までは証明できたのですが・・・。

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

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

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

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