パターンをチェックするには？
解決TList に①〜順に TPoint でX座標値、Y座標地が
道路情報のデータとして入力されています。
図を見ると、【例１】 【例２】は
道路情報として正しいことがわかりますが、
【例３】はおかしいことがわかります。
ところが、この正誤判断をプログラムで行うとする場合
どうやっていいのかアルゴリズムがわかりません。
すみませんが教えてください
【例１】 【例２】 【例３】
②─③ ②─────③ ②───③
│ │ │ │ │ │
│ │ │ ⑨─⑧ │ │ │
│ │ │ │ │ │ │ │
│ │ ⑥─┤ ├─⑦ │ ⑤───┼───④
│ │ │ │ │ │ │ │
│ │ ⑤─┤ ├───④ │ │
│ │ │ │ │ │
│ │ │ │ ⑥───┼───⑦
│ │ │ │ │ │
│ │ │ │ │ │
│ │ │ │ │ │
①─④ ①─⑩ ①───⑧
何がどうおかしいのか、よくわからないのですが・・・
どこがどうおかしいのか、詳しく書かないとなかなかレスは
付かないと思いますよ。色々な分野の人たちがいますし。
また、Delphiに直接関係無いことは、やはり基本的にはレスは
付かないと思います。
アルゴリズム用の掲示板とかがあれば、そちらがいいと思います。
（無いのかな？）
>【例３】はおかしいことがわかります。
そうかな？
道路が平面上で交差していても、立体交差あるいはトンネルであれば
おかしくないと思うよ。
要は平面上という条件で、直線が交差しているかどうかを判定したいということかな？
すみません。
説明不足なんですね。
道路の立体交差を上から見ている状態のデータで、
ラインはガードレールだと思ってもらうとわかりやすいでしょうか？
囲まれた部分が車の走る部分です。
【例１】は直線道路で、
【例２】は立体交差の道路です。
④〜⑤、⑥〜⑦、はデータとしてはつながっているので
図に描くと線は上の道路に隠れていますが、④-⑦から⑤−⑥に
道路があると考えます。
【例３】は直線道路の一部が左にずれたようななんとも表現のしにくい
パターンです。
この説明でわかってもらえるでしょうか?
よろしくお願いします。
条件次第さんへ、
要するにデータが TList でポイント型のデータとして座標は有るのですが
上下の情報が入っていません。
実際にデータを平面状に書いていくと上記のようになった場合に
【例２】の場合ですと、向かって下側がスタート地点で、
向かって左側がゴール地点としたばあいに
①−⑩ → ②−⑨ → ③−⑧ → ⑦−④ → ⑤-⑥
という風に車が移動できる道のデータかを判定したいのです。
よろしくお願いします。
おもしろいですね、この問題。座標の具体的な数値に依存するのではなく
なんというか、トポロジー（位相数学）の問題ですね。
わたしにはまったくわからないですけど、直感的には、①から最後の点まで
を結んで多角形をつくったとき、それを塗りつぶしたところを通ることが
できるかどうか、みたいですね。例３だけが、頂点を接する三つの多角形に
なって、通ることができませんね。回答でなくてすみません。
回答でないのに連投すみません。
ずっと昔、洞窟の迷路問題というのがあって、これを解くには、
「入り口の壁と出口の壁はつながっている」という原則を
使えばよい、と知りました。この問題も、にているような気がします。
例①と②は壁を伝わってぐるりと元に戻ってきます。例③は、メービウスの環
のように、壁の内側と外側が入れ替わっています。
Delphiとほとんど関係ないので、どこかのアルゴリズムや数学関係の掲示板で
質問された方がよいと思います。
上下関係のデータが必要ですよね。
で、例えば⑥から⑦へ行く間に自分の道が下側という
ポイントを２回通るかどうかで判断するとか・・・。
いろんなパターンがあるので完璧じゃないですけど＾＾；
道路の形を追っていって道路幅が０以下になっては駄目と
言う問題でいいのでしょうか。
TSさん、それでいいと思います。
で問題は、座標値からどうやって「道路の形を追っていって道路幅が０以下」である
ことをしることができるか、だと。
>>大熊猫
条件にもよると思いますが
・タイルのように正方形のマスが並んでいる
・道の幅は１マス
という条件を与えるなら、道のパターンはかなり有限だと思います。
幅が１マスですから、あるマスから上下左右に直線のマスが連続していて、
それらの繰り返しと考えられるかと。うんとさんの言われるように、多角形を
作って、その図形がつながった直線の繰り返しで構成されてるかどうかを判定
すれば良いかと思います。
ただし、Ｔ字路みたいなものや、ロータリーみたいなループしている部分が
あるとこの方法は複雑になって使えないかもしれません。
皆さんどうもありがとうございます。
＞＞deldelさん＆うんとさん
「座標値からどうやって「道路の形を追っていって道路幅が０以下」である」
そうなんです。それが問題なんですよ。
１回交差したから＋１（階層のフラグ）にするとかしても
うまくいかなかったです。複雑になると＋１なのか−１なのかが
判断できなくって・・・
＞＞さなみさん
道幅は一定ではありませんので１マスで
構成されているわけではないんですよね。
それに、Ｔ字路というより分岐点（三叉路など）が存在します。
無理っぽいので、他を探してみます。
参考になるURL等ありましたら教えてください。
回答になっていませんが、これは、仕様に不備があるのではないでしょうか？
はずしているかもしれませんが、たとえば
１．道路の両端にはガードレールがある。
２．ガードレールはx.y座標を持つドットの連続で示される。
３．道幅は一定ではないが、連続するドットの間隔は、最も狭い道路の幅
よりも、かなり小さい。
４．道が交叉している場合、下にある道のガードレールは表示しない。
５．道路は全て水平／垂直方向に走っている。斜めには走っていない。
具体的には、
＼＼
＼＼こんな道も
─┐
┐└┐
└┐│こうミクロに解釈するよ。
こんな仕様であれば、ケーニヒスベルクの橋レベルであるから、簡単な
プログラムで解決する。
・・・ここまでは問題ないですよね。
>TList に①〜順に TPoint でX座標値、Y座標地が
>道路情報のデータとして入力されています。
ですが、【例２】の場合、下の【例２Ａ】なのか【例２Ｂ】なのか
が不明です。それとも【例２Ｂ】の場合は【例２Ｃ】（座標略）
のように、明示的に切り離した座標が与えられますか？
【例２Ａ】
②─────③
│■■■■■│。
│■⑨─⑧■│
│■│ │■│
│■│ │■│
⑥─┤■├─⑦■│
│■│■│■■■│
⑤─┤■├───④
│■│
①─⑩
【例２Ｂ】
②─────③
│■■■■■│
│■⑨─⑧■│
│■│ │■│
│■│ │■│
⑥─┼─┼─⑦■│
│■│■│■■■│
⑤─┤■├───④
│■│
①─⑩
【例２Ｃ】
②─────③
│■■■■■│
│■⑨─⑧■│
│■│ │■│
○─○ │■│
⑥─○─○─⑦■│
│■│■│■■■│
⑤─┤■├───④
│■│
①─⑩
一直線ならば・・・・
終了点が短いほうに曲がっていれば正しく、終了点が長いほうに
まがっていれば間違いと判断すれば可能かと思います。
Ｔ字路が有る場合には無理です。
斜線が有る場合すこし計算が面倒になりそうです。
【例２】 の場合
①−② に対応する ⑩−⑨ 短い⑨のほうへ曲がっている
②−③ に対応する ⑨−⑧ 短い⑧のほうへ曲がっている
・・
【例３】 の場合
①−② に対応する ⑧−⑦ 長い②のほうへ曲がっている
| ツイート |  |