点在多边形algorithm
我看到下面的algorithm工作来检查点是否在这个链接给定的多边形：
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; } 我试过这个algorithm，它实际上是完美的。 但遗憾的是，花了一些时间想清楚这一点后，我不能理解。
所以如果有人能够理解这个algorithm，请给我解释一下。
谢谢。
该algorithm是射线铸造的权利。 循环的每一次迭代都会根据多边形的边缘检查testing点。 if-test的第一行成功，如果该点的y坐标在边界范围内。 第二行检查testing点是否在行的左边（我想 – 我没有任何废纸手来检查）。 如果这是真的，则从testing点向右画的线与该边缘交叉。
通过反复颠倒c的值，该algorithm计算右边的线与多边形相交的次数。 如果它跨越了奇数次，那么这个点在里面; 如果是偶数，则该点在外。
我会担心的是：a）浮点运算的准确性; b）水平边缘的效果，或者是具有与顶点相同的y坐标的testing点。
Chowlett在各个方面，形状和forms都是正确的。 该algorithm假定，如果你的点在多边形的线上，那么在外面 – 在某些情况下，这是错误的。 将两个“>”运算符更改为“> =”，将“<”更改为“<=”将会修复该问题。
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; }
这可能和解释实际代码中的光线跟踪algorithm一样详细。 它可能不是最优化的，但必须始终在完整掌握系统之后才能完成。
//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; }
关于优化只是一个字：最短的（和/或最简单的）代码是最快实现的。 从数组中读取和存储一个元素，并在代码块的执行过程中（可能）多次使用它，比在每次需要时访问数组要快得多。 如果数组非常大，这个特别重要。 在我看来，通过将数组中的每个项存储在一个命名好的variables中，评估其目的也变得更加容易，从而形成更可读的代码。 只是我的两分钱…
algorithm被分解成最必要的元素。 经过开发和testing，所有不必要的东西都被删除了。 因此，你不能很容易地做到这一点，但它的工作也是非常好的。
我冒昧地把它翻译成ActionScript-3 ：
// not optimized yet (nvert could be left out) public static function pnpoly(nvert: int, vertx: Array, verty: Array, x: Number, y: Number): Boolean { var i: int, j: int; var c: Boolean = false; for (i = 0, j = nvert - 1; i < nvert; j = i++) { if (((verty[i] > y) != (verty[j] > y)) && (x < (vertx[j] - vertx[i]) * (y - verty[i]) / (verty[j] - verty[i]) + vertx[i])) c = !c; } return c; }
只要多边形的边不交叉，该algorithm就可以在任何闭合的多边形中工作。 三angular形，五angular形，正方形，甚至是一条非常弯曲的分段线性橡胶带，不会穿过。
1）将多边形定义为一个有向vector组。 这意味着多边形的每一边都由从顶点an到顶点an + 1的vector描述。 vector如此指引，以便一个人的头部触及下一个的尾部，直到最后一个vector触及第一个尾部。
2）select多边形内部或外部的testing点。
3）对于沿多边形周长的每个向量Vn，find在testing点开始并在Vn的尾部结束的向量Dn。 计算定义为DnXVn / DN * VN的向量Cn（X表示叉积，*表示点积）。 用Mn命名Cn的大小。
4）添加所有的锰并称这个数量为K.
5）如果K是零，则该点在多边形之外。
6）如果K不为零，则该点位于多边形内。
从理论上说，位于多边形边缘的点会产生未定义的结果。
K的几何意义是坐在我们testing点上的跳蚤“看到”走在多边形边缘的ant向左走的angular度减去走向右边的angular度的总angular度。 在一个闭路，ant结束的地方开始。 在多边形之外，不pipe位置如何，答案都是零。
在多边形的内部，不pipe位置如何，答案都是“围绕一点”。
此方法检查从点（testx，testy）到O（0,0）的光线是否切割多边形的边。
这里有一个众所周知的结论：如果一个射线从一个点开始，并且在一个奇数时间内切割一个多边形的边，那么这个点将属于这个多边形，否则这个点将会在这个多边形之外。
我认为基本思想是从这个点计算vector，每个边的一个边。 如果vector穿过一条边，则该点位于多边形内。 如果凹多边形穿过奇数个边，则它也位于内部（免责声明：虽然不确定是否适用于所有凹多边形）。
为了扩展@ chowlette的答案 ，第二行检查点是否在行的左边，没有给出派生，但是这是我的工作：首先它有助于想象2个基本情况：
- 这一点是左边的线
. /. /或 - 该点是正确的
/ .
如果我们的观点是水平射线，那么它会在线段上出现。 我们指向它的左边还是右边？ 里面还是外面？ 我们知道它的y坐标，因为它的定义和点一样。 x坐标是什么？
把你的传统的直线公式y = mx + b 。 米是运行的上升。 在这里，我们正在试图find该线段上与我们的点具有相同高度（y）的点的x坐标 。
所以我们求解x： x = (y - b)/m 。 (yj - yi)/(xj - xi)变为(xj - xi)/(yj - yi) 。 b是起源的偏移量。 如果我们假设yi作为坐标系的基础，那么b变成yi。 我们的点testing是我们的input，减去yi将整个公式转换成与yi的偏移。
我们现在有(xj - xi)/(yj - yi)或者1/m乘以y或(testy - yi) ：（ (xj - xi)(testy - yi)/(yj - yi) yi所以我们把它加回去以便比较两个（或者零的testx）
这里是一个PHP的实现：
<?php class Point2D { public $x; public $y; function __construct($x, $y) { $this->x = $x; $this->y = $y; } function x() { return $this->x; } function y() { return $this->y; } } class Point { protected $vertices; function __construct($vertices) { $this->vertices = $vertices; } //Determines if the specified point is within the polygon. function pointInPolygon($point) { /* @var $point Point2D */ $poly_vertices = $this->vertices; $num_of_vertices = count($poly_vertices); $edge_error = 1.192092896e-07; $r = false; for ($i = 0, $j = $num_of_vertices - 1; $i < $num_of_vertices; $j = $i++) { /* @var $current_vertex_i Point2D */ /* @var $current_vertex_j Point2D */ $current_vertex_i = $poly_vertices[$i]; $current_vertex_j = $poly_vertices[$j]; if (abs($current_vertex_i->y - $current_vertex_j->y) <= $edge_error && abs($current_vertex_j->y - $point->y) <= $edge_error && ($current_vertex_i->x >= $point->x) != ($current_vertex_j->x >= $point->x)) { return true; } if ($current_vertex_i->y > $point->y != $current_vertex_j->y > $point->y) { $c = ($current_vertex_j->x - $current_vertex_i->x) * ($point->y - $current_vertex_i->y) / ($current_vertex_j->y - $current_vertex_i->y) + $current_vertex_i->x; if (abs($point->x - $c) <= $edge_error) { return true; } if ($point->x < $c) { $r = !$r; } } } return $r; }
testing运行：
<?php $vertices = array(); array_push($vertices, new Point2D(120, 40)); array_push($vertices, new Point2D(260, 40)); array_push($vertices, new Point2D(45, 170)); array_push($vertices, new Point2D(335, 170)); array_push($vertices, new Point2D(120, 300)); array_push($vertices, new Point2D(260, 300)); $Point = new Point($vertices); $point_to_find = new Point2D(190, 170); $isPointInPolygon = $Point->pointInPolygon($point_to_find); echo $isPointInPolygon; var_dump($isPointInPolygon);
这是我使用的algorithm，但我添加了一些预处理技巧来加速。 我的多边形有1000个边，它们不会改变，但是我需要查看光标是否在每个鼠标移动的内部。
我基本上将边界矩形的高度拆分为等长的间隔，并且对于每个这些间隔我编译位于/与之相交的边的列表。
当我需要查找一个点时，我可以计算 – 在O（1）时间内 – 它处于哪个区间，然后我只需要testing区间列表中的那些边。
我用256间隔，这减less了我需要testing的边缘的数量2-10而不是〜1000。
我修改了代码来检查点是否在一个多边形中，包括点在边上。
bool point_in_polygon_check_edge(const vec<double, 2>& v, vec<double, 2> polygon[], int point_count, double edge_error = 1.192092896e-07f) { const static int x = 0; const static int y = 1; int i, j; bool r = false; for (i = 0, j = point_count - 1; i < point_count; j = i++) { const vec<double, 2>& pi = polygon[i); const vec<double, 2>& pj = polygon[j]; if (fabs(pi[y] - pj[y]) <= edge_error && fabs(pj[y] - v[y]) <= edge_error && (pi[x] >= v[x]) != (pj[x] >= v[x])) { return true; } if ((pi[y] > v[y]) != (pj[y] > v[y])) { double c = (pj[x] - pi[x]) * (v[y] - pi[y]) / (pj[y] - pi[y]) + pi[x]; if (fabs(v[x] - c) <= edge_error) { return true; } if (v[x] < c) { r = !r; } } } return r; }
我改变了原来的代码 ，使其更具可读性（也使用Eigen）。 algorithm是相同的。
// This uses the ray-casting algorithm to decide whether the point is inside // the given polygon. See https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm bool pnpoly(const Eigen::MatrixX2d &poly, float x, float y) { // If we never cross any lines we're inside. bool inside = false; // Loop through all the edges. for (int i = 0; i < poly.rows(); ++i) { // i is the index of the first vertex, j is the next one. // The original code uses a too-clever trick for this. int j = (i + 1) % poly.rows(); // The vertices of the edge we are checking. double xp0 = poly(i, 0); double yp0 = poly(i, 1); double xp1 = poly(j, 0); double yp1 = poly(j, 1); // Check whether the edge intersects a line from (-inf,y) to (x,y). // First check if the line crosses the horizontal line at y in either direction. if ((yp0 <= y) && (yp1 > y) || (yp1 <= y) && (yp0 > y)) { // If so, get the point where it crosses that line. This is a simple solution // to a linear equation. Note that we can't get a division by zero here - // if yp1 == yp0 then the above if be false. double cross = (xp1 - xp0) * (y - yp0) / (yp1 - yp0) + xp0; // Finally check if it crosses to the left of our test point. You could equally // do right and it should give the same result. if (cross < x) inside = !inside; } } return inside; }
