代码之家 › 专栏 › 技术社区 › Lou

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

convex-hull algorithm

2

Lou · 技术社区 · 10 年前

如果我知道我的点总是排列成两个矩形,那么有没有一种优化的方法来获得凸包?

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

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

Convex hull around pairs of rectangles

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

使现代化

为了明确我的最终目标,我已经将大约100个矩形分成两对,以及数千个点,我必须实时检查它们是否位于每个凸包内。现在我已经考虑过了,我想凸包部分不会成为整个操作的瓶颈(但仍有约100个,我的目标是实时60fps处理),所以我不妨使用@BartKiers建议的普通算法,然后在分析之后再讨论这个问题。

我将暂时不回答这个问题,也许有人有一个优化的想法,无论如何都可能有用。

1 回复 | 直到 10 年前

1

8

Yves Daoust 10 年前

如果我是对的,你可以列举所有相关的配置,注意如果一个矩形的左侧比另一个的左侧更靠左,那么它的两个左侧顶点位于凸包上。

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

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

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