查找重叠的圆
我知道如何检查其中两个圆是否重叠（它们中心之间的距离小于直径）。我可以对每对圆执行此检查，但我想知道是否有更好的算法（比O(n^2))更快）。
编辑
圆圈的数目通常是100个左右，重叠不会经常发生。
共有1个答案
鉴于对问题陈述的新解释，我将推荐一种不同的方法。
在战场上覆盖一个正方形网格，网格步长等于一个圆直径。每个圆圈最多可以重叠四个单元格。在每个单元格中，保留一个重叠圆的列表（并在每次移动时更新它）。
探测潜在的碰撞现在将需要每圈大约四个单元/圈测试，即接近线性时间。
-
问题内容： 我在数据库中有2个表，这些表具有以下属性： 第二个表是“预订”和“资源”之间的关联实体（即1个预订可以包含许多资源）。属性booking_start和booking_end是带有日期和时间的时间戳。 我是否可以知道如果日期/时间与其他类似resource_id的预订重叠或冲突，我如何能够找到每个resource_id（预订的）？ 我以图形方式在纸上涂上答案，以查看它是否可以帮助我形象化
-
问题内容： 我想从间隔与查询中指定的间隔相交的表中提取行。假设我有一个简单的表和两个查询参数，并且，表达查询的最简单方法是什么，以便找到具有至少一个公共元素的所有行？ 更新： 为了使预期结果更加清晰，请在下面找到输入值和预期结果的列表。列是 。 问题答案： 更简单：
-
我试图找出两个矩形是否相互重叠。我将下面的矩形表示为< code>[x1，x2] x [y1，y2] 我只需要一个伪代码，我可以实现它来查找矩形是否彼此重叠。
-
问题内容： 我试图找到一种基于特定列（id）在数据框中查找重叠数据范围（每行提供的开始/结束日期）的更有效方法。 数据框在“来自”列上排序 我认为有一种方法可以像我一样避免“双重”应用功能… 我使用“应用”功能在所有组上循环，并且在每个组中，每行使用“应用”： 问题答案： 您可以移动列并直接减去日期时间。 分组时应用它可能看起来像 演示版
-
假设我有一个表，它有两列X1和X2，其中X1总是小于X2。每行构成一定的范围（X1，X2）。可能有几行的X1/X2范围重叠，从而产生更大的范围（X1n，X2m）。 有没有办法使用标准SQL查询来查找所有这些范围？ 例如，该表可能如下所示： 预期产出将是： 我非常感谢您在正确方向上对我们的帮助。 我正在使用sqlite。
-
给定两个字符串，我想识别从最长到最短的所有公共子字符串。 最后，我需要检查一个字符串与数千个字符串的固定列表。我不确定在散列出这些字符串中的所有子字符串时是否有一个明智的步骤。 先前的答复： 在这个线程中，发现了一个动态编程解决方案，它需要O（nm）时间，其中n和m是字符串的长度。我对一种更有效的方法感兴趣，它将使用后缀树。 背景： 我正在根据旋律片段创作歌曲旋律。有时，一个组合会产生一个旋律，与