By

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;
}

Read More

By

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment