|
|
 |
互いの座標の位置関係を調べるために、まず基準点を決めます。
基準点は、最も小さい y値( = y0とする)をもつ頂点とします。 そして、y = y0 の直線を仮想的に引き、その直線と、 基準点と各頂点を結ぶ線分による角度αを各点につき求めます。 基準点に「最も小さい y値( = y0)をもつ頂点」を選んだ理由は、 その角度が 0〜180度 に限定されるようにするためです。こうしておくと、 プログラムが非常に簡略化されます。角度αは、左下記の式により求めます。 最後に、その角度αに対して各点を昇順あるいは降順にソートすれば、 多角形が描かれるように点が順序通り並びます。 |
| 下のコードで描画される多角形は、基準点にのみ依存します。従って必ずしも意図した多角形が描かれるとは 限りません。また、基準点と2つ以上の点が一直線上にのるとき正確に多角形が 描かれるとは限りません。 |
'閉路のための構造体
Private Type POSITION
x As Double 'x座標
y As Double 'y座標
r As Double '基準点水平方向に対しての位置(0〜2)
End Type
'POSITIONの配列中で最も小さいy値を含む配列番号を求める
'PosData() 頂点データが入った配列
'pdCount 頂点の数
Private Function GetMinPosY(PosData() As POSITION, _
pdCount As Long) As Long
Dim ret As Long
Dim i As Long
ret = 0&
For i = 1& To pdCount - 1&
If PosData(i).y < PosData(ret).y Then ret = i
Next
GetMinPosY = ret
End Function
'基準点水平方向に対しての位置(0〜2)を求める
'その位置(0〜2)に90をかけると角度が求まる
'StandardPos 基準点
'TargetPos 角度を求める点
Private Sub GetPosition(StandardPos As POSITION, _
TargetPos As POSITION)
Dim dx As Double, dy As Double 'x,y成分の差
Dim Pos As Double '基準点に対しての位置
dx = TargetPos.x - StandardPos.x
dy = TargetPos.y - StandardPos.y
Pos = Abs(dy) / (Abs(dx) + Abs(dy))
If (dx < 0# And dy >= 0#) Then Pos = (1# - Pos) + 1#
TargetPos.r = Pos
End Sub
Private Sub SubSort(data1 As POSITION, data2 As POSITION)
Dim temp As POSITION
temp.x = data2.x: temp.y = data2.y: temp.r = data2.r
data2.x = data1.x: data2.y = data1.y: data2.r = data1.r
data1.x = temp.x: data1.y = temp.y: data1.r = temp.r
End Sub
'閉路作成のためのソート本体
'PosData() 頂点データが入った配列
'pdCount 頂点の数
Private Sub SortPosition(PosData() As POSITION, pdCount As Long)
Dim MinY As Long
Dim i As Long, j As Long
'最小のy値を含む配列番号を求める
MinY = GetMinPosY(PosData, pdCount)
'それを最初の要素とする
Call SubSort(PosData(0), PosData(MinY))
PosData(0).r = 0#
'各頂点の基準点水平方向に対しての位置(0〜2)を求める
For i = 1& To pdCount - 1&
Call GetPosition(PosData(0), PosData(i))
Next i
'求めた位置に対して、挿入法を用いて昇順ソートする
'0番目は基準点なので、ソートでは1番目が最初の要素である
j = 1& + 1&
'最後の要素まで
Do While j < pdCount
i = j - 1&
'1番目の要素まで
Do While i >= 1&
If PosData(i + 1&).r < PosData(i).r Then
Call SubSort(PosData(i), PosData(i + 1&))
Else
Exit Do
End If
i = i - 1&
Loop
j = j + 1&
Loop
End Sub
|
|
（参考書） 『アルゴリズムＣ 第３巻』 野平浩平、星守、佐藤創、田口東 共訳 近代科学社 |
| 機種 | PC-9821V13S |
| OS | Windows95 |
| 開発ツール | Visual Basic Ver.4.0 |
| 更新日 | 00/08/08 |
Visual Basic Ver.5.0,Ver.6.0でも問題なく動作すると思います。
なお、掲載されているプログラムコード、およびプログラムファ イルが原因で生じた損害などに関して一切の責任を負うことはできません。
★掲載されているプログラムコード、 およびプログラムファイル、ソースファイルを無断で配布・転載することは、 原則として禁止です。