geometry - 扩展凸包以减少边

Question

我们有一组凸包不重叠的标记点。凸包之间有一些空隙。

给定一个不在我们的数据中的未标记点，我们想大致确定它位于哪个凸包内。

为了加快计算速度，我们希望减少凸包的边数(从而稍微扩大凸包，但不要太多)。

我可以使用哪些算法？

更新:理想情况下，我想在不与给定的附近多边形相交的约束下进行扩展。 (这个约束的动机是我有几个不相交的船体，我想减少它们的边数，同时仍然保持它们不相交。但是把它当作一个括号，因为我不想做联合修改。我是很高兴修改一个船体，同时保持其他船体不变。我很高兴破解这个简单的案例，以迭代方式进行联合修改。)

Answer 1

也许这值得一试。求 A 联合 x 的凸包 A' 和 B 的凸包 B' 联合 x。选择增加船体面积最少的那个。在下面的示例中，A' 是赢家。

---

---

为回应评论而添加:一种路线是通过“最小封闭 k-gons”:

• Mictchell 等人:“Minimum-Perimeter Enclosing k-gon” 2006 ( CiteSeer link )
• Aggarwal 等人:“最小面积外切多边形”1985 (CiteSeer link)
• O'Rourke 等人:“寻找最小封闭三角形的最佳算法”，1986 年，Algorithmica ( ACM link )

但是，这些算法非常复杂，不太可能有多大帮助。