点多边形算法

Question

我看到以下算法可以检查该链接中的点是否在给定的多边形中：

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)

{

  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

Chowlett在各种方式，形状和形式上都是正确的。该算法假定，如果您的点在多边形的线上，则该点在外面-在某些情况下，这是错误的。将两个'>'运算符更改为'> ='并将'<'更改为'<='将解决此问题。bool PointInPolygon(Point point, Polygon polygon) {&nbsp; vector<Point> points = polygon.getPoints();&nbsp; int i, j, nvert = points.size();&nbsp; bool c = false;&nbsp; for(i = 0, j = nvert - 1; i < nvert; j = i++) {&nbsp; &nbsp; if( ( (points[i].y >= point.y ) != (points[j].y >= point.y) ) &&&nbsp; &nbsp; &nbsp; &nbsp; (point.x <= (points[j].x - points[i].x) * (point.y - points[i].y) / (points[j].y - points[i].y) + points[i].x)&nbsp; &nbsp; &nbsp; )&nbsp; &nbsp; &nbsp; c = !c;&nbsp; }&nbsp; return c;}

Answer 2

这可能与在实际代码中解释光线跟踪算法所获得的结果一样详细。它可能未进行优化，但必须始终在系统完全掌握之后才能进行优化。&nbsp; &nbsp; //method to check if a Coordinate is located in a polygonpublic boolean checkIsInPolygon(ArrayList<Coordinate> poly){&nbsp; &nbsp; //this method uses the ray tracing algorithm to determine if the point is in the polygon&nbsp; &nbsp; int nPoints=poly.size();&nbsp; &nbsp; int j=-999;&nbsp; &nbsp; int i=-999;&nbsp; &nbsp; boolean locatedInPolygon=false;&nbsp; &nbsp; for(i=0;i<(nPoints);i++){&nbsp; &nbsp; &nbsp; &nbsp; //repeat loop for all sets of points&nbsp; &nbsp; &nbsp; &nbsp; if(i==(nPoints-1)){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //if i is the last vertex, let j be the first vertex&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j= 0;&nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //for all-else, let j=(i+1)th vertex&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j=i+1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; float vertY_i= (float)poly.get(i).getY();&nbsp; &nbsp; &nbsp; &nbsp; float vertX_i= (float)poly.get(i).getX();&nbsp; &nbsp; &nbsp; &nbsp; float vertY_j= (float)poly.get(j).getY();&nbsp; &nbsp; &nbsp; &nbsp; float vertX_j= (float)poly.get(j).getX();&nbsp; &nbsp; &nbsp; &nbsp; float testX&nbsp; = (float)this.getX();&nbsp; &nbsp; &nbsp; &nbsp; float testY&nbsp; = (float)this.getY();&nbsp; &nbsp; &nbsp; &nbsp; // following statement checks if testPoint.Y is below Y-coord of i-th vertex&nbsp; &nbsp; &nbsp; &nbsp; boolean belowLowY=vertY_i>testY;&nbsp; &nbsp; &nbsp; &nbsp; // following statement checks if testPoint.Y is below Y-coord of i+1-th vertex&nbsp; &nbsp; &nbsp; &nbsp; boolean belowHighY=vertY_j>testY;&nbsp; &nbsp; &nbsp; &nbsp; /* following statement is true if testPoint.Y satisfies either (only one is possible)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; -->(i).Y < testPoint.Y < (i+1).Y&nbsp; &nbsp; &nbsp; &nbsp; OR&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; -->(i).Y > testPoint.Y > (i+1).Y&nbsp; &nbsp; &nbsp; &nbsp; (Note)&nbsp; &nbsp; &nbsp; &nbsp; Both of the conditions indicate that a point is located within the edges of the Y-th coordinate&nbsp; &nbsp; &nbsp; &nbsp; of the (i)-th and the (i+1)- th vertices of the polygon. If neither of the above&nbsp; &nbsp; &nbsp; &nbsp; conditions is satisfied, then it is assured that a semi-infinite horizontal line draw&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; to the right from the testpoint will NOT cross the line that connects vertices i and i+1&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; of the polygon&nbsp; &nbsp; &nbsp; &nbsp; */&nbsp; &nbsp; &nbsp; &nbsp; boolean withinYsEdges= belowLowY != belowHighY;&nbsp; &nbsp; &nbsp; &nbsp; if( withinYsEdges){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // this is the slope of the line that connects vertices i and i+1 of the polygon&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; float slopeOfLine&nbsp; &nbsp;= ( vertX_j-vertX_i )/ (vertY_j-vertY_i) ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // this looks up the x-coord of a point lying on the above line, given its y-coord&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; float pointOnLine&nbsp; &nbsp;= ( slopeOfLine* (testY - vertY_i) )+vertX_i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //checks to see if x-coord of testPoint is smaller than the point on the line with the same y-coord&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; boolean isLeftToLine= testX < pointOnLine;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(isLeftToLine){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //this statement changes true to false (and vice-versa)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; locatedInPolygon= !locatedInPolygon;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }//end if (isLeftToLine)&nbsp; &nbsp; &nbsp; &nbsp; }//end if (withinYsEdges&nbsp; &nbsp; }&nbsp; &nbsp; return locatedInPolygon;}关于优化的一句话：最短的（和/或最有趣的）代码实现最快是不正确的。与在每次需要访问数组时相比，从数组中读取和存储一个元素并在代码块的执行过程中（可能）多次使用该元素的过程要快得多。如果阵列非常大，这一点尤其重要。我认为，通过将数组的每个项存储在一个命名良好的变量中，也可以更容易地评估其目的，从而形成更具可读性的代码。只是我的两分钱