我看到下面的算法可以从这个链接检查一个点是否在给定的多边形中：
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;
}
我尝试了这个算法，它实际上非常完美。但遗憾的是，在花了一些时间试图了解它之后，我无法很好地理解它。
所以如果有人能够理解这个算法，请给我解释一下。
谢谢你。
该算法是向右投射光线。循环的每次迭代，都会根据多边形的一个边检查测试点。如果点的 y 坐标在边的范围内，则 if 测试的第一行成功。第二行检查测试点是否在该行的左侧（我想 - 我没有任何废纸要检查）。如果是这样，则从测试点向右绘制的线穿过该边缘。
通过反复反转 的值c，该算法计算向右的线穿过多边形的次数。如果它穿过奇数次，则该点在内部；如果是偶数，则该点在外面。
不过，我会担心 a) 浮点运算的准确性，以及 b) 具有水平边缘或与顶点具有相同 y 坐标的测试点的影响。
编辑 1/30/2022：我在 9 年前上大学时写了这个答案。聊天对话中的人表示它不准确。你可能应该去别处看看。♂️</p>
乔利特在各个方面、形状和形式上都是正确的。该算法假设如果您的点在多边形的线上，那么它就在外面——在某些情况下，这是错误的。将两个 '>' 运算符更改为 '>=' 并将 '<' 更改为 '<=' 将解决此问题。
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;
}
这可能与解释实际代码中的光线追踪算法一样详细。它可能没有经过优化，但必须始终在完全掌握系统之后进行。
//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;
}
关于优化只有一句话：最短（和/或最简洁）的代码不是最快的实现。从数组中读取和存储元素并在代码块的执行中（可能）多次使用它比每次需要时访问数组要快得多。如果阵列非常大，这一点尤其重要。在我看来，通过将数组的每个项存储在一个命名良好的变量中，也更容易评估其用途，从而形成更易读的代码。就我的两分钱...
我更改了原始代码以使其更具可读性（这也使用了 Eigen）。该算法是相同的。
// 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;
}
只要多边形的边不交叉，该算法就适用于任何封闭的多边形。三角形、五边形、正方形，甚至是非常弯曲的不交叉的分段线性橡皮筋。
1）将您的多边形定义为一组有向向量。这意味着多边形的每一边都由一个从顶点an到顶点an+1的向量来描述。这些向量是这样定向的，以至于一个人的头部接触到下一个向量的尾部，直到最后一个向量接触到第一个向量的尾部。
2) 在多边形内部或外部选择要测试的点。
3) 对于沿多边形周边的每个向量 Vn，找到从测试点开始到 Vn 尾部结束的向量 Dn。计算定义为 DnXVn/DN*VN 的向量 Cn（X 表示叉积；* 表示点积）。将 Cn 的大小称为 Mn。
4) 把所有的 Mn 相加，称这个量为 K。
5) 如果 K 为零，则该点在多边形之外。
6) 如果 K 不为零，则该点在多边形内。
理论上，位于多边形边缘上的点将产生未定义的结果。
K 的几何含义是坐在我们测试点上的跳蚤“看到”在多边形边缘行走的蚂蚁向左行走的总角度减去向右行走的角度。在闭合回路中，蚂蚁在它开始的地方结束。在多边形之外，无论位置如何，答案都是零。
在多边形内部，无论位置如何，答案都是“绕点一次”。
该算法被精简为最必要的元素。在它被开发和测试之后，所有不必要的东西都被删除了。结果，您无法轻易理解它，但它可以完成工作并且性能也非常好。
// 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;
}
此方法检查从点 (testx, testy) 到 O (0,0) 的光线是否切过多边形的边。
这里有一个众所周知的结论：如果一条来自 1 点的射线切割多边形的边一段奇数时间，则该点将属于该多边形，否则该点将位于该多边形之外。
为了扩展@chowlette 的答案，第二行检查点是否在行的左侧，没有给出推导，但这是我得出的结论：首先，它有助于想象2个基本情况：
. /或/ .如果我们的观点是水平射出一条射线，它会在哪里击中线段。我们的点是在它的左边还是右边？里面还是外面？我们知道它的 y 坐标，因为根据定义它与点相同。x坐标是什么？
采取您的传统线路公式y = mx + b。m 是在运行中的上升。在这里，我们试图找到与我们的 point 具有相同高度 (y) 的线段上的点的 x 坐标。
所以我们求解 x: x = (y - b)/m。m是上升超过运行，所以这变成溢出上升或(yj - yi)/(xj - xi)变为(xj - xi)/(yj - yi)。b 是与原点的偏移量。如果我们假设yi作为我们坐标系的基础，b 就变成了 yi。我们的观点testy是我们的输入，减法yi将整个公式变成一个偏移量yi。
我们现在有(xj - xi)/(yj - yi)or1/m时间 y or (testy - yi):(xj - xi)(testy - yi)/(yj - yi)但 testx 不是基于，yi所以我们将它添加回来以便比较两者（或零 testx ）
我认为基本思想是从点计算向量，多边形的每个边缘一个。如果向量穿过一条边，则该点在多边形内。通过凹多边形，如果它穿过奇数个边，它也在里面（免责声明：虽然不确定它是否适用于所有凹多边形）。
这是我使用的算法，但我添加了一些预处理技巧来加速它。我的多边形有大约 1000 条边并且它们不会改变，但我需要在每次鼠标移动时查看光标是否在一个内部。
我基本上将边界矩形的高度分割为相等长度的间隔，并且对于这些间隔中的每一个，我都会编译位于其中/与它相交的边的列表。
当我需要查找一个点时，我可以计算 - 在 O(1) 时间内 - 它位于哪个区间，然后我只需要测试区间列表中的那些边。
我使用了 256 个间隔，这将我需要测试的边数减少到 2-10 而不是 ~1000。
这是一个 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;
}
测试运行：
<?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);
我修改了代码以检查该点是否在多边形中，包括该点是否在边缘上。
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;
}