粗略测试点是否为凸包的 inside/outside
Rough test if points are inside/outside of convex hull
我正在研究一种算法，我必须检查点是在某些点的凸包内部还是外部。问题是
- 我要检查这个很多点：~2000，
- 定义凸包的点云有大约 10000 个点，
- 我工作的尺寸相当高：10-50。
我的观点唯一可能的积极因素是，对于每个点 x，也有 -x，因此这些点定义了一个点对称多面体，并且凸包没有退化（内部非空）。
现在我正在用线性规划来做这个，例如
为了加快我的程序，我想在精确计算之前估计一个点是否确定在凸包内部或外部。换句话说，我需要一些快速算法来确定某些点是否在内部。他们是否在外面-对于某些点，快速算法无法决定。
我现在正在做的是首先查看我的点云的边界框，其次是 中的方法 - yombo 的评论。
但是这两种方法都只能确定一个点是否肯定在外面（而且这两种方法都比较粗糙）。
因为我检查的大部分点都在内部，所以我主要需要一个测试来确定一个点是否肯定在内部。
长问短：
我需要一种可以非常快速地测试的算法，无论一个点是否 inside/outside 凸包。
允许该算法报告 "inside"、"no idea" 和 "outside".
为了快速清除经证明位于凸包内的点，您可以重复使用在边界框计算中找到的点。
即，包含每个维度中的最小值和最大值的 2k 个点（维度 k）。
您可以构建一个小型（2k 约束）线性规划问题，并清除这 2k 个点的凸包内的任何点。
您可以对查询点和原始点云都执行此操作，这将为您留下一个较小的线性规划问题来解决剩余的点。
我正在研究一种算法，我必须检查点是在某些点的凸包内部还是外部。问题是
- 我要检查这个很多点：~2000，
- 定义凸包的点云有大约 10000 个点，
- 我工作的尺寸相当高：10-50。
我的观点唯一可能的积极因素是，对于每个点 x，也有 -x，因此这些点定义了一个点对称多面体，并且凸包没有退化（内部非空）。
现在我正在用线性规划来做这个，例如
为了加快我的程序，我想在精确计算之前估计一个点是否确定在凸包内部或外部。换句话说，我需要一些快速算法来确定某些点是否在内部。他们是否在外面-对于某些点，快速算法无法决定。
我现在正在做的是首先查看我的点云的边界框，其次是 中的方法 - yombo 的评论。 但是这两种方法都只能确定一个点是否肯定在外面（而且这两种方法都比较粗糙）。
因为我检查的大部分点都在内部，所以我主要需要一个测试来确定一个点是否肯定在内部。
长问短： 我需要一种可以非常快速地测试的算法，无论一个点是否 inside/outside 凸包。 允许该算法报告 "inside"、"no idea" 和 "outside".
为了快速清除经证明位于凸包内的点，您可以重复使用在边界框计算中找到的点。 即，包含每个维度中的最小值和最大值的 2k 个点（维度 k）。
您可以构建一个小型（2k 约束）线性规划问题，并清除这 2k 个点的凸包内的任何点。
您可以对查询点和原始点云都执行此操作，这将为您留下一个较小的线性规划问题来解决剩余的点。