Polygon C++ 算法实现中的点

Question

我尝试了两种在其他 Whosebug 问题中得到解答的算法：

Check point within polygon

Point in Polygon Algorithm

两者都显示了一些点在 out 或 out as in 而其他点是正确的。这个测试演员假设总是只有4个顶点（矩形）

bool PointInPolygon(Coordinate point, vector<Coordinate> points) {
cout << "x,y" << point.getX() << "," << point.getY() << endl;
cout << "TEST COOR ARRAY" << endl;
for (int i=0; i<4; i++) {
    cout << points[i].getX() << "," << points[i].getY() << endl;
}
   
int i, j, nvert = points.size();
bool c = false;

for(i = 0, j = nvert - 1; i < nvert; j = i++) {
  if( ( (points[i].getY() > point.getY() ) != (points[j].getY() > point.getY()) ) &&
      (point.getX() < (points[j].getX() - points[i].getX()) * (point.getY() - points[i].getY()) / (points[j].getY() - points[i].getY()) + points[i].getX())
    )
    c = !c;
}

cout << c << "======================" << endl;

return c;
}

并且输出错误，其中 (2,3) 和 (1,1) 不应该出现。周边的线不被认为是在。但即便如此，那么2,3也应该一直在。

x,y1,1
TEST COOR ARRAY
1,1
1,3
4,3
4,1
1======================
IN
x,y2,2
TEST COOR ARRAY
1,1
1,3
4,3
4,1
1======================
IN
x,y2,3
TEST COOR ARRAY
1,1
1,3
4,3
4,1
0======================
OUT
x,y3,2
TEST COOR ARRAY
1,1
1,3
4,3
4,1
1======================
IN
x,y3,3
TEST COOR ARRAY
1,1
1,3
4,3
4,1
0======================
OUT

我在使用我发现的其他算法时也遇到了类似的问题。如果有人能指出我正确的方向，我将不胜感激！

Answer 1

算法基于以下概念：
对于任何封闭的多边形，任何直线都应与它的边相交偶数次（不考虑线对线的情况）...
将其视为（输入、退出、输入、退出...）。

所以，如果你从你的测试点画一条线到基本上无穷大，取决于它的起点，如果点在外面，它应该相交 Even 次，并且奇数如果它在！

正如我所见，通过测试用例和“4个顶点”注释：您正在寻找
PointInRectangle(Coord c, Rect r) 更简单、更快并且看起来合适。

对于您的测试用例，其中 (2,3) in (1,1)-(1,3)-(3,4)-(4,1) = TRUE
它与你的底线平行，可能是 "Disregarded",
但最有可能的是，由于 Floating Point Inaccuracy.
，与您的垂直线有交集您应该将表达式分成几部分，或者按原样调试它以查看在那里计算出的实际值。

Polygon C++ 算法实现中的点

Point in Polygon C++ Algorithm implementation

c++

algorithm

polygon