|
ある点が、三角形や多角形の内部の点であるかを判定します。
|
| 3点の平均値である中心は必ず三角形の内部にある |
|
難しい判定のようにも見えますが、三角形による包含判定に関しては
簡単に行うことができます。 「幾何アルゴリズムの神髄は『解釈』にあり」 ということで、上の定義を用います。 三角形による包含判定は、 「三角形を構成する3点を通る3直線を境界線として ある点Pと三角形の中心がその3直線に対して、 同じ側に存在すれば、ある点Pは三角形に包含している」 と考えることができます。 つまり、3直線とある点P,中心を結ぶ線分の交差判定を 行い、どれも交差しなければ、ある点が三角形に包含していることになります。  |
'構造体
Private Type POINT
x As Double
y As Double
End Type
'座標 p1,p2 を通る直線と座標 p3,p4 を結ぶ線分が交差しているかを調べる
'戻り値
'= 0 - 直線上に線分の1点 or 2点がある
'< 0 - 直線と線分が交差する
'> 0 - 直線と線分は交差しない
Private Function intersectM(p1 As POINT, p2 As POINT, p3 As POINT, p4 As POINT) As Double
intersectM = ((p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x)) * _
((p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x))
End Function
'ある点が三角形内の点であるかどうかを判定する
'tp1,tp2,tp3 三角形を構成する点
'xp ある点
'ある点が三角形内の点であれば True,外の点であれば False を返す
'ただし、三角形の境界線上の点に対しては、Trueを返す
Public Function PosIncludeTri(tp1 As POINT, tp2 As POINT, _
tp3 As POINT, xp As POINT) As Boolean
Dim c As POINT
'与えられる三角形の3点のチェック
'3点が一直線上にある(三角形ではない)とき、「包含しない」と判定
If ((tp1.x - tp3.x) * (tp1.y - tp2.y) = (tp1.x - tp2.x) * (tp1.y - tp3.y)) Then
PosIncludeTri = False: Exit Function
End If
'三角形の平均値を求める
c.x = (tp1.x + tp2.x + tp3.x) / 3#
c.y = (tp1.y + tp2.y + tp3.y) / 3#
'3点の中心とある点を結ぶ線分が三角形を構成する直線と交差するならば、
'ある点は三角形に包含していない
If (intersectM(tp1, tp2, xp, c) < 0#) Then PosIncludeTri = False: Exit Function
If (intersectM(tp1, tp3, xp, c) < 0#) Then PosIncludeTri = False: Exit Function
If (intersectM(tp2, tp3, xp, c) < 0#) Then PosIncludeTri = False: Exit Function
PosIncludeTri = True
End Function
|
|
'ある点が三角形内の点であるかどうかを判定する-より簡単に
'tp1,tp2,tp3 三角形を構成する点
'xp ある点
'ある点が三角形内の点であれば True,外の点であれば False を返す
'ただし、三角形の境界線上の点に対しては、Trueを返す
Public Function PosIncludeTriEx(tp1 As POINT, tp2 As POINT, _
tp3 As POINT, xp As POINT) As Boolean
'与えられる三角形の3点のチェック
'3点が一直線上にある(三角形ではない)とき、「包含しない」と判定
If ((tp1.x - tp3.x) * (tp1.y - tp2.y) = (tp1.x - tp2.x) * (tp1.y - tp3.y)) Then
PosIncludeTriEx = False: Exit Function
End If
'各辺を境界線である直線として、それに対する頂点とある点を
'結ぶ線分がその直線と交差するならば、ある点は三角形に包含していない
If (intersectM(tp1, tp2, xp, tp3) < 0#) Then PosIncludeTriEx = False: Exit Function
If (intersectM(tp1, tp3, xp, tp2) < 0#) Then PosIncludeTriEx = False: Exit Function
If (intersectM(tp2, tp3, xp, tp1) < 0#) Then PosIncludeTriEx = False: Exit Function
PosIncludeTriEx = True
End Function
|
|
と考えれば、上記の三角形による包含判定を用いて行うことができます。 |
'ある点が多角形内の点であるかどうかを調べる
'ppos() 頂点データ
'n 頂点の数
'xp ある点
'「PosIncludeTri」を用いる
'「PosIncludeTri」で『三角形の境界線上の点に対しては、Trueを返す』
'とした理由は、このプロシージャの判定を正確に行うためである
Public Function PosIncludePoly(ppos() As POINT, n As Long, xp As POINT) As Boolean
Dim i As Long
For i = 0& To n - 2& - 1&
If PosIncludeTriEx(ppos(0), ppos(i + 1), ppos(i + 2), xp) = True Then
PosIncludePoly = True: Exit Function
End If
Next i
PosIncludePoly = False
End Function
|
|
（判定の問題点） 三角形による包含判定では線分上の点について、「包含している」という判定を しますが、上記のコードではこの判定が正確に行われるかは非常に微妙です。 （整数のみの計算であれば、正確に判定可能です） というのも、線分と直線の交差判定で、『0.0』との比較をしているからです。 浮動小数点の乗算による誤差や丸めによって、 本来は『0.0』なのに、計算によって 誤差が生じ、『0.0』にならない場合があります。 このことは、三角形による包含判定であれば、かなり微妙な部分なので無視しても 問題ないと思いますが、上記のような多角形による包含判定ではこの微妙な判定でも 正確に行う必要があります。（明らかに包含していても、包含していないと判定される） それを防ぐ方法として、Double型の値ではなくSingle型、あるいはもっと精度の低い値 を入力値として扱い、計算時にDouble型を用い判定時にまた精度の低い値を 用いれば、『0.0』との比較も正確に行うことができる！？と思いますが定かではあリません。(^^ （任意の多角形による包含判定） 上記の判定法は、基本的に多角形(閉路)の作成〜散在した点のソート〜 で作成される多角形が対象です。では、他の多角形、例えば次のような 星形の多角形の場合はどのようして判定するか？ 「多角形はどんなものでも三角形に分割できる」 ということを利用して、それぞれの三角形に対して包含判定を行えば可能です。 （気合いが足りない絵だなぁ・・・）  （他の包含判定） 多角形に含まれていない任意の点を求め、その点とある点を結ぶ線分が 多角形を構成する線分と何回交差しているかを求め、その数が偶数回であれば 「包含していない」、奇数回であれば、「包含している」というような判定方法 もありますが、任意の点とある点を結ぶ線分上 に多角形を構成する頂点が存在したときの 例外処理（これはかなりやっかい）を行う必要がある事など、 別の判定方法であっても「簡単に」とはいかないようです。 |
| 機種 | PC-9821V13S |
| OS | Windows95 |
| 開発ツール | Visual Basic Ver.4.0 |
| 更新日 | 00/09/07 |
Visual Basic Ver.5.0,Ver.6.0でも問題なく動作すると思います。
なお、このコーナーに掲載されているプログラムコード、およびプログラムファ イルが原因で生じた損害などに関して一切の責任を負うことはできません。
★掲載されているプログラムコード、およびプログラムファイル、 ソースファイルを無断で配布・転載することは、原則として禁止です。