선이 다각형과 교차합니까?

Question

여기에서 sijipie의 코드를 다시 작성했습니다. https://www.mrexcel.com/forum/excel-questions/713005-does-point-fall-within-polygon-visual-basic-applications-function.html

내가해야할 것은 라인이 다각형 내에 있는지 결정하는 것입니다.

필자는 선의 중간 점을 반복하고 내부 점임을 테스트 할 때 모든 단일면과 선의 교차점을 테스트하지 않기 때문에 약간 게으른 편입니다.

더 빠른 방법이 있는지 궁금합니다. 아래

VBA 코드 : 모든 다각형의 정점 (왼쪽 또는 오른쪽) 같은 반 평면에 있는지

Function PolyLineIntersect(lXY As Range, polyXY As Range) As Boolean 
    Dim i As Integer, j As Integer, a As Integer, polySides As Integer 
    Dim Result As Boolean 
    Dim x As Double, y As Double 
    Dim aXY As Variant 
    Dim mXY(1 To 5, 1 To 2) As Integer 
    Dim tXY(1 To 5) As Boolean 

    x = lXY.Cells.value2(1, 1) 
    y = lXY.Cells.value2(1, 2) 
    xb = lXY.Cells.value2(1, 3) 
    yb = lXY.Cells.value2(1, 4) 

    mXY(1, 1) = x 
    mXY(1, 2) = y 
    mXY(2, 1) = xb 
    mXY(2, 2) = yb 
    mXY(3, 1) = (xb + x)/2 
    mXY(3, 2) = (yb + y)/2 
    mXY(4, 1) = (xb + mx1)/2 
    mXY(4, 2) = (yb + my1)/2 
    mXY(5, 1) = (xb + mx1)/2 
    mXY(5, 2) = (yb + my1)/2 

    Result = False 

    aXY = polyXY.Value 

    polySides = polyXY.Rows.Count 
    j = polySides - 1 
    For a = 1 To 5     
     x = mXY(a, 1) 
     y = mXY(a, 2)     
     For i = 1 To polySides      
     If (((aXY(i, 2) < y And aXY(j, 2) >= y) _ 
     Or (aXY(j, 2) < y And aXY(i, 2) >= y)) _ 
     And (aXY(i, 1) <= x Or aXY(j, 1) <= x)) Then     
      Result = Result Xor (aXY(i, 1) + (y - aXY(i, 2))/(aXY(j, 2) - aXY(i, 2)) * (aXY(j, 1) - aXY(i, 1)) < x)        
     End If 
     j = i   
     Next i 
    Next a 
    PolyLineIntersect = Result 

End Function 

Answer 1

확인 cross product를 사용하여 주어진 라인에 상대. 그렇다면 선이 다각형과 교차하지 않습니다.

Side = Sign(CrossProduct(L2-L1, P[i] - L1)) 
where L1, L2 are points defining the line, P[i] is i-th polygon vertex 

알고리즘은 선형 시간 O (N)에서 작동하며 N은 다각형 정점 개수입니다. 볼록 다각형의 경우 바이너리 검색을 사용하여 O (logN) 시간에 결과를 추론 할 수 있습니다.