java - 在java中表示二维球堆

Question

我正在创建一个应用程序，需要使用 java 来建模(并显示)大量二维“球”(圆圈)。我首先创建一个由 Circle 对象组成的 ArrayList(我定义的一个类，其中包含圆心的 x/y 像素坐标、半径、颜色、以及 x 和 y 方向的速度)。我使用 java.util.Timer 对象和重复的 TimerTask 来控制圆圈的运动。这些圆圈的大小各不相同，半径约为 10-50 像素。

我想要发生的是让球从屏幕顶部落下(随机分布在 x 轴上)，直到它们到达屏幕底部，这就像地板一样 - 到达它的球停止移动，到达停止球的球会在其他球上滚下坡，直到它们停留在低点/平坦点。将来我可能想让它们的行为变得更复杂一点，所以我想创建灵活的代码，以便我可以轻松扩展。现在的工作原理是，每个时间段每个圆圈都会检查它们与其他每个圆圈的接近程度。如果附近没有其他圆圈，它们会继续正常下降。如果两个(或更多)圆圈彼此靠近，则有代码确定它们将如何相互作用。

我让它对于少量的圆圈(< 200)来说工作得很好，但是当我得到大量的圆圈(> 400)时，它开始显着减慢。我确信我可以优化一些逻辑以使比较更快一点，但我想知道除了无组织的 ArrayList 之外是否有任何方法可以将圆存储在某种结构中，这可以让我轻松找到彼此靠近的圆，因此我不必执行将每个圆与其他圆进行比较的 N^2 操作，而是只需将一个圆与最接近它的 5-10 个圆进行比较即可。例如，我考虑过使用 2D 数组来表示每个像素(或者可能是 5x5 像素的正方形)并在其中心所在的位置存储一个圆(这样我可以检查任何附近的单元格中是否有圆，并忽略休息)。然而，这看起来仍然相当低效，就好像我使用带有 500 个圆圈的 800x1000 像素 Canvas 一样，二维数组中会有大量空白空间，我会浪费时间检查这些空白空间。我也考虑过某种 HashMap ，但我也没有想到使用它的好方法。

那么，有人能想到一种有效的方法来存储这些与二维空间中的位置相对应的圆圈，并可以轻松找到附近的圆圈吗？提前致谢!

Answer 1

您可以使用四叉树来查找近邻。或者您可以简单地按一个方向排序，这会更容易实现，并且仍然允许您将候选邻居的数量减少到一个小窗口。