§Algorithm§


☆多角形(閉路)の作成〜散在した点のソート〜☆

 左図のようにバラバラに点在した点を線分で結び、 お互い交差することがないように多角形(閉路)を描画するには?


 これは意外に簡単で、互いの点の位置関係を調べ、ソート を用いるだけで実行できます。


 互いの座標の位置関係を調べるために、まず基準点を決めます。 基準点は、最も小さい 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


(参考書)

『アルゴリズムC 第3巻』
野平浩平、星守、佐藤創、田口東 共訳
近代科学社


(サンプルプログラムの動作確認)

機種 PC-9821V13S
OS Windows95
開発ツール Visual Basic Ver.4.0
更新日 00/08/08

ダウンロード Heiro.lzh(3.24KB)

Visual Basic Ver.5.0,Ver.6.0でも問題なく動作すると思います。
なお、掲載されているプログラムコード、およびプログラムファ イルが原因で生じた損害などに関して一切の責任を負うことはできません。

★掲載されているプログラムコード、 およびプログラムファイル、ソースファイルを無断で配布・転載することは、 原則として禁止です。


Algorithmインデックス トップ


Copyright(C)2000 Tomoya. All rights reserved.