language-agnostic - 有效地确定集合的边界

Question

我正在使用游戏提供的 API 为 RTS 游戏编写 AI。我想做的一件事是确定一组边界敌国的线段，但是，游戏只提供了一个函数，它告诉我领土的单个 2D 点的 teamID。

对游戏 AI 的查询执行起来非常昂贵，因此我需要将查询数量保持在绝对最低限度，即使这意味着偶尔会得到质量稍差的答案。高估敌方领土的面积也比低估它要好。

如何使用最少数量的查询高效地确定一组非凸空间区域周围的边界线？

注意:用 Lua 编写的答案加分，但伪代码也可以。

Answer 1

您可能正在寻找一组点周围的凸包，请参阅:http://en.wikipedia.org/wiki/Convex_hull

这是一个复杂度为 O(n log n) 的问题——在计算上还算不错。对于一些伪代码，请参见:http://en.wikipedia.org/wiki/Graham_scan

编辑:根据您澄清的问题，我知道这些区域不一定是凸的，因此凸包会给您提供比您正在寻找的更广泛的区域。但是，它可能是您可以改进的起点(因为您正在寻找的最终非凸区域位于船体内部)。

更多编辑:如果您真的只有查询单个点的函数，那么您的问题与矢量化位图图像相同。每个点都是一个“像素”，敌人区域是“像素”的(近似)矢量化。