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

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

Учитывая случайный многоугольник, сформулированный с помощью 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 - py)/m + px; return CGPointMake(x,y); } CGPoint pointOnLineWithX(CGPoint p, float m, float x) { float y = m*(x - px) + py; return CGPointMake(x, y); } 

    Если у вас есть вершины, вы можете вычислить сумму углов между тестовой точкой и каждой парой точек, составляющих многоугольник. Если это 2 * pi, то это внутренняя точка. Если это 0, то это внешняя точка.

    Некоторый код:

      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 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); } значение  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 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); } 

    Источник: http://paulbourke.net/geometry/insidepoly/

    Другие места, которые вы можете посмотреть: http://alienryderflex.com/polygon/

    http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

    http://sidvind.com/wiki/Point-in-polygon:_Jordan_Curve_Theorem