如何确定一个点在多面体的内部或外部？ [英] How to determine a point is inside or outside the polyhedron?

问题描述

我的多面体有n侧（x1，y1，z1），......，（xn，yn，zn）和点P（x，y，z）。如何确定P在多面体的内部还是外部？谢谢。

I have a polyhedron with n-side (x1, y1, z1),...., (xn, yn, zn) and a point P(x, y, z). How to determine P is inside or outside the polyhedron? Thanks.

推荐答案

我会把它分成两个问题。



1.是否在多面体的边界球，这是一个非常常见的命中测试，将给你非常好的结果。通常这对于任何类型的模拟或游戏都是足够的，因为命中测试的准确性实际上随着边数的增加而增加。



2.如果你真的需要知道点本身是否需要将其视为任何其他多边形。通常，这涉及在任何方向上投射光线并计算交叉点的数量。如果该点位于多边形内部，则它将仅相交一次（正多面体不是凹的），如果它在外部，它将相交零或两次。如果多面体是凹的类型（如星形多面体）那么这就变得难以确定。



如果你搜索google的Point in Polyhedron它会给你一些文章，比如这个StackOverflow答案 [ ^ ]可能会给你你需要的东西。

I would break it into two problems.

1. Is the point inside the bounding sphere of the polyhedron, this is a pretty common hit test and will give you very good results. Typically this would be sufficient for any kind of simulation or game since the accuracy of the hit test actually increases with the number of sides.

2. If you really need to know if the point itself then you need to treat it as any other polygon. Typically this involves casting a ray in any direction and counting the number of intersections. If the point is inside the polygon it will only intersect once (regular polyhedrons are not concave), and if its outside it will intersect zero or twice. If the polyhedron is of a type that is concave (like Star Polyhedrons) then this becomes much harder to determine.

If you search google for "Point in Polyhedron" it will give you a number of articles, and things like this StackOverflow answer[^] that may give you what you need.

这篇关于如何确定一个点在多面体的内部或外部？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！