给定几个点和几个圈，我如何分辨哪个点在哪个圈里？

Question

给定少量的点和圆（比方说在100以下），我如何分辨哪个点在哪个圆里？圆圈可以相交，所以一个点可以位于多个圆圈中。

Answer 1

如果点和圆的数目是那么少，你可能会逃脱暴力强迫它。圆点交叉点相当便宜，并且100*100检查一帧应该不会损害性能。

如果您完全确定此例程是瓶颈，需要优化，请继续阅读。

您可以尝试使用限制卷层次结构的变体。

边界卷层次结构是一个树，其中每个节点覆盖两个子卷的整个卷（如果您决定使用更高程度的树，则覆盖更多个子卷）。必须进行交叉测试的卷/对象总是树的叶节点。

插入、删除和交集查询的平均运行时间为O（log n)。但是，您必须更新树，因为您的对象是动态的，这是通过删除和重新插入无效节点（不再完全包含叶子节点的节点）来完成的。更新完整树需要O(n logn)的最坏情况时间。

应当注意，在插入时，应当将节点插入到子树中，从而使子树体积增加最少。

这里是Randy Gaul的一篇很好的博客文章，它很好地解释了动态边界层次结构。

您将不得不使用圆作为包围体，除非您能找到一种方法在除叶节点之外的所有节点中使用AABB，并且圆作为叶节点。AABB更加精确，并且应该给出一个构造得更好的树。