[vba] 닫힌 다각형의 내부 외부 판별

지식인에서 엑셀 카테고리에는 잘 올라오지 않는 질문이 하나 올라왔는데, 엑셀보다는 수학과 더 관련이 있는 것 같다.

바로 "어떤 점이 닫힌 다각형의 내부에 있는가?" 를 알게 해 주는 방법을 묻는 질문이었다.

 

관련한 로직은 수학 관련 블로그에 많이 있지만, 그림 하나로 대체하려 한다. 자세한 설명은 링크 참조.

위 그림에서 A와 B 두 개의 점이 있는데, A는 다각형의 외부, B는 다각형의 내부에 있다.

그것을 알 수 있는 방법은, 해당 점에서 오른쪽으로 (X축이 커지는 방향) 수평선을 그어서, 다각형의 선분과 교차하는 지점의 수를 세어보는 것이다.

교차점의 갯수가 홀수이면 다각형의 내부에 있는 것이고, 짝수이면 외부에 있는 것이다.

눈으로 보면 어린아이도 알 수 있는 것이지만, 이것을 알고리즘으로 구현하는 것이 문제이다.

위의 링크에 가보면 C언어로 소스코드를 만들어놓았다.

질문자가 필요한 것은 VBA이기에, 구글 검색을 해보았더니 어느 고수가 올려놓은 것을 발견할 수 있었다.

Option Explicit
Public Function PtInPoly(Xcoord As Double, Ycoord As Double, Polygon As Variant) As Variant
  Dim x As Long, m As Double, b As Double, Poly As Variant
  Dim LB1 As Long, LB2 As Long, UB1 As Long, UB2 As Long, NumSidesCrossed As Long
  Poly = Polygon
  If Not (Poly(LBound(Poly), 1) = Poly(UBound(Poly), 1) And _
        Poly(LBound(Poly), 2) = Poly(UBound(Poly), 2)) Then
    If TypeOf Application.Caller Is Range Then
      PtInPoly = "#닫히지않은 다각형!"
    Else
      Err.Raise 998, , "닫힌 다각형이 아닙니다!"
    End If
    Exit Function
  ElseIf UBound(Poly, 2) - LBound(Poly, 2) <> 1 Then
    If TypeOf Application.Caller Is Range Then
      PtInPoly = "#잘못된좌표!"
    Else
      Err.Raise 999, , "배열의 좌표가 잘못되었습니다!"
    End If
    Exit Function
  End If
  For x = LBound(Poly) To UBound(Poly) - 1
    If Poly(x, 1) > Xcoord Xor Poly(x + 1, 1) > Xcoord Then
      m = (Poly(x + 1, 2) - Poly(x, 2)) / (Poly(x + 1, 1) - Poly(x, 1))
      b = (Poly(x, 2) * Poly(x + 1, 1) - Poly(x, 1) * Poly(x + 1, 2)) / (Poly(x + 1, 1) - Poly(x, 1))
      If m * Xcoord + b > Ycoord Then NumSidesCrossed = NumSidesCrossed + 1
    End If
  Next
  PtInPoly = CBool(NumSidesCrossed Mod 2)
End Function

자세히는 살펴보기 어렵지만, 대충 보면 다각형의 꼭지점의 좌표를 배열변수에 담고, 해당 변수사이의 계산을 통해 주어진 점의 좌표가 다각형과 교차하는 수를 세어서 짝수이면 False, 홀수이면 True 값을 반환한다.

그래서

=IF(PtInPoly(I2,J2,D1:E5),"내부","외부")

이런 식으로 수식을 쓰면, 내부 외부를 판별할 수 있다.

주의할 점은, 다각형의 꼭지점을 셀에 표시할 때, 그림처럼 맨 첫 꼭지점의 좌표를 맨 아래에 한 번 더 써줘야한다는 것이다.

위의 코드는 아래와 같이 간략하게 할 수 있는데, 아래와 같이 코드를 쓰려면 두 가지 조건이 있다.

1. 다각형은 닫혀 있을것

2. 좌표는 2차원일것 (x,y,z 처럼 3차원에서는 작동하지 않는다)

Public Function PtInPoly(Xcoord As Double, Ycoord As Double, Polygon As Variant) As Variant Dim x As Long, NumSidesCrossed As Long, m As Double, b As Double, Poly As Variant Poly = Polygon For x = LBound(Poly) To UBound(Poly) - 1 If Poly(x, 1) > Xcoord Xor Poly(x + 1, 1) > Xcoord Then m = (Poly(x + 1, 2) - Poly(x, 2)) / (Poly(x + 1, 1) - Poly(x, 1)) b = (Poly(x, 2) * Poly(x + 1, 1) - Poly(x, 1) * Poly(x + 1, 2)) / (Poly(x + 1, 1) - Poly(x, 1)) If m * Xcoord + b > Ycoord Then NumSidesCrossed = NumSidesCrossed + 1 End If Next PtInPoly = CBool(NumSidesCrossed Mod 2) End Function

코드에 대한 자세한 분석은 다음에 시간이 있을 때 하도록 하자

  다각형의내부판별.xlsm