人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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


●質問者: ymlab
●カテゴリ:コンピュータ
✍キーワード:プログラム 言語
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● natsuakane
●100ポイント ベストアンサー

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

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

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

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

残った点をDとします。

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

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

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

URLはダミーです。

◎質問者からの返答

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

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

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

ありがとうございます。

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


2 ● 186
●50ポイント

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

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...

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

◎質問者からの返答

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

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

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

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

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

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

ーーー

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

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


3 ● hkrhr1
●50ポイント

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に線を引く

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

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

◎質問者からの返答

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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ