その４つの点を線分で結ぶとき、各線分が交わらないようにしたいです。（凸四角形を作りたい）
これを、プログラム言語で実装する場合、どういう風にすればよいのでしょうか。
こんな方法があるかと思います。
まず、任意の一点Aを選びます。
点Aを原点とした相対座標（平行移動させる）で各点と原点の角度のsin,cosから角度を求め、一番小さい角度になった点をBとします。
次に点Bを原点とした相対座標で残りの点の角度を求め、角度が小さい方の点をCとします。
残った点をDとします。
A→B→C→Dと線を結んでいけば、X軸が右方向でY軸が下方向の座標系であれば時計回りに線を結べます。
説明がざっくりで分かりにくくて申し訳ありません。
http://q.hatena.ne.jp/1162304205
URLはダミーです。
こんな方法があるかと思います。
まず、任意の一点Aを選びます。
点Aを原点とした相対座標（平行移動させる）で各点と原点の角度のsin,cosから角度を求め、一番小さい角度になった点をBとします。
次に点Bを原点とした相対座標で残りの点の角度を求め、角度が小さい方の点をCとします。
残った点をDとします。
A→B→C→Dと線を結んでいけば、X軸が右方向でY軸が下方向の座標系であれば時計回りに線を結べます。
説明がざっくりで分かりにくくて申し訳ありません。
http://q.hatena.ne.jp/1162304205
URLはダミーです。
回答ありがとうございます。
角度からラジアンを求めていくのですね。
同じラジアンの場合は、どっちでもよいという処理を加えるとうまく実装できそうです。
ありがとうございます。
試してみることにします。
言語の指定もなくプログラムを書くのが面倒なのでアルゴリズムの概要だけ答えます.
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が交わるかどうかを調べて交わっているものがあればそれを採用し凸四角形を作ります.
アルゴリズムをまとめると
となります.
線分交差判定アルゴリズムは, http://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/Intersectio...
等を参照してください. 参照先のアルゴリズムは重なっているものを交差していると判定しないので使いやすいかと.
回答ありがとうございます。
その方法を最初に考えたのですが、もっとエレガンスな方法はないのかなぁ。と思って、
調べてみたのですがなかなか発見できなかったので、質問をしました。
自分では、それぞれ点の中点を原点として、象限で考えたらいけるのかな。とか、中点より、複素平面上で回転させていけばよいのか。とか思ったりしたのですが・・・。
角度を求める方法が上手く作ることができなかったら、試してみます。
ありがとうございました。
ーーー
言語は、特に指定せず、プログラミングで実装しようとしていることを明確にするために書いたのです。
ちなみに、言語は、VC6.0 SDK です。
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に線を引く
--------------------------------------
以上。この場合、凹(矢印形)となってしまう場合も含まれています。
回答ありがとうございます。
一度試してみることにします。
皆さんありがとうございました。
皆さんの貴重な意見を参考にしてがんばってみます。
回答ありがとうございます。
角度からラジアンを求めていくのですね。
同じラジアンの場合は、どっちでもよいという処理を加えるとうまく実装できそうです。
ありがとうございます。
試してみることにします。