select 多边形网格单元

Question

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

y = 100 * 纽约州 -50 <= 纽约州 <= 50

因此，单元格中心（因为它是一个矩形网格）位于： xc = 25 + 50 * nxc（其中：0 <= nxc <= 99） xc = 50 + 100 * 纽约市（其中：-50 <= 纽约市 <= 49）

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

有了这个网格，我希望能够 "draw" 一个多边形和 select 这个多边形内的所有单元格（或单元格中心）。如何解决这个问题？

示例多边形是

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 个交点。如果是，它可能是凹陷的标志，然后它真的取决于你对内部或外部的定义。

---