矩形周围的有效凸壳(并检查船体内是否有一个点)

Question

如果我知道我的点总是被排列成两个矩形，那么是否有一种得到凸包的优化方法？

我编写了经典的凸包算法(通过枚举所有的点)，但是由于我有一堆矩形，所以我在徘徊，如果有更有效的方法来处理这个特殊情况。

这就是我所说的，以澄清：

​

​

我试着用不同的方式对这些点进行排序，但我只是找不到优化它的一般规则。对于这种情况，基本的凸包算法也是最有效的方法吗？

更新

为了明确我的最终目标，我已经把100个矩形分成了两对，还有数千个点，我必须实时地检查它们是否在每个凸壳内。现在我已经考虑过了，我想凸包部分不会成为整个操作中的瓶颈(但是仍然有100个，我的目标是实时处理60fps )，所以我最好使用一个简单的ol‘算法，就像@BartKier建议的那样，然后在剖析之后再回到这个问题上。

我将这个问题搁置一段时间，也许有人有一个优化的想法，无论如何可能是有用的。

Answer 1

如果我是对的，你可以列举所有相关的配置，注意到如果一个矩形的左边比另一个左边多，那么它的两个左顶点就在凸包上。

在四个基本方向上有相同的推理，有16种不同的情况，你可以硬编码。

​

​

另一种看待它的方法是观察凸包是两个矩形的最紧的包围盒，其中0，2或4个角被“切断”。找出边框是很简单的，当一个角不属于任何矩形时，你可以决定它是否被切割。

您可以很容易地从这个规则导出一个点包含测试。如果您已经有了边框测试，那么添加角测试就足够了。