C言語での開発環境での線の扱い方

C言語での開発環境での線の扱い方

TSP問題を考えています。

１：2次元配列で座標(今回は5点程度)を用意。
(例)sorce[4][4]={{0,1},{3,8},{2,4},{2,7},{8,2}}
２：任意の点をスタート位置に設定。
３：座標同士の距離を計測(ユークリッド距離)。
４：(２)のうち最短距離を選ぶ。

ここまでできています。
これからアルゴリズムとしては、

５：任意のスタート位置から最短距離にある座標を線で繋ぐ。
６：繋いだ先の座標から最短距離にある座標を線で繋ぐ(これを繰り返す。)。
７：もし線の交差があれば、交差している座標間で線を入れ替える。

この処理を行いたいのですが、まず線を引くような、処理をどうやったらC言語で行えるのか(実際に線を引いて出力するわけではありません。)がわかりません。

ですので、5番の方法だけでも結構ですので、教えてください。よろしくお願いします。

No.1 ベストアンサー 回答者： t_nojiri 回答日時： 2010/07/12 14:26

線の描画の仕方。

色々な方法が有ると思いますが、windowsならdirectx、LinuxならXlib使うのが一般的かと思います。

http://www.h2.dion.ne.jp/~takusoft/directx8/d3d/ …
http://ja.wikipedia.org/wiki/Xlib

まあ、ちょっとCとかC++だけでは無いような説明になりますが、使い方はX,Y軸の頂点間２点を結ぶ物になります。

No.2 回答者： kmee 回答日時： 2010/07/12 19:06

> sorce[4][4]={{0,1},{3,8},{2,4},{2,7},{8,2}}

これ、おかしくないですか?
5要素の[2要素の配列]の配列で初期化してるのに、
4要素の[4要素の配列]の配列
になってますよ。



「線」を引くのに必要な情報は「両端の点」です。
なので、その両端を表せるようなデータ構造を考ればよいです。
例1)struct Line{ double x1,y1,x2,y2; } line[N]と宣言
→ i番目の線は 座標(line[i].x1,line[i].y1)から座標(line[i].x2,line[i].y2)まで

今回のケースだと、高々数個の決まった座標しか使わないので、その「座標番号」を使えばよいでしょう。
例2) struct Edge { int snode, enode; } edge[N] ;
→ i番目の線は ノードsnodeから ノードenodeまで

プログラムの作り方次第では、距離も格納できる型にした方がいいかもしれませんし、配列でなくリストで表現した方がいいかもしれません。