按多边形选择网格单元格

Question

对于我正在构建的一个小程序，我有以下情况:例如，我有一个(矩形)网格，网格单元格的边界是:x= 50 * nx，0 <= nx <= 100

和y= 100 * ny和-50 <=纽约<= 50

单元中心(因为它是一个矩形网格)可以在以下位置找到: xc = 25 + 50 * nxc (具有:0 <= nxc <= 99) xc = 50 + 100 * nyc (具有：-50 <= <= 49)

(nx，ny，nxc，nyc当然是整数)

有了这个网格，我希望能够“绘制”一个多边形，并选择在这个多边形中的所有单元格(或单元中心)。怎样才能做到这一点呢？

一个例子是多边形

​

​

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

绘制的形状(多边形)只是一个例子，它可以是任何形状。但是，定义形状的多边形没有相交的线条。

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

那么如何确定多边形内的细胞(或细胞中心)呢？

Answer 1

维基百科提供了一个很好的技巧来决定一个点是在多边形内部还是外部。polygon

基本上，选择一个任意的线，通过一个点的细胞感兴趣的计算，它有多少个交叉点与多边形。偶数->在外面，奇数->在里面。由于所有多边形段都已知，这将是微不足道的。小心，如果有一个与方程的数学交点，确保交点实际上在段上。如果( a1，b1) (a2，b2)代表段，(x，y)代表交集，请确保x在a1和a2之间，y在b1和b2之间。

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

编辑：

为了使答案更完整，以覆盖凹的情况，如下面的四个角都在多边形，但不是所有的细胞体是。

检查凹度的一种方法是，选择单元格的四个边，而不是任意一条线，以查看四个边中是否有>= 2交叉点。如果是的话，这可能是一个凹的迹象，然后它真的取决于你对内或外的定义。