如果我知道我的点总是排列成两个矩形,是否有优化的方法来获得凸包?
我编写了经典的凸包算法(仅通过枚举所有点),但由于我有一堆矩形对,所以我在犹豫是否有更有效的方法来处理这种特殊情况。
这就是我要说的,澄清一下:
我尝试以各种方式对点进行排序,但我就是找不到优化它的一般规则。基本的凸包算法也是处理这种情况的最有效方法吗?
更新
为了阐明我的最终目标,我已经将大约 100 个矩形分成两个一组,还有数千个点,我必须实时检查它们是否位于每个凸包内。现在我已经考虑了一下,我想凸包部分不会成为整个操作的瓶颈(但仍然有 ~100 个,我的目标是实时 60fps 处理),所以我可能以及按照@BartKiers 的建议使用普通的 ol' 算法,然后在分析后返回到这里。
我会暂时搁置这个问题,也许有人有优化的想法,无论如何都可能有用。
最佳答案
如果我是对的,您可以通过注意如果一个矩形的左侧比另一个矩形的左侧更靠左,则它的两个左侧顶点在凸包上,您可以列举所有相关配置。
根据四个基本方向的相同推理,您可以对 16 种不同的情况进行硬编码。
另一种看待它的方法是观察凸包是两个矩形中最紧密的边界框,有 0、2 或 4 个角被“切掉”。找到边界框很简单,当一个角不属于任何矩形时,您可以决定是否切割它。
您可以轻松地从该规则中导出点包含测试。如果您已经有边界框测试,添加角点测试就足够了。
关于algorithm - 矩形周围的高效凸包(并检查点是否位于包内),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28232526/