algorithm - 矩形周围的高效凸包(并检查点是否位于包内)

Question

如果我知道我的点总是排列成两个矩形，是否有优化的方法来获得凸包？

我编写了经典的凸包算法(仅通过枚举所有点)，但由于我有一堆矩形对，所以我在犹豫是否有更有效的方法来处理这种特殊情况。

这就是我要说的，澄清一下:

我尝试以各种方式对点进行排序，但我就是找不到优化它的一般规则。基本的凸包算法也是处理这种情况的最有效方法吗？

更新

为了阐明我的最终目标，我已经将大约 100 个矩形分成两个一组，还有数千个点，我必须实时检查它们是否位于每个凸包内。现在我已经考虑了一下，我想凸包部分不会成为整个操作的瓶颈(但仍然有 ~100 个，我的目标是实时 60fps 处理)，所以我可能以及按照@BartKiers 的建议使用普通的 ol' 算法，然后在分析后返回到这里。

我会暂时搁置这个问题，也许有人有优化的想法，无论如何都可能有用。

Answer 1

如果我是对的，您可以通过注意如果一个矩形的左侧比另一个矩形的左侧更靠左，则它的两个左侧顶点在凸包上，您可以列举所有相关配置。

根据四个基本方向的相同推理，您可以对 16 种不同的情况进行硬编码。

另一种看待它的方法是观察凸包是两个矩形中最紧密的边界框，有 0、2 或 4 个角被“切掉”。找到边界框很简单，当一个角不属于任何矩形时，您可以决定是否切割它。

您可以轻松地从该规则中导出点包含测试。如果您已经有边界框测试，添加角点测试就足够了。