按多边形选择网格单元

Question

对于我正在构建的一个小程序，我有以下情况： 我有一个（矩形）网格，网格单元的边界在上，例如： x=50*nx 其中：0<；=nx<；=100

y=100*ny 其中-50<；=ny<；=50

因此，单元中心（因为它是矩形网格）可在以下位置找到： xc=25+50*nxc（其中：0<；=nxc<；=99） xc=50+100*nyc（其中：-50<；=nyc<；=49）

（nx，ny，nxc，nyc当然是整数）

有了这个网格，我想能够“绘制”一个多边形，并选择这个多边形内的所有单元（或单元中心）。如何处理这个问题？在

例如多边形

x     y
400   -200
1000  2500
2000  1500
1800  -300
1000  -100
500   -2000

绘制的形状（多边形）只是一个例子，它可以是任何形状。但是，定义形状的多边形没有相互交叉的线。在

矩形网格也可以是任意大小的，但是网格边界的位置及其单元中心是已知的。在

那么如何确定多边形内部的单元（或单元中心）？在

Answer 1

维基百科提供了一个很好的技巧来决定一个点是在多边形内部还是外部。http://en.wikipedia.org/wiki/Point_in_polygon

基本上，选择一条穿过感兴趣单元中某个点的任意直线来计算它与多边形相交的次数。偶数->外部，奇数->内部。因为所有的多边形段都是已知的，这将是微不足道的。注意，如果与方程式存在数学交集，请确保交点实际位于线段上。如果（a1，b1）（a2，b2）表示线段，（x，y）表示交点，请确保x在a1和a2之间，y在b1和b2之间。在

也就是说，要确定一个单元是否在多边形内，需要它的所有4个角点都在多边形中，否则该单元要么部分位于多边形之外，要么完全位于多边形之外。在

编辑：

为了使答案更完整，请覆盖下面这样的凹面案例，其中所有四个角都在多边形中，但并非所有单元格主体都位于多边形中。
检查凹度的一种方法是选择单元格的四个边，而不是任意一条直线，以查看这四条边上是否有>；=2个交点。如果是的话，这可能是一个凹陷的迹象，那么它实际上取决于你对内部或外部的定义。在

---