Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

配線の方法 #9

Open
HAYASAKA-Ryosuke opened this issue Oct 23, 2014 · 6 comments
Open

配線の方法 #9

HAYASAKA-Ryosuke opened this issue Oct 23, 2014 · 6 comments

Comments

@HAYASAKA-Ryosuke
Copy link
Owner

どうやって配線を表現するか．
基本的にピンとピンを結ぶ線は次のようなルールで表現することが多い
・基本的に直線
・曲げるときは90度
・線どうしを結ぶときには交わりを示す交点を打つ．
今回はこれらのルールに則った配線を行ないたいが，具体的に自動的にどう処理するか考える必要がある．
@HAYASAKA-Ryosuke
Copy link
Owner Author

図をグリッド化して処理するとか．
その場合細かさはどの程度にすべきか．

@HAYASAKA-Ryosuke
Copy link
Owner Author

ざっくりと方法を書いておく
・グリッドは等間隔
・配線は配線位置から上下左右のどれか

処理
・配線位置から見た上下左右のグリッドと配線終了位置までの距離を求める
・そのなかでもっとも近いグリッドに線を伸ばす．
・基本的にはこの繰り返しで距離が0になれば配線終了
・伸ばすときに他の配線とぶつかる箇所があれば次に近いグリッドを通る
・どのグリッドもぶつかるのであれば一度だけ交わるような配線を引く(ただし二度連続はダメ)
・それでも無ければ現在のグリッド位置は間違えなので一つ前のグリッドのうち次に距離が短い方を選択して探索する．

単純なループで調べたいところだけど計算量が心配

@HAYASAKA-Ryosuke
Copy link
Owner Author

networkxをつかえば最短のノードを通るような経路を出力してくれるので，ルート検索にはこれをつかう．

@HAYASAKA-Ryosuke
Copy link
Owner Author

グリッドはとりあえず対数に横，縦それぞれの値を代入してそれを四捨五入した整数だけ等間隔に分割する．こうすることで距離が短いときには小さな値に分割されるし，距離が遠いときも分割数が過剰に多くなるのを防ぐ．

@HAYASAKA-Ryosuke
Copy link
Owner Author

とりあえずグリッド対数やめて10でわったものにした．
10で割ったのはある程度線の長さを稼ぎたかったから(そうしないと斜め線に見えそう)

@HAYASAKA-Ryosuke
Copy link
Owner Author

ICが描画されているエリアをもとめて，その範囲にあるグリッドの点リストをつくる．
描画するときにはそこを通らないようにさせる．

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@HAYASAKA-Ryosuke