我看到以下算法可以检查点是否位于此链接的给定多边形中：
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 年前上大学时写了这个答案。聊天对话中的人表示它不准确。你可能应该看看其他地方。🤷♂️
乔利特在各个方面、形状和形式上都是正确的。该算法假设，如果您的点在多边形的线上，那么该点在外面 - 在某些情况下，这是错误的。将两个">"运算符更改为">="并将"<"更改为"<="将解决此问题。
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;
}
我更改了原始代码以使其更具可读性(这也使用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 will 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;
}
扩展"太聪明的把戏"。我们想遍历所有相邻的顶点，就像这样(假设有 4 个顶点(：
i | j |
|---|---|
| 0 | 1 |
| 1 | 阿拉伯数字 |
| 阿拉伯数字 | 3 |
| 3 | 0 |
这可能与在实际代码中解释光线追踪算法一样详细。它可能没有被优化，但必须始终在完全掌握系统之后进行。
//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;
}
关于优化只有一个词：最短(和/或最简洁(的代码并不是最快的实现。从数组中读取和存储元素并在代码块的执行中多次使用它(可能(比每次需要访问数组要快得多。如果阵列非常大，这一点尤其重要。在我看来，通过将数组的每个术语存储在一个命名良好的变量中，也更容易评估其目的，从而形成更具可读性的代码。就我的两分钱...
该算法被剥离到最必要的元素。在开发和测试之后，所有不必要的东西都被删除了。因此，您无法轻松理解它，但它可以完成工作并且性能也非常好。
我冒昧地将其翻译成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;
}
只要多边形的边不相交，此算法就适用于任何闭合多边形。 三角形，五边形，正方形，甚至是一个非常弯曲的分段线性橡皮筋，不会交叉。
1( 将多边形定义为有向向量组。 这意味着多边形的每一条边都由从顶点 an 到顶点 an+1 的向量描述。 向量是如此定向，以至于一个向量的头部接触下一个向量的尾巴，直到最后一个向量的尾部接触第一个向量的尾部。
2( 选择要在多边形内部或外部测试的点。
3( 对于沿多边形周长的每个向量 Vn，找到从测试点开始并在 Vn 尾部结束的向量 Dn.计算定义为 DnXVn/DN*VN 的向量 Cn(X 表示叉积;* 表示点积(。用Mn的名字来称Cn的大小。
4(将所有Mn相加，并将此数量称为K。
5( 如果 K 为零，则点在多边形之外。
6( 如果 K 不为零，则点在多边形内。
从理论上讲，位于多边形边缘的点将产生未定义的结果。
K 的几何含义是坐在我们测试点上的跳蚤"看到"蚂蚁在多边形边缘向左行走的总角度减去向右行走的角度。 在闭合回路中，蚂蚁在它开始的地方结束。在多边形之外，无论位置如何，答案均为零。
在多边形内部，无论位置如何，答案都是"围绕点一次"。
此方法检查从点(testx，testy(到O(0,0(的光线是否切割了多边形的边。
这里有一个众所周知的结论：如果一条光线从 1 点开始切割多边形的边一段奇数时间，则该点将属于多边形，否则该点将位于多边形之外。
为了扩展@chowlette的答案，其中第二行检查该点是否在该行的左侧，没有给出推导，但这是我计算出来的：首先，它有助于想象 2 个基本案例：
- 该点位于行的左侧
. /或 - 该点位于行的右边
/ .
如果我们的点是水平射出一条射线，它会击中线段的位置。我们的点是左边还是右边？里面还是外面？我们知道它的 y 坐标，因为根据定义，它与点相同。x 坐标是什么？
以传统的线条公式y = mx + b . m 是运行中的上升。在这里，我们试图找到与我们的点具有相同高度 (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) 或 1/m 次 y 或 (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;
}