Как проверить, находится ли точка (x, y) внутри многоугольника в декартовой системе координат?

У этого вопроса уже есть ответ:
Точка в полигоне aka hit test
С# Точка в полигоне

Учитывая случайный многоугольник, сформулированный с помощью N линейных уравнений в декартовой системе координат, существует ли какая-либо стандартная формула, которая используется для проверки принадлежности точки (x, y)?

Простое решение состоит в том, чтобы получить все формулы линии и проверить, находится ли точка X ниже этой строки, над этой линией и справа от другой линии и т.д. Но это, вероятно, будет утомительным.

Следует отметить, что многоугольник может иметь любую форму с любым числом сторон и может быть вогнутым или выпуклым.

Для удобства я уже добавил эти служебные функции:

float slope(CGPoint p1, CGPoint p2)
{
    return (p2.y - p1.y) / (p2.x - p1.x);
}

CGPoint pointOnLineWithY(CGPoint p, float m, float y)
{
    float x = (y - p.y)/m + p.x;
    return CGPointMake(x,y);
}

CGPoint pointOnLineWithX(CGPoint p, float m, float x)
{
    float y = m*(x - p.x) + p.y;
    return CGPointMake(x, y);
}

typedef struct { int h,v; } Point; int InsidePolygon(Point *polygon,int n,Point p) { int i; double angle=0; Point p1,p2; for (i=0;i<n;i++) { p1.h = polygon[i].h - p.h; p1.v = polygon[i].v - p.v; p2.h = polygon[(i+1)%n].h - p.h; p2.v = polygon[(i+1)%n].v - p.v; angle += Angle2D(p1.h,p1.v,p2.h,p2.v); } if (ABS(angle) < PI) return(FALSE); else return(TRUE); } /* Return the angle between two vectors on a plane The angle is from vector 1 to vector 2, positive anticlockwise The result is between -pi -> pi */ double Angle2D(double x1, double y1, double x2, double y2) { double dtheta,theta1,theta2; theta1 = atan2(y1,x1); theta2 = atan2(y2,x2); dtheta = theta2 - theta1; while (dtheta > PI) dtheta -= TWOPI; while (dtheta < -PI) dtheta += TWOPI; return(dtheta); }

Ответ 1