点多边形算法

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) {

  vector<Point> points = polygon.getPoints();

  int i, j, nvert = points.size();

  bool c = false;

  for(i = 0, j = nvert - 1; i < nvert; j = i++) {

    if( ( (points[i].y >= point.y ) != (points[j].y >= point.y) ) &&

        (point.x <= (points[j].x - points[i].x) * (point.y - points[i].y) / (points[j].y - points[i].y) + points[i].x)

      )

      c = !c;

  }

  return c;

}

Answer 2

这可能与在实际代码中解释光线跟踪算法所获得的结果一样详细。它可能未进行优化，但必须始终在系统完全掌握之后才能进行优化。

    //method to check if a Coordinate is located in a polygon

public boolean checkIsInPolygon(ArrayList<Coordinate> poly){

    //this method uses the ray tracing algorithm to determine if the point is in the polygon

    int nPoints=poly.size();

    int j=-999;

    int i=-999;

    boolean locatedInPolygon=false;

    for(i=0;i<(nPoints);i++){

        //repeat loop for all sets of points

        if(i==(nPoints-1)){

            //if i is the last vertex, let j be the first vertex

            j= 0;

        }else{

            //for all-else, let j=(i+1)th vertex

            j=i+1;

        }

        float vertY_i= (float)poly.get(i).getY();

        float vertX_i= (float)poly.get(i).getX();

        float vertY_j= (float)poly.get(j).getY();

        float vertX_j= (float)poly.get(j).getX();

        float testX  = (float)this.getX();

        float testY  = (float)this.getY();

        // following statement checks if testPoint.Y is below Y-coord of i-th vertex

        boolean belowLowY=vertY_i>testY;

        // following statement checks if testPoint.Y is below Y-coord of i+1-th vertex

        boolean belowHighY=vertY_j>testY;

        /* following statement is true if testPoint.Y satisfies either (only one is possible) 

        -->(i).Y < testPoint.Y < (i+1).Y        OR  

        -->(i).Y > testPoint.Y > (i+1).Y

        (Note)

        Both of the conditions indicate that a point is located within the edges of the Y-th coordinate

        of the (i)-th and the (i+1)- th vertices of the polygon. If neither of the above

        conditions is satisfied, then it is assured that a semi-infinite horizontal line draw 

        to the right from the testpoint will NOT cross the line that connects vertices i and i+1 

        of the polygon

        */

        boolean withinYsEdges= belowLowY != belowHighY;

        if( withinYsEdges){

            // this is the slope of the line that connects vertices i and i+1 of the polygon

            float slopeOfLine   = ( vertX_j-vertX_i )/ (vertY_j-vertY_i) ;

            // this looks up the x-coord of a point lying on the above line, given its y-coord

            float pointOnLine   = ( slopeOfLine* (testY - vertY_i) )+vertX_i;

            //checks to see if x-coord of testPoint is smaller than the point on the line with the same y-coord

            boolean isLeftToLine= testX < pointOnLine;

            if(isLeftToLine){

                //this statement changes true to false (and vice-versa)

                locatedInPolygon= !locatedInPolygon;

            }//end if (isLeftToLine)

        }//end if (withinYsEdges

    }

    return locatedInPolygon;

}

关于优化的一句话：最短的（和/或最有趣的）代码实现最快是不正确的。与在每次需要访问数组时相比，从数组中读取和存储一个元素并在代码块的执行过程中（可能）多次使用该元素的过程要快得多。如果阵列非常大，这一点尤其重要。我认为，通过将数组的每个项存储在一个命名良好的变量中，也可以更容易地评估其目的，从而形成更具可读性的代码。只是我的两分钱