- データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
302 ：デフォルトの名無しさん[sage]：2014/03/26(水) 03:06:58.26 ID:r7VC3H2x - ２Ｄ上の多角形を検出するアルゴリズムで詰まりました。助けてください。
各ラインを 56,80-120,100 という２頂点のデータで複数持っています。
とある２Ｄの座標が多角形を構成しているラインの中か外かをチェックする必要があります。
中か外かをチェックする処理は作成したのですが、そもそも多角形を構成しているのかどうなのかという処理で、
良いアルゴリズムが浮かびません。
多角形の頂点数は３点以上です。
何か良いアルゴリズムは無いでしょうか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
303 ：302[]：2014/03/26(水) 03:24:55.09 ID:r7VC3H2x - 追加です。
各ラインの交差はありません。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
305 ：302[sage]：2014/03/26(水) 05:36:23.23 ID:r7VC3H2x - >>304
ありがとうございます。
頂点ＡＢＣＤＥＦＧと頂点ＢＣＤＥＦＧＡは同じなのですが、チェックがめんどくさくて、、、
閉じているかチェックしたいだけなので、力技ではなく何かテクニックがあったら教えていただきたいです。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
307 ：302[sage]：2014/03/26(水) 06:56:33.51 ID:r7VC3H2x - 条件出さないんで、助けてください＞＜
あえて出すとすれば、同じ頂点を共有した別の多角形が存在するという条件でしょうか。
条件出しちゃいました。。。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
309 ：302[sage]：2014/03/26(水) 09:04:50.88 ID:r7VC3H2x - >>308
ありがとうございます。
難しそうですね。。。
実装時間に制約があるので、１頂点から２線以上出せないという仕様を一つ追加して乗り切りたいと思います。
|
|