获取由3d多边形包围的点

我有一个位于3D平面上的多边形。 我希望得到这个多边形所包含的所有点。任何人都可以帮助我吗? 我可以通过平面替换扫描线来制作3D扫描线算法,并获得与我的多边形的平面交叉,但我想要更快的解决方案。 提前致谢。

“是的,它是一个凸3p多边形,但它的所有点都在同一个平面上”

在这种情况下 – 只需将多边形和所有测试点转换为平面的2D局部坐标,并使用2D算法:

  • 2D射线拍摄:你仍然可以在我的3D建议中使用类似的算法 – 拍摄源自测试点的2D光线,并计算你击中多边形边界的次数。

  • 线性不等式:如果多边形是凸的,则可以遵循suszterpatt的方法,将多边形定义为半平面ax+by的交集

进一步阅读:

我现在能看到的一种方法是射击 随机 来自您要validation的每个点的任意光线,并计算它与3d网格表面相交的次数。 如果它是奇怪的 – 它在里面,如果是偶数 – 在外面。

如果多边形是凸的,则可以使用以下方法:

多边形的每个面都是由方程ax + by + cz = d给出的平面的一部分。 找到所有面的等式,根据哪个关系描述多边形内部的点,将它们修改为< d> d ,然后求解这个线性不等式系统。 这应该给你一组x,y和z的关系,只有多边形内的点满足。

CygnusX1的答案是标准的多边形点测试,可以针对各种不同的系统进行修改(例如,我有一个编码用于处理球体的版本)。 适应它的主要技巧是决定光线方向。 ‘Abitrary’比’随机’更好。 对于2d欧几里德的工作,我会在平行于其中一个轴(并垂直于另一个轴)的方向上拍摄它。 对于球体,您使用其中一个极点。 对于3d中的2d平面多边形,我很想选择一条垂直于其中一条轴的直线。

或者我会转换我的坐标,以便所有计算都在平面上。 这将大大简化实际的多边形点测试。 我认为这也会更快(对于大型多边形和许多测试而言也是如此):每个多边形角只需要转换一次,但是每个多边形点测试将在两个测试中使用它。

将多边形投影到(x,y)平面上。 现在这是一个二维问题。 2-D投影内的每个点(x,y)表示3-D多边形内的点(x,y,z)。 注意:如果您的平面垂直于(x,y)平面,则不起作用; 如果它几乎是垂直的,你会失去精确度。 因此,在实践中,您将投影到与您的三维平面最不垂直的坐标平面上。

我已经看到使用matplotlib / scipy / numpy之一实现了类似的东西。 我不能完全记住算法,但看看这是否有帮助。