Polytope中的点也就是Hit Test
本文关键字：Hit Test 也就是 Polytope | 更新日期: 2023-09-27 17:49:47
在n维空间中存在一组S点。我想检验一个给定点P是否在S的区域内。
由于这是n维空间，点应该形成一个多面体。接下来的问题是确定给定的点是否在凸多面体内。
我发现这是三维多面体，但c++库没有意义，我找不到它们的定义。此外，它不检查边界条件。
我发现的另一种算法是用于二维多边形。我无法修改，因为写得不清楚。我当然可以扩展它，但我不是这方面的专家，所以最好先问一下。
最后我找到了一个凹多边形的三角剖分算法，但我认为它不适合我的情况。
不知道你到底在问什么，似乎你有几个问题。首先计算一个点集的凸包。在2d中，您可以使用BOOST或CGAL。对于3d CGAL。不确定它们能不能处理高维。对于内部检查，一种方法是(如您发布的链接所述)检查从查询点到已知外部点的射线相交。射线的交点(对于内点)应该位于法线指向与射线相同方向的平面上。意思是你正在退出这个卷。更有效的方法是使用二进制空间分区树(BSP)之类的东西。有很多关于如何工作的教程链接。
根据你们的描述，你们已经确定S是凸的。如果是这种情况，可以应用超平面分离定理(http://en.wikipedia.org/wiki/Hyperplane_separation_theorem)
- 求S中离p最近的点Q
- 构造一个位于Q上且垂直于P-Q的超平面H
- 测试S中与H边对应的所有点
- 如果它们都在平面上或者相对于P在H的另一边，那么P要么在s的上面要么在s的外面。如果一些点在H的前面，一些点在H的后面，那么P在s的里面。