By

文章目录
  1. 1. PNPoly
  2. 2. 基于扫描填充多边形的方法

PNPoly

PNPoly是由W. Randolph Franklin提出的一种在二维空间较为高效地判断点是否在多边形内的算法，算法具有很好的通用性，对凸多边形、凹多边形以及含有空洞的多边形均适用。
最小外接矩形范围判断

1
2
3
if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
    // 点在多边形之外
}

首先判断点是否在多边形的最小外接矩形之内，该步骤不是必须的，但是可以有效避免不必要的计算。
核心算法

1
2
3
4
5
6
7
8
9
10
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;
}

针对每一个点，算法遍历多边形相邻的每两个顶点（即一条边），假如待判断点满足以下两个条件即改变点是否在多边形内的状态标识c：

  1. 待判断点的Y坐标在点i和点j的Y坐标范围之内
  2. 待判断点的X坐标在点i和点j连线之下
    遍历所有的边之后假如以上两个条件同时满足奇数次则该带判断点位于多边形之内，否则位于多边形之外。
    算法复杂度为O(n)，其中n为多边形的顶点个数。

算法主页： PNPoly
相关出版物：Haines, Eric, “Point in Polygon Strategies,” Graphics Gems IV, ed. Paul Heckbert, Academic Press, p. 24-46, 1994.

基于扫描填充多边形的方法

若针对同一多边形有大量的点需要判断是否在该多边形的话上述方法计算量将会很大，可以借助计算机图形学中的多边形填充方法，采用影像辅助判断点是否在多边形内，基于voronoi图的影像镶嵌（正射影像制作）是该方法典型的运用。
首先计算多边形的最小外接矩形，采用openCV绘制一张与外接矩形大小的黑色图像（图像分辨率可自定义，为适应之后的填充算法创建的影像的大小在扫描方向上需多加1个像素），在图像上绘制多边形的边。

1
2
image = cv::Mat::zeros(height,width,CV_8UC1);
line(image,pointi,pointj,255);

得到如下图像：绘制多边形边对上面的影像进行填充：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
for (int i = 0; i < height; i++)
{
	int trans_count(0);
	bool is_in_pologon(false);
	int trans_index(0);
	for (int j = 0; j < width-1; j++)
	{
		//cv::Vec3b a = image.at<cv::uchar>(i,j);
		if (image.at<cv::uchar>(i,j)==white_pixl&&image.at<cv::uchar>(i,j+1)!=white_pixl)
		{
			is_in_pologon = !is_in_pologon;
			trans_index = j;
			trans_count++;
		}
		if (is_in_pologon)
		{
			image.at<cv::uchar>(i,j) = 255;
		}
	}
	if (is_in_pologon)
	{
		image.at<cv::uchar>(i,width-1);
	}
	if (trans_count == 1)
	{	
		for (int j = width-1; j > trans_index; j--)
		{	 
			image.at<cv::uchar>(i,j) = 0;
		}
	}
}

填充后影像如下：扫描填充影像将待判断点的坐标换算到影像上若得到相应的像素值为255则该点在这个多边形之内，若得相应像素值为0则该点在多边形外。

文章目录
  1. 1. PNPoly
  2. 2. 基于扫描填充多边形的方法