如果想要计算XY坐标是否在特定区域内，应如何操作？

Question

假设我有一个10x10的网格（大小可以是任意的，但为了举例说明，我们假设是10），并且在这个网格中，有3个点标记了三角形的顶点（同样可以是任意数量的点来限定任意的形状）。

那么我的问题是... 只凭这些信息，是否有一种程序化的方法来确定任何给定的坐标是否在该形状内？

假设坐标是3,2-7,3-5,5。我能否在迭代给定的网格时挑选出落在这些点内的单元格？

- galdikas

---

这可能有助于您的研究：这个问题通常被称为点在多边形内。 - Kevin

你想检查一对点是否在多边形内，还是有一个网格并想确定所有属于多边形的正方形？前者是上述的点在多边形问题，后者是光栅化，并需要完全不同的算法（如果你希望它高效）。 - user395760

对于凸形状，这很容易处理，但是你说“任意形状”，所以我假设你会有非凸形状。这正确吗？ - tlehman

@delnan，我需要确定所有在多边形内的点。 - galdikas

@TobiLehman 是的，也可以是非凸的。它用于创建非矩形的元胞自动机模拟。 - galdikas

Answer 1

将文本翻译成中文：

称你要检查的点为P，将该形状的n个顶点命名为S₁,S₂,...,S_n。

假设对于所有i都有P ≠ S_i。

1. P是否在边界上？
2. 如果问题1的答案是否定的，则随机选择一条通过P的直线L
3. 选择一个你知道在多边形外部的点F
4. 从F开始沿着L与该形状相交的顺序一直走到P（将这个序列称为F, ..., P）
5. 计算序列F, ..., P的长度，将结果存储在M中
6. 如果M是偶数，则P在多边形内，否则P不在多边形内

注意：通过引入起始点F，我们改变了维基百科上关于点在多边形算法描述中提到的奇偶性。

- tlehman

---

请注意，OP想要检查所有点。他们实际上正在进行光栅化。对于如此多的点运行点-多边形查询比枚举所有点的算法效率要低得多。 - user395760

这是一个很好的观点，虽然它可以通过选择两个点P和P'，然后在P和P'上都应用步骤4-6来减少一半。 - tlehman

谢谢你的帮助！ - galdikas