[C++] Is the Point Inside the Polygon?

point-in-polygon (PIP)

“In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon.” Wikipedia.

점이 다각형(Polygon) 내부에 있는지 확인하는 코드입니다.

struct Point
{
  int x;
  int y;
};

bool InsidePolygon(int nvert, Point polygon[], int pointx, int pointy)
{
    int i, j = 0;
    bool inside = false;

    for (i = 0, j = nvert - 1; i < nvert; j = i++)
    {
        if (((polygon[i].y > pointy) != (polygon[j].y > pointy)) &&
          (pointx < (polygon[j].x - polygon[i].x) * (pointy - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x)) {
            inside = !inside;
        }
    }

    return inside;
}

인수

• nvert : 다각형의 정점 수
• polygon[] : 다각형을 형성하는 점의 배열
• pointx : 점의 X 좌표
• pointy : 점의 Y 좌표

테스트

int main()
{
  Point polygon[] = {{0, 0}, {50, 0}, {50, 50}, {0, 50}};
  int n = sizeof(polygon) / sizeof(polygon[0]);

  bool result = InsidePolygon(n, polygon, 0, 5);
  result ? std::cout << "YES \n" : std::cout << "NO \n";

  result = InsidePolygon(n, polygon, 60, 20);
  result ? std::cout << "YES \n" : std::cout << "NO \n";

  return 0;
}

결과

YES
NO