Точки внутри многоугольника (без границ)

Question

В настоящее время я нахожу координаты внутри определенной формы с 12 вершинами.

  (3,7) (5,7) 
      ####### 
      #  # 
      # X # 
     (3,5)#  #(5,5) 
(1,5)####### X #######(7,5) 
     #     # 
     # X X X X X # 
     #     # 
(1,3)####### X #######(7,3) 
     (3,3)#  #(5,3) 
      # X # 
      #  # 
      ####### 
      (3,1) (5,1) 

Я хотел бы узнать координаты внутри формы (с пометкой «X»), за исключением координат, которые составляют форму.

Я попробовал pnpoly от W. Randolph Franklin (http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html), но он также считает координаты, которые составляют форму как «внутри формы».

Обратите внимание, что приведенная выше форма является всего лишь примером. Координаты могут быть в любом месте.

Как я могу изменить код таким образом, чтобы он не позволял включать границы формы?

int pnpoly(int vertx[], int verty[], int testx, int testy) { 
    int nvert = 12; 
    int i, j, c = 0; 
    for (i = 0, j = nvert-1; i < nvert; j = i++) { 
     if (((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i])/(verty[j]-verty[i]) + vertx[i])) { 
      c = !c; 
     } 
    } 
    return c; 
} 

Answer 1

Уменьшить форму на границе, которую вы хотите исключить, а затем использовать существующий алгоритм.

BTW: Не используйте int vertx[], это опасная ложь. Эквивалентный очевидный код - int* vertx, что делает очевидным, что ему не хватает const.

Answer 2

Поскольку у вас есть код для проверки, находится ли точка внутри заданного многоугольника, вам просто нужно исключить те точки, которые являются на многоугольником. Примечание: этот тест является только надежным, если вы используете целочисленные координаты (не плавает).

struct Point { 
    int X; 
    int Y; 
}; 

bool PointOnLineSegment(const Point pt, const Point linePt1, const Point linePt2) 
{ 
    return ((pt.X == linePt1.X) && (pt.Y == linePt1.Y)) || 
    ((pt.X == linePt2.X) && (pt.Y == linePt2.Y)) || 
    (((pt.X > linePt1.X) == (pt.X < linePt2.X)) && 
    ((pt.Y > linePt1.Y) == (pt.Y < linePt2.Y)) && 
    ((pt.X - linePt1.X) * (linePt2.Y - linePt1.Y) == 
     (linePt2.X - linePt1.X) * (pt.Y - linePt1.Y))); 
} 

bool PointOnPolygonEdge(const Point pt, Point *poly, int vertexCnt) 
{ 
    if (vertexCnt < 2) return false; 
    vertexCnt--; 
    for (int i = 0; i < vertexCnt; ++i) 
    if (PointOnLineSegment(pt, poly[i], poly[i+1])) 
     return true; 
    if (PointOnLineSegment(pt, poly[vertexCnt], poly[0])) return true; 
    return false; 
}