c++ - c++中动力学凸包的拆分和合并

Question

注意：我不确定这个问题是否属于这里，如果合适，请移至适当的 stackexchange 站点。

我正在开发一个多人游戏。

我想在我的代码中维护：2d 集群。

什么是集群：它们是用户的聚合（用户周围的凸包）。

什么是用户：用户有 ax,y 位置和他可以影响的信封。理想情况下，信封可以是一个圆形，其半径是他能看到多远。集群中的每个用户信封应与同一集群中的至少一个其他信封相交。

在图中，我有 4 个集群。第 2 和第 3 幅图显示了随着用户移动新集群将如何形成。在此处输入图像描述

随着用户四处移动，集群将分裂或合并以保持上述属性。

我想知道“动力学凸包”是否是我应该寻找解决方案以在我的 c++ 游戏代码中实现这种集群维护的正确区域。

注意：我现在正在阅读有关动力学凸包的信息，但我还没有完成，但我认为它涉及围绕一组固定点形成凸包。我需要那个，但我还需要将船体分成两个或更多，当船体内的用户信封不与同一船体内的其他信封相交时。例如上面第三张图片中的 A。

score 0 · Accepted Answer

不是专家，但看起来您需要检查每个用户移动的交叉点（仅检查移动用户）。如果用户的信封已停止与来自同一船体的用户相交，则您需要重建船体。您还需要检查用户的信封是否也开始与另一个用户的信封相交。如果是这样 - 您将需要重建旧船体和新船体（可能合并它们）。

编辑：澄清

基本上，在每次用户移动时，您都必须检查移动用户的状态：

如果该用户的信封已停止与其他用户的信封相交 - 将该用户排除在船体之外
如果此用户的信封已开始与其他用户的信封相交
1. 如果此用户不是任何其他船体的一部分，则将其添加到其他用户的船体
2. 如果此用户是另一个船体的一部分 - 合并船体

score 0 · Accepted Answer

根据您的描述，我不明白您为什么需要凸包。

在您的第三张图片中，B 和 F 之间的空白空间将位于凸包内。船体本身将从 B 到 F。

（注意：包络的外壳与 B 和 F 的包络相切。计算起来比较困难，但很容易近似。）

如果这类信息对您的游戏有用，那么凸包就适合您！如果动力学凸包不支持拆分/合并，则只需重新计算凸包。但是这么少的点，无论如何这不应该是一个昂贵的操作。至少它不适用于非动力船体。

2 回答 2