座標を持った平面範囲に座標を持った線分が入っているかを判断する方法

座標を持った平面範囲に、座標を持った線分が入っているかどうかを判断する方法を教えてください。
アルゴリズムやエクセルコードがあれば、嬉しいです。

No.4 回答者： sxsijk 回答日時： 2021/03/29 21:46

一つの座標点の内外判定に、Winding Number Algorithm と呼ばれる方法があります。

これを折れ線近似した線分の節点に順次適用すれば、ある程度の判定は可能です。
ただし、前後の節点を結ぶ線の一部が図形の外に出る可能性があるので、厳密ではありません。

経路に沿った節点（時系列に得られる経路の各時点での位置、線分を折れ線近似した各節点など）が多角形で表された図形の内か外かを判定する方法を、下記に示します。

水平右向きをx軸、垂直上向きをy軸とする。
図形は多角形polygonで表す。
節点nodeから右側に引いた水平線と多角形の各辺との交差状況に基づき、下記のルールで内外判定を行う。

ルール1. 上向きの辺は、開始点を含み終点を含まない。
ルール2. 下向きの辺は、開始点を含まず終点を含む。
ルール3. 水平線と辺の交点は、節点の右側になくてはならない。
ルール4. 上向きの辺と交差する場合、+1する。
ルール5. 下向きの辺と交差する場合、-1する。

下記urlの［座標点の図形内外判定(Excel)］にサンプルを載せています。
http://sxs.html.xdomain.jp/che/index.html


Sub Inoutjudg()
' Inoutjudg(Args(1), Args(2), Args(3))

'線分と多角形の内外判定（Winding Number Algorithm）

' Args(1) = polygon：入力、多角形節点テーブル
' Args(2) = node ：入力、線分節点テーブル
' Args(3) = result ：出力、判定結果テーブル

Dim i, k As Integer
Dim np, nn As Integer
Dim polygon() As Double
Dim node() As Double
Dim result() As Double
Dim cfx As Double

'データ入力
np = Args(1).rowCount ' 多角形節点数
nn = Args(2).rowCount ' 線分節点数
ReDim polygon(np, 2) As Double
ReDim node(nn, 2) As Double
ReDim result(nn) As Double

Range("A1").Cells(Args(1).row, Args(1).Column).Select
For i = 1 To np
polygon(i, 1) = Selection.Cells(i, 1).Value
polygon(i, 2) = Selection.Cells(i, 2).Value
Next i
Range("A1").Cells(Args(2).row, Args(2).Column).Select
For i = 1 To nn
node(i, 1) = Selection.Cells(i, 1).Value
node(i, 2) = Selection.Cells(i, 2).Value
Next i

Range("A1").Cells(Args(3).row, Args(3).Column).Select '判定結果の出力セルの準備

For k = 1 To nn
result(k) = 0
For i = 1 To np - 1
'上向きの辺の処理
'y軸方向について、節点が始点と終点の間にある。ただし、終点は含まない。(ルール1)
If ((polygon(i, 2) <= node(k, 2)) And (node(k, 2) < polygon(i + 1, 2))) Then
'節点と同じ高さになる辺の位置におけるxの値を求め、辺が節点の右か左か判定する。
'辺は節点よりも右側にある。(ルール3)
cfx = (node(k, 2) - polygon(i, 2)) / (polygon(i + 1, 2) - polygon(i, 2))
If (node(k, 1) < (polygon(i, 1) + (cfx * (polygon(i + 1, 1) - polygon(i, 1))))) Then
result(k) = result(k) + 1 '上向きの辺と交差した場合は+1（ルール4）
End If

'下向きの辺の処理
'y軸方向について、節点が始点と終点の間にある。ただし、始点は含まない。(ルール2)
ElseIf ((polygon(i, 2) > node(k, 2)) And (node(k, 2) >= polygon(i + 1, 2))) Then
'節点と同じ高さになる辺の位置におけるxの値を求め、辺が節点の右か左か判定する。
'辺は節点よりも右側にある。(ルール3)
cfx = (node(k, 2) - polygon(i, 2)) / (polygon(i + 1, 2) - polygon(i, 2))
If (node(k, 1) < (polygon(i, 1) + (cfx * (polygon(i + 1, 1) - polygon(i, 1))))) Then
result(k) = result(k) - 1 '下向きの辺と交差した場合は-1（ルール5）
End If
End If
Next i
Selection.Cells(k, 1).Value = result(k)
Next k
End Sub

No.3 回答者： ありものがたり 回答日時： 2021/03/25 10:00

「座標を持った」というのが、座標成分の等式で表示されている

という意味であれば、平面の方程式へ直線のパラメータ表示を
代入して、恒等式になっているかチェックすればよいです。

No.2 回答者： finalbento 回答日時： 2021/03/24 23:43

「入るようにもできるし入らないようにもできる。

自分の好きなように決めればいいだけ」


この質問文を読んだだけだとこう言う回答しかできないはずです。恐らく質問したい内容が伝わりません。

No.1 回答者： Tacosan 回答日時： 2021/03/24 19:22

「座標を持った平面範囲」とか「座標を持った線分」とかって, どういうもの? また, 「入っている」とはどういう状態を指す?